数据结构与算法-面试题汇总 女爷i 2022-11-14 13:25 171阅读 0赞 **目录** 栈和队列 哈希表 什么是哈希表,哈希表的实现是怎么样的,哈希冲突是什么,怎么解决哈希冲突? 树 简述完全二叉树 简述AVL树 简述红黑树 红黑树和AVL树有什么区别? 图 简述最小生成树和其对应的算法 简述最短路径算法 排序 简述稳定排序和非稳定排序的区别 常见的稳定排序算法有哪些 常见的不稳定排序算法有哪些 简述快速排序 简述希尔排序 简述归并排序 简述堆排序 -------------------- # 栈和队列 # **栈**是一种**后进先出**的线性表,其限制只能在表尾进行插入或删除操作。 **队列**是一种**先进先出**的线性表。其限制只能在线性表的一端进行插入,而在另一端删除元素。 # 哈希表 # ## 什么是哈希表,哈希表的实现是怎么样的,哈希冲突是什么,怎么解决哈希冲突? ## 哈希表(又名散列表)是根据键(key)直接访问内存存储位置的一种数据结构,通过计算一个关于键值的函数,将所需查询的数据映射到表中的一个位置来访问记录,映射函数叫做散列函数,存放记录的数组叫散列表 哈希冲突的解决办法: * 开放定址法:当发生哈希冲突时,如果哈希表未被装满,那么可以把这个值存放到冲突位置中的下一个空位置中去 * 链地址法:对相同的哈希地址,设置一个单链表,单链表内放的都是哈希冲突 * 再哈希法:又叫双哈希法,有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数计算地址,直到无冲突。虽然不易发生聚集,但是增加了计算时间。 * **建立公共溢出区: 将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表** # 树 # ## **简述完全二叉树** ## 一棵**深度为k**的有**n个结点**的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点**与满二叉树中编号为i的结点在二叉树中的位置相同**,则这棵二叉树称为完全二叉树。 ## **简述AVL树** ## AVL树是一种改进版的搜索二叉树,其引入平衡因子(左子支高度与右子支高度之差的绝对值),通过旋转使其尽量保持平衡。任何一个节点的左子支高度与右子支高度之差的绝对值不超过1。 ## **简述红黑树** ## 红黑树本身是有2-3树发展而来,红黑树是保持黑平衡的二叉树,其查找会比AVL树慢一点,添加和删除元素会比AVL树快一点。增删改查统计性能上讲,红黑树更优。红黑树主要特征是在每个节点上增加一个属性表示节点颜色,可以红色或黑色。红黑树和 AVL 树类似,都是在进行插入和删除时通过旋转保持自身平衡,从而获得较高的查找性能。红黑树保证从根节点到叶尾的最长路径不超过最短路径的 2 倍,所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转,更加高效地完成了插入和删除之后的自平衡调整。 ## 红黑树和AVL树有什么区别? ## 红黑树的优点 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。所以红黑树的插入效率更高!!! 与AVL树的比较 红黑树要求从根节点到叶子节点的最长路径不大于最短路径的两倍 AVL 树要求每一个子树的左右孩子节点高度差不超过1 保持平衡的要求上面,AVL树要求大于RBtree, 也就带来了search, insert 和delete操作的性能差异 相同点 # 图 # ## **简述最小生成树和其对应的算法** ## 最小生成树:对于有 n 个结点的原图,生成原图的极小连通子图,其**包含原图中的所有 n 个结点**,并且有保持图连通的**最少的边。** 普里姆算法(加点):取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。 克鲁斯卡尔算法(加边):先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使 SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止。 ## **简述最短路径算法** ## Dijkstral算法为求解一个点到其余各点最小路径的方法,其算法为: 假设我们求解的是顶点v到其余各个点的最短距离。n次循环至n个顶点全部遍历: 1. 从权值数组中找到权值最小的,标记该边端点k 2. 打印该路径及权值 3. 如果存在经过顶点k到顶点i的边比v->i的权值小 4. 更新权值数组及对应路径 # 排序 # ## **简述稳定排序和非稳定排序的区别** ## 稳定排序:排序前后两个**相等的数相对位置**不变,则算法稳定 非稳定排序:排序前后两个相等的数相对位置发生了变化,则算法不稳定 ## **常见的稳定排序算法有哪些** ## 插入排序、冒泡排序、归并排序 ## **常见的不稳定排序算法有哪些** ## 希尔排序、直接选择排序、堆排序、快速排序 ## **简述快速排序** ## 随机选择一个基准元素,通过一趟排序将要排序的数据分割成独立的两部分,一部分全部小于等于基准元素,一部分全部大于等于基准元素,再按此方法递归对这两部分数据进行快速排序。 排序算法**不稳定**,时间复杂度 O(nlogn),空间复杂度 O(logn)。 ## **简述希尔排序** ## 希尔排序:把记录按下标的一定增量分组,对每组进行直接插入排序,每次排序后减小增量,当增量减至 1 时排序完毕。 排序算法**不稳定**。时间复杂度 O(nlogn),空间复杂度 O(1)。 ## **简述归并排序** ## 归并排序:将待排序序列分成两部分,然后对两部分分别递归排序,最后进行合并。 排序算法**稳定**,时间复杂度都为 O(nlogn),空间复杂度为 O(n)。 ## **简述堆排序** ## 堆排序:将待排序数组看作一个树状数组,建立一个二叉树堆。通过对这种数据结构进行每个元素的插入,完成排序工作。 排序算法**不稳定**,时间复杂度 O(nlogn),空间复杂度 O(1)。
还没有评论,来说两句吧...