考研数据结构与操作系统在线题库每日一练（一十三）

本文提供考研数据结构与操作系统在线题库每日一练，以下为具体内容

2、下列哪个算法适合求稀疏图的最小生成树？（）

A、Prim

B、Kruskal

C、Dijkstra

D、Floyd

3、图的广度优先遍历类似于树的？（）

A、先序遍历

B、中序遍历

C、后序遍历

D、层序遍历

4、以下排序空间复杂度最大的是？（）

A、希尔排序

B、快速排序

C、堆排序

D、归并排序

2、试题答案：B

试题解析：

Prim和Kruskal是求最小生成树的算法，Prim适用于稠密图，Kruskal适用于稀疏图；Dijkstra和Floyd用于求最短路径的算法，Dijkstra求从某顶点到其余各顶点的最短路径（单源最短路径），Floyd求每一对顶点之间的最短路径。综上本题选B。

3、试题答案：D

试题解析：

图的遍历算法：广度优先搜索BFS和深度优先搜索DFS。广度优先搜索BFS类似于树的层次遍历；深度优先搜索DFS类似于树的先序遍历。故本题选D。

4、试题答案：D

试题解析：

由下表可知，题中各种排序中空间复杂度最大的是归并排序，故本题选D。