明薇通网站建设,国内设计精美的网站,工程建设领域专项治理工作网站,把网站做成手机版请简述深度优先遍历、广度优先遍历的基本思想#xff1f;#xff1a; 深度遍历是在图中先选择一个顶点#xff0c;随后的每次遍历中选择与顶点相邻并且还没有遍历过的结点进行遍历#xff0c;类似于树的先序遍历 广度遍历是先在图中选择一个顶点#xff0c;并加入队列中 深度遍历是在图中先选择一个顶点随后的每次遍历中选择与顶点相邻并且还没有遍历过的结点进行遍历类似于树的先序遍历 广度遍历是先在图中选择一个顶点并加入队列中然后向该顶点的所有未访问过的邻接点进行扩散加入到队列当中类似于树的广度遍历 简述二叉树完全二叉树二叉排序树平衡二叉树的特性
二叉树Binary Tree要求其任意节点的子节点数量不超过2分左节点即左子树和右节点即右子树。
完全二叉树Complete Binary Tree要求所有叶子点都在最后一层或者倒数第二层且最后一层的叶子结点在左边连续倒数第二层的叶子结点右侧连续。
二叉排序树Binary Search Tree也叫二叉搜索树如果左子树不空则子树上面的所有节点的值均小于或者等于根节点的值。而且如果右子树不空则右子树的所有节点的值均大于或者等于根节点的值。其根节点的左右子树都是二叉排序树或者是一颗空树。
平衡二叉树Balanced Binary Tree也叫AVL树它是一颗空树或者其左右子树高度差绝对值不超过1即只有度位0或者1的二叉树其左右的两个子树都均为平衡二叉树。 简述什么是队列的上溢出现象和假溢出现象解决它们的办法有哪些 先进先出FIFO在队列的顺序存储结构中设头指针为front队尾指针为rear队的容量存储空间的大小为m。当有元素加入到队列时若rearm(初始时rear0)则发生队列的上溢出现象该元素不能加入到队列中。
队列的假溢出现象是指队列中虽然还有空余的空间但元素不能进队列——造成这种现象的原因是由于队列的操作方式所致。
解决队列上溢的方法有
建立一个足够大的存储空间但这样做往往造成空间使用效率低 当出现假溢出时可采用以下几种方法
采用平移元素的方法。每当队列中加入一个元素时队列中已有的元素向队头移动一 个位置当然要有空余的空间可移
每当删除一个队头元素时则依次序移动队中的元素始终使front指针指向队列中 的第一个位置
采用循环队列方式。把队列看成一个首尾相邻的循环队列虽然物理上队尾在队首之 前但逻辑上队首仍然在前作插入和删除运算时仍按“FIFO”的原则。
建立一个足够大的存储空间但这样做往往造成空间使用效率低。
简述单链表设置头节点的作用是什么?至少说出两条好处) 链表中第一个结点的存储位置叫做头指针那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点其实就是上一个的后继指针指向的位置。“链表中第一个结点的存储位置叫做头指针”如果链表有头结点那么头指针就是指向头结点数据域的指针。
头结点是为了操作的统一与方便而设立的放在第一个元素结点之前其数据域一般无意义当然有些情况下也可存放链表的长度、用做监视哨等等。
有了头结点后对在第一个元素结点前插入结点和删除第一个结点其操作与对其它结点的操作统一了。
首元结点也就是第一个元素的结点它是头结点后边的第一个结点而且头结点不是链表所必需的。
在线性表的链式存储结构中头指针是指链表指向第一个结点的指针若链表有头结点则头指针就是指向链表头结点的指针。
头指针具有标识作用故常用头指针冠以链表的名字。
无论链表是否为空头指针均不为空。头指针是链表的必要元素。
若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构? 为什么? 若线性表需要频繁查找很少进行插入和删除操作时宜采用顺序存储结构。若需要频繁插入和删除时宜采用单链表结构。 当线性表中的元素个数变化较大或者根本不知道有多大时最好用单链表结构这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度用顺序存储结构效率会高很多。 为什么会引入线索二叉树它有什么优势 对于一个有n个结点的二叉链表每个结点有指向左右孩子的两个指针域所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线树即其实是存在2n-(n-1)n1个空指针域。这些空间不存储任何事物造成空间的浪费就想到了线索二叉树。 线索二叉树指向前驱和后继的指针称为线索加上线索的二叉链表称为线索链表相应的二叉树就称为线索二叉树。其中对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。 对于有大量的插入和查找的二叉树来说线索二叉树比较适用。 当线性表中的元素个数变化较大或者根本不知道有多大时最好用单链表结构这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度用顺序存储结构效率会高很多。 优点因为二叉树在遍历的时候如果你想找到某个节点的前驱节点就必须把整个二叉树全部遍历一遍而线索二叉树相当于一个双向链表可以很简单的找到某个节点的前驱节点通常使用中序线索二叉树因为通常叶子节点有空节点根据中序遍历左-中-右的遍历特点很容易几乎将整个二叉树连接起来. 循环比递归的效率一定高吗 递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高递归和循环是两码事递归带有栈操作循环则不一定不同场景做不同的尝试。
递归算法
优点代码简洁、清晰并且容易验证正确性。
缺点它的运行需要较多次数的函数调用如果调用层数比较深需要增加额外的堆栈处理有可能出现堆栈溢出比如参数传递需要压栈等操作会对执行效率有一定影响。对于某些问题不使用递归代码会艰涩难懂。
循环算法
优点速度快结构简单。
缺点不能解决所有问题。有的适合使用递归而不是循环使用循环并不困难的话最好使用循环。
递归算法和循环算法总结
一般递归调用可以处理的算法也通过循环去解决常需要额外的低效处理。 现在的编译器在优化后对于多次调用的函数处理会有非常好的效率优化效率未必低于循环。 递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换而不影响程序的阅读那么替换成递归往往是好的——比如求阶乘的递归实现与循环实现。 请比较 AOE 网与 AOV 网 从定义上来看很容易看出两种网的不同AOV网的活动以顶点表示而AOE网的活动以有向边来表示AOV网的有向边仅仅表示活动的先后次序。纵观这两种网图其实它们总体网络结构是一样的仅仅是活动所表示的方式不同因此可以猜想从AOV网转换成AOE网应该是可行的。
通常AOE网都是和关键路径联系在一起的在AOE网中我们可以通过关键路径法来计算影响整个工期的关键路径达到缩短工期的目的。在传统的AOV网中是没有表示活动时间的权值的因此传统的AOV网无法估算工期但是如果我们在AOV网中的活动结点上都标上时间属性那么AOV网就可以完全转换为AOE网。 栈和队列的异同点 栈与队列的相同点
1.都是线性结构。
2.插入操作都是限定在表尾进行。
3.都可以通过顺序结构和链式结构实现。、
4.插入与删除的时间复杂度都是O1在空间复杂度上两者也一样。
5.多链栈和多链队列的管理模式可以相同。
栈与队列的不同点
1.删除数据元素的位置不同栈的删除操作在表尾进行队列的删除操作在表头进行。
2.应用场景不同常见栈的应用场景包括括号问题的求解表达式的转换和求值函数调用和递归实现深度优先搜索遍历等常见的队列的应用场景包括计算机系统中各种资源的管理消息缓冲器的管理和广度优先搜索遍历等。
3.顺序栈能够实现多栈空间共享而顺序队列不能。
4.栈先进后出队列先进先出 栈在后缀表达式求值的算法思想 算法思想遍历整个表达式如果是操作数入栈。如果是操作符将当前栈顶元素和栈第二个元素出栈进行运算并将结果压栈。若是除减操作符第二个元素作为被除数被减数栈顶元素作为除数减数。表达式遍历完后当前栈的栈顶元素即为所求表达式的值。 Dijkstra 算法和 BFS 求的最短路径有什么区别吗 dijkstra算法是求单源点的最短路径问题要求权值不能为负bfs算法则是从某顶点出发按广度优先的原则依次访问各连通的顶点图可以无权值
dijkstra是bfs的升级版就是说如果求最短路径当图从无权值变成有权值时bfs不再适用了于是我们用dijkstra方法。换句话说对于无权值图dijkstra方法跟bfs是一致的。你可以画个无权图用dijkstra走一遍发现其实这就是bfs。 简述什么是哈夫曼树 当用 n 个结点都做叶子结点且都有各自的权值试图构建一棵树时如果构建的这棵树的带权路径长度最小称这棵树为“最优二叉树”有时也叫“赫夫曼树”或者“哈夫曼树”。在构建哈弗曼树时要使树的带权路径长度最小只需要遵循一个原则那就是权重越大的结点离树根越近。 树的带权路径长度(WPL)为树中所有叶子结点的带权路径长度之和。构建哈夫曼树是从叶子结点开始不断地构建新的父结点直至树根所以结点中应包含指向父结点的指针。使用哈夫曼树时是从树根开始根据需求遍历树中的结点因此每个结点需要有指向其左孩子和右孩子的指针。 时间复杂度为 O(nlogn)的排序方法 快速排序
从数组中取出一个数称之为基数 遍历数组将比基数大的数字放到它的右边比基数小的数字放到它的左边。遍历完成后数组被分成了左右两个区域 将左右两个区域视为两个数组重复前两个步骤直到排序完成 按照上述规则每轮中的基数都被调整到其最终的位置上第一轮遍历排好 1 个基数第二轮遍历排好 2 个基数两个子数组中有两个基数第三轮遍历排好 4 个基数四个子数组中有四个基数… 因此总遍历轮数为logn ~ n 次
归并排序
针对两个无序数组开辟一个长度等同于两个数组长度之和的新数组并使用两个指针来遍历原有的两个数组不断将较小的数字添加到新数组中并移动对应的指针即可。
针对一个无序数组我们可以把数组不断地拆成两份直到只剩下一个数字时这一个数字组成的数组我们就可以认为它是有序的两个对于两个由一个数字组成的数组我们就可以使用归并排序得到一个有两个数字的有序数组然后再将这些拆分的数组不断的两两组合起来就完成了归并排序。
堆排序
用数列构建出一个大顶堆取出堆顶的数字 调整剩余的数字构建出新的大顶堆再次取出堆顶的数字 循环往复完成整个排序。 希尔排序
将待排序数组按照一定的间隔进行排序如此时排序间隔为gap则从indexgap处的元素开始排序对于index i的元素每次和当前index - gap处的元素进行比较直到符合插入条件然后继续比较index i的元素直到数组末尾完成当前间隔的排序 逐渐缩小间隔进行下一轮排序 最后一轮时取间隔为 1也就相当于直接使用插入排序。但这时经过前面的「宏观调控」数组已经基本有序了所以此时的插入排序只需进行少量交换便可完成 排序算法稳定性的定义有那些不稳定排序 稳定排序排序前后两个相等的数相对位置不变则算法稳定 非稳定排序排序前后两个相等的数相对位置发生了变化则算法不稳定
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法 堆排序是否是一种稳定的排序方法?为什么? 我们知道堆的结构是节点i的孩子为2i和2i1节点大顶堆要求父节点大于等于其2个子节点小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了而第n/2-1个父节点把后面一个相同的元素没有交换那么这2个相同的元素之间的稳定性就被破坏了。所以堆排序不是稳定的排序算法 比较直接插入排序算法和希尔排序算法的不同点 直接插入排序
算法描述顾名思义直接插入排序就是将待插入的数据插入到该数据之前的有序序列的正确位置处使得序列依然有序的排序算法。当数据有序且不需要移动是时间复杂度为On当为逆序时每次插入都需要移动数据效率最差则时间复杂度为On2。在插入过程中需要用一个临时的辅助空间来保存待插入的数据所以该算法的平均时间复杂度为On2)空间复杂度为O1。另外由于数据是一个一个逐个插入所以这还是一种稳定的排序算法。
希尔排序算法
算法描述希尔排序是按其设计者希尔Donald Shell的名字命名它是一种基于插入排序的快速排序算法是对直接插入排序时间复杂度上的优化。希尔排序通过将需要排序的数据分为若干个区域来提升插入排序的性能每次能够使数据前进给定的步长然后每次减小步长再进行插入排序最后变为一个普通的插入排序但到了这时数据已经变得局部有序所以此时的插入排序比较快。 树的存储结构有哪些
对于存储结构可能会联想到前面的顺序存储和链式存储结构。但是对于数这种可能会有很多孩子的特殊数据结构只用顺序存储结构或者链式存储结构很那实现那么可以将这两者结合产生主要的三种存储结构表示法双亲表示法、孩子表示法、孩子兄弟表示法 栈在括号匹配中的算法思想
1凡出现左括弧则进栈 2凡出现右括弧首先检查栈是否空 若栈空则表明该“右括弧”多余否则和栈顶元素比较若相匹配则“左括弧出栈” 否则表明不匹配。 3表达式检验结束时若栈空则表明表达式中匹配正确否则表明“左括弧”有余 贪心算法和动态规划以及分治法的区别 分治法与动态规划的相同点 分治法与动态规划二者要求原问题具有最有子结构都是将问题分而治之分解成若干个规模较小的子问题
不同点 动态规划是将原问题分解为多个子问题通过计算出子问题的结果构造一个最优解。动态规划通过迭代法自底向上求解动态规划将分解后的子问题理解为相互间有联系有重叠的部分 算法的应用装配线矩阵乘法最长公共子序列构造最优的二叉树 分治法是将原问题分解为多个子问题利用递归对各个子问题独立求解最后利用各子问题的解进行合并形成原问题的解。分治法将分解后的子问题看成是相互独立的。
例如在求解斐波那契数列过程中 求解fibonacci(5)求解fibonacci(5)时,得求解fibonacci(4)和fibonacci(3).其中,求解fibonacci(4)时,需要求解fibonacci(3). 在分治法中,求解完fibonacci(4)后还得重新求解fibonacci(3),即使求解fibonacci(4)子问题的时候已经求解过,也就是说,求解了二次子问题fibonacci(3).
贪心算法依赖于当前已经做出的所有选择采用自顶向下(每一步根据策略得到当前一个最优解保证每一步都是选择当前最优的)的解决方法。 贪心算法的应用最小生成树最短路径数据压缩–哈夫曼编码 有哪些哈希函数的构造方法列举一些 直接定址法
取关键字或关键字的某个线性函数值为散列地址。 即 H(key) key 或 H(key) a*key b其中a和b为常数。 除留余数法
取关键字被某个不大于散列表长度 m 的数 p 求余得到的作为散列地址。 即 H(key) key % p, p m。 数字分析法
当关键字的位数大于地址的位数对关键字的各位分布进行分析选出分布均匀的任意几位作为散列地址。 仅适用于所有关键字都已知的情况下根据实际应用确定要选取的部分尽量避免发生冲突。 平方取中法
先计算出关键字值的平方然后取平方值中间几位作为散列地址。 随机分布的关键字得到的散列地址也是随机分布的。 折叠法叠加法
将关键字分为位数相同的几部分然后取这几部分的叠加和舍去进位作为散列地址。 用于关键字位数较多并且关键字中每一位上数字分布大致均匀。 随机数法
选择一个随机函数把关键字的随机函数值作为它的哈希值。 通常当关键字的长度不等时用这种方法。 如何由遍历序列构造一棵二叉树 在先序遍历序列中第一个结点一定是二叉树的根结点而在中序遍历中根结点必然将中序序列分割成两个子序列前一个子序列是根结点的左子树的中序序列后一个子序列是根结点的右子树的中序序列。
根据这两个子序列在先序序列中找到对应的左子序列和右子序列。在先序序列中左子序列的第一个结点是左子序列的根结点右子序列的第一个结点是右子树的根结点。
如此递归地进行下去便能唯一地确定这一唯一二叉树
