文华学院数据结构模拟试卷(数据结构邓文华答案)

导语：华文慕课-数据结构图题库

1、

解析：

根据拓扑排序的定义，顶点1必须在顶点3前，顶点1、顶点2和顶点3必须在顶点4前，故排列可以为1234、1324、2134

答案： 1234 1324 2134

扩充例子：

2、无向图G=(V, E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}，对该图进行深度优先遍历（优先访问编号小的结点），得到的顶点序列为？

A、abedfc

B、aebdfc

解析：

根据深度优先的算法，先访问a，再访问a的邻接顶点b，再访问b的邻接顶点e，访问e的邻接顶点d，访问d的邻接顶点f（注意是无向图），访问f的邻接顶点c，不再有没访问的顶点，结束。

3、下列关于最短路算法的说法正确的有：

A、当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。

解析：即使是只有负权边，也会导致以前已经被选出来更新其它结点最短路值的结点的最短路值被更新，造成错误。

B、当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。

解析：可以执行多次Dijkstra算法实现这一要求。

C、当图中存在负权回路时，Dijkstra算法也一定能求出源点到所有点的最短路。

解析：Dijkstra算法无法处理图中存在任何负权边的情况。

D、Dijkstra算法不能用于每对顶点间最短路计算。

解析：可以执行多次Dijkstra算法实现这一要求。

4、请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b (a < b)之间的边编号为ab，例如图中权值为1的边编号为02。

解析

Kruskal算法优先选择权值小的边，先挑选权值为1的边02，再选择权值为2的边35，再选择权值为3的边14，再选择权值为4的边25，再选择权值为5的边，只有选择12才能连接两个不同的连通分支

​

答案： 02 35 14 25 12

5、题图为一无向图,分别写出从顶点1出发,按深度优先搜索遍历算法得到的顶点序列,和按广度优先搜索遍历算法得到的顶点序列

解析

根据深度优先定义，先访问1，依次是2、3、4、5、6，注意是无向图。广度优先是一层一层访问，即123564，答案为123456 123564

答案： 123456 123564

本文内容由小开整理编辑！