考研数据结构与操作系统在线题库每日一练（二十）
以下是希赛网给大家分享考研数据结构与操作系统在线题库每日一练，希望通过刷题可以帮助大家巩固重要知识点，对知识点查漏补缺，祝愿大家能顺利通过考试！
本文提供考研数据结构与操作系统在线题库每日一练，以下为具体内容
2、下列哪个算法适合求稀疏图的最小生成树？（）
A、Prim
B、Kruskal
C、Dijkstra
D、Floyd
3、图的广度优先遍历类似于树的？（）
A、先序遍历
B、中序遍历
C、后序遍历
D、层序遍历
4、采用线性探测再散列解决冲突的方式，若查找到一个关键字可能经过多次探测地址，则这些探测到的关键字？（）
A、一定是同义字
B、一定不是同义字
C、可能是同义字
D、以上说法均错误
5、以下排序空间复杂度最大的是？（）
A、希尔排序
B、快速排序
C、堆排序
D、归并排序
2、试题答案：B
试题解析：
Prim和Kruskal是求最小生成树的算法，Prim适用于稠密图，Kruskal适用于稀疏图；Dijkstra和Floyd用于求最短路径的算法，Dijkstra求从某顶点到其余各顶点的最短路径（单源最短路径），Floyd求每一对顶点之间的最短路径。综上本题选B。
3、试题答案：D
试题解析：
图的遍历算法：广度优先搜索BFS和深度优先搜索DFS。广度优先搜索BFS类似于树的层次遍历；深度优先搜索DFS类似于树的先序遍历。故本题选D。
4、试题答案：C
试题解析：
线性探测再散列法：设Hash(x)=Hash(y)=i，则x与y发生冲突；根据线性探测再散列，则y查看下一位置i+1，若有Hash(z)=i+1，则z与y发生冲突，但z与y不是同义字；故可能是同义字，可能不是同义字。综上本题选C。
同义字：关键字x、y经过哈希函数映射到同一个地址，则称x和y产生了冲突，即x与y是同义字。
5、试题答案：D
试题解析：
由下表可知，题中各种排序中空间复杂度最大的是归并排序，故本题选D。
