计算机专业基础综合数据结构(图)历年真题试卷汇编9

2024年3月11日发(作者：奥迪rs5双门轿跑)

计算机专业基础综合数据结构（图）历年真题试卷汇编9

(总分：62.00，做题时间：90分钟)

一、 单项选择题(总题数：20，分数：42.00)

1.若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为( )【。中国科学技术大学1997一、3(1分)2004】

A.对称矩阵

B.稀疏矩阵

C.三角矩阵

D.一般矩阵 √

若是下三角矩阵，说明编号大的顶点是弧尾，编号小的顶点是弧头，不会出现编号小的顶点指向编号大的

顶点的现象。上三角矩阵恰恰相反。这两种情况说明该有向图可以拓扑排序，但是具有拓扑排序序列的有

向图的邻接矩阵不一定是三角矩阵。有向无环图具有拓扑排序序列，其邻接矩阵没有明显特征。

2.采用邻接表存储的图的深度优先遍历算法类似于树的( )，而其广度优先遍历算法类似于树的( )。【北

京交通大学2007】

A.中序遍

B.先序遍历 √

C.后序遍

D.按层次遍历 √

3.执行( )操作时，需要使用队列作辅助存储空间。【华中科技大学2006一、1(2分)】

A.查找哈希(Hash)表

B.广度优先搜索图 √

C.先序(根)遍历二叉树

D.深度优先搜索图

4.图的BFS生成树的树高比：DFS生成树的树高( )。【青岛大学2004一、8(3分)】

A.小或相等 √

B.小

C.大或相等

D.大

5.无向图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))，对该图进行深度优先遍历，得到的顶点序列正确的是( )。【南京理工大学2001一、14(1．5分)】

A.a，b，e，c，d,f

B.a，c，f,e ，b，d

C.a，e，b，c,f,d

D.a，e，d,f, c，b √

6.设图如下所示，在下面的5个序列中，符合深度优先遍历的序列有多少? ( )。【南京理工大学2000一、

20(1．5分)】

A.5个

B.4个

C.3个

D.2个 √

第一个和第四个序列符合深度优先遍历。

下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(①)，而进行

广度优先遍历得到的顶点序列是(②)。【中科院软件所1999六、2(1)(2分)】

①

A.1354267

（分数：4.00）

a e b d f c ;a cf d e b; a e df c b; a efd c b; a efd b c

B.1347652

C.1534276 √

D.1247653

E.以上答案均不正确

②

A.1 534267

B.1 726453

C.1 354276 √

D.1 247653

E.以上答案均不正确

7.下面哪一方法可以判断出一个有向图是否有环(回路)?( )【东北大学2000 4．2(4分)】

A.深度优先遍历 √

B.拓扑排序 √

C.求最短路径

D.求关键路径

8.判断有向图是否有回路，除了可以用拓扑排序外，还可以用( )。【南京理工大学2004一、7(1分)】

A.求关键路径的方法

B.广度优先遍历算法

C.求最短路径的算法

D.深度优先遍历算法 √

9.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。【合肥工业大学2001一、2(2

分)】

A.O(n)

B.O(n+e) √

C.O(n )

D.O(n )

10.在求边稠密的图的最小代价生成树时，采用( )算法较合适。【上海交通大学2005四、7(2分)】

A.普里姆(Prim) √

B.克鲁斯卡尔(Kruskal)

C.迪杰斯特拉(Dijkstra)

D.其他

11.在具有n个顶点的图G中，若最小生成树不唯一，则( )。【电子科技大学2008一、2(1分)】

A.G的边数一定大于n-1 √

B.G的权值最小的边一定有多条

C.G的最小生成树的代价不一定相等

D.上述选项都不对

生成树有n个顶点和n—1条边。最小生成树是权值之和最小的那棵生成树。若最小生成树不唯一，一定是

有权值相等的边，但未必是权值最小的边相等。最小生成树的代价一定相等。当然，G的边数一定大于n

—1，否则，就只有一棵生成树了。

12.(1)求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实

际应用中无意义； (2)利用Dijkztra求每一对不同顶点之间的最短路径的算法时间是O(n )(图用邻接矩

阵表示)； (3)Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正

确的是( )。【南京理工大学2000一、21(1．5分)】

A.(1)，(2)，(3)

B.(1)

C.(1)，(3) √

D.(2)，(3)

13.当各边上的权值( )时，BFS算法可用来解决单源最短路径问题。【中科院计算所2000一、3(2分)】

A.均相等 √

3

2

2