【免费】考研数据结构第七章-图论必刷题资源-CSDN文库

数据结构

需积分: 0 55 浏览量 2023-04-27 21:24:53 上传评论 1 收藏 1.14MB PDF 举报

资源推荐

资源详情

资源评论

第七章图

⼀、选择题

1．图中有关路径的定义是（）。【北⽅交通⼤学 2001 ⼀、24 （2 分）】

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列

C．由不同边所形成的序列 D．上述定义都不是

2．设⽆向图的顶点个数为 n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n

【清华⼤学 1998 ⼀、5 （2 分）】【⻄安电⼦科技⼤ 1998 ⼀、6 （2 分）】

【北京航空航天⼤学 1999 ⼀、7 （2 分）】

3．⼀个 n 个顶点的连通⽆向图，其边的个数⾄少为（）。【浙江⼤学 1999 四、4 (4 分)】

A．n-1 B．n C．n+1 D．nlogn；

4．要连通具有 n 个顶点的有向图，⾄少需要（）条边。【北京航空航天⼤学 2000 ⼀、6(2 分）】

A．n-l B．n C．n+l D．2n

5．n 个结点的完全有向图含有边的数⽬（）。【中⼭⼤学 1998 ⼆、9 （2 分）】

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）

6．⼀个有 n 个结点的图，最少有（）个连通分量，最多有（）个连通分量。

A．0 B．1 C．n-1 D．n

【北京邮电⼤学 2000 ⼆、5 （20/8 分）】

7．在⼀个⽆向图中，所有顶点的度数之和等于所有边数（）倍，在⼀个有向图中，所有顶点的⼊

度之和等于所有顶点出度之和的（）倍。【哈尔滨⼯业⼤学 2001 ⼆、3 （2 分）】

A．1/2 B．2 C．1 D．4

8．⽤有向⽆环图描述表达式(A+B)*（（A+B）/A），⾄少需要顶点的数⽬为( )。【中⼭⼤学 1999 ⼀、

14】

A．5 B．6 C．8 D．9

9．⽤ DFS 遍历⼀个⽆环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A．逆拓扑有序 B．拓扑有序 C．⽆序的【中科院软件所 1998】

10．下⾯结构中最适于表示稀疏⽆向图的是（），适于表示稀疏有向图的是（）。

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．⼗字链表 E．邻接表

【北京⼯业⼤学 2001 ⼀、3 (2 分)】

11．下列哪⼀种图的邻接矩阵是对称矩阵？（）【北⽅交通⼤学 2001 ⼀、11 （2 分）】

A．有向图 B．⽆向图 C．AOV ⽹ D．AOE ⽹

12．从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条

弧；如果是⽆向图，则共有（③）条边。【中科院软件所 1999 六、2（3 分）】

①．A．9 B．3 C．6 D．1 E．以上答案均不正确

②．A．5 B．4 C．3 D．2 E．以上答案均不正确

③．A．5 B．4 C．3 D．2 E．以上答案均不正确

13．当⼀个有 N 个顶点的图⽤邻接矩阵 A 表示时，顶点 Vi 的度是（）。【南京理⼯⼤学 1998 ⼀、4(2

分）】

A． B． C． D． +

14．⽤相邻矩阵 A 表示图，判定任意两个顶点 Vi 和 Vj 之间是否有⻓度为 m 的路径相连，则只要检

查（）的第 i ⾏第 j 列的元素是否为零即可。【武汉⼤学 2000 ⼆、7】

A．mA B．A C．A

D．Am-1

15. 下列说法不正确的是（）。【⻘岛⼤学 2002 ⼆、9 （2 分）】

A．图的遍历是从给定的源点出发每⼀个顶点仅被访问⼀次 C．图的深度遍历不适⽤于有向图

B．遍历的基本算法有两种：深度遍历和⼴度遍历 D．图的深度遍历是⼀个递归过程

16．⽆向图 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

17. 设图如右所示，在下⾯的 5 个序列中，符合深度优先遍历的序列有多少？（）

【南京理⼯⼤学 2000 ⼀、20 （1.5 分）】

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．5 个 B．4 个 C．3 个 D．2 个

第 17 题图第 18 题图

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

⽽进⾏⼴度优先遍历得到的顶点序列是（ ② ）。【中科院软件所 1999 六、2-（1）（2 分）】

①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确

②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确

19．下⾯哪⼀⽅法可以判断出⼀个有向图是否有环（回路）：【东北⼤学 2000 4、2（4 分）】

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

20. 在图采⽤邻接表存储时，求最⼩⽣成树的 Prim 算法的时间复杂度为( )。

A. O(n) B. O(n+e) C. O(n

) D. O(n

)

【合肥⼯业⼤学 2001 ⼀、2 （2 分）】

21. 下⾯是求连通⽹的最⼩⽣成树的 prim 算法：集合 VT，ET 分别放顶点和边，初始为（ 1 ），下⾯

步骤重复 n-1 次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。【南京理⼯⼤学 1997 ⼀、11_14 （8 分）】

（1）．A．VT，ET 为空 B．VT 为所有顶点，ET 为空

C．VT 为⽹中任意⼀点，ET 为空 D．VT 为空，ET 为⽹中所有边

（2）．A. 选 i 属于 VT，j 不属于 VT，且（i，j）上的权最⼩

B．选 i 属于 VT，j 不属于 VT，且（i，j）上的权最⼤

C．选 i 不属于 VT，j 不属于 VT，且（i，j）上的权最⼩

D．选 i 不属于 VT，j 不属于 VT，且（i，j）上的权最⼤

（3）．A．顶点 i 加⼊ VT，（i,j）加⼊ ET B. 顶点 j 加⼊ VT，（i,j）加⼊ ET

C. 顶点 j 加⼊ VT，（i,j）从 ET 中删去 D．顶点 i,j 加⼊ VT，（i,j）加⼊ ET

（4）．A．ET 中为最⼩⽣成树 B．不在 ET 中的边构成最⼩⽣成树

C．ET 中有 n-1 条边时为⽣成树，否则⽆解 D．ET 中⽆回路时，为⽣成树，否则⽆解

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

是在实际应⽤中⽆意义；

(2). 利⽤ Dijkstra 求每⼀对不同顶点之间的最短路径的算法时间是 O(n

) ；（图⽤邻接矩阵表示）

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

上⾯不正确的是（）。【南京理⼯⼤学 2000 ⼀、21 （1.5 分）】

A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)

23．当各边上的权值( )时，BFS 算法可⽤来解决单源最短路径问题。【中科院计算所 2000 ⼀、3 (2

分）】

A．均相等 B．均互不相等 C．不⼀定相等

24. 求解最短路径的 Floyd 算法的时间复杂度为( )。【合肥⼯业⼤学 1999 ⼀、2 （2 分）】

A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n）

25．已知有向图 G=(V,E)，其中 V={V

}，

E={<V

>,<V

>},G 的拓扑序列是

（）。

A．V

B．V

C．V

D．V

【北京航空航天⼤学 2000 ⼀、7 （2 分）】

26．若⼀个有向图的邻接距阵中,主对⻆线以下的元素均为零,则该图的拓扑有序序列（）。

A．存在 B．不存在【中科院计算所 1998 ⼆、6 (2 分）】【中国科技⼤学 1998 ⼆、6（2 分）】

27．⼀个有向⽆环图的拓扑排序序列（）是唯⼀的。【北京邮电⼤学 2001 ⼀、3 （2 分）】

A．⼀定 B．不⼀定

28. 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（）。

A．G 中有弧<Vi，Vj> B．G 中有⼀条从 Vi 到 Vj 的路径

C．G 中没有弧<Vi,Vj> D．G 中有⼀条从 Vj 到 Vi 的路径

【南京理⼯⼤学 2000 ⼀、9 （1.5 分）】

29. 在⽤邻接表表示图时，拓扑排序算法时间复杂度为( )。

A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n)

【合肥⼯业⼤学 2000 ⼀、2 （2 分）】【南京理⼯⼤学 2001 ⼀、9 （1.5 分）】

【⻘岛⼤学 2002 ⼆、3 （2 分）】

30. 关键路径是事件结点⽹络中（）。【⻄安电⼦科技⼤学 2001 应⽤⼀、4 （2 分）】

A．从源点到汇点的最⻓路径 B．从源点到汇点的最短路径

C．最⻓回路 D．最短回路

31. 下⾯关于求关键路径的说法不正确的是（）。【南京理⼯⼤学 1998 ⼀、12 （2 分）】

A．求关键路径是以拓扑排序为基础的

B．⼀个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C．⼀个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D．关键活动⼀定位于关键路径上

32．下列关于 AOE ⽹的叙述中，不正确的是（）。

A．关键活动不按期完成就会影响整个⼯程的完成时间

B．任何⼀个关键活动提前完成，那么整个⼯程将会提前完成

C．所有的关键活动提前完成，那么整个⼯程将会提前完成

D．某些关键活动提前完成，那么整个⼯程将会提前完成

【北⽅交通⼤学 1999 ⼀、7 （3 分）】【北京⼯业⼤学 1999 ⼀、1 (2 分)】

⼆、判断题

1.树中的结点和图中的顶点就是指数据结构中的数据元素。（）【⻘岛⼤学 2001 四、1 （1 分）】

2．在 n 个结点的⽆向图中，若边数⼤于 n-1,则该图必是连通图。（）【中科院软件所 1997 ⼀、4(1

分）】

3．对有 n 个顶点的⽆向图，其边数 e 与各顶点度数间满⾜下列等式 e= 。（）

【南京航空航天⼤学 1996 六、4 （1 分）】

4. 有 e 条边的⽆向图，在邻接表中有 e 个结点。（）【南京理⼯⼤学 1998 ⼆、5 （2 分）】

5. 有向图中顶点 V 的度等于其邻接矩阵中第 V ⾏中的 1 的个数。（）【合肥⼯业⼤学 2001 ⼆、7(1

分）】

6．强连通图的各顶点间均可达。（）【北京邮电⼤学 2000 ⼀、3 （1 分）】

7．强连通分量是⽆向图的极⼤强连通⼦图。（）【北京邮电⼤学 2002 ⼀、7 （1 分）】

8．连通分量指的是有向图中的极⼤连通⼦图。（）【燕⼭⼤学 1998 ⼆、4 （2 分）】

9．邻接多重表是⽆向图和有向图的链式存储结构。（）【南京航空航天⼤学 1995 五、5 （1 分）】

10. ⼗字链表是⽆向图的⼀种存储结构。（）【⻘岛⼤学 2001 四、7 （1 分）】

11. ⽆向图的邻接矩阵可⽤⼀维数组存储。（）【⻘岛⼤学 2000 四、5 （1 分）】

12．⽤邻接矩阵法存储⼀个图所需的存储单元数⽬与图的边数有关。（）

【东南⼤学 2001 ⼀、4 （1 分）】【中⼭⼤学 1994 ⼀、3 （2 分）】

13．有 n 个顶点的⽆向图, 采⽤邻接矩阵表示, 图中的边数等于邻接矩阵中⾮零元素之和的⼀半。

（）

【北京邮电⼤学 1998 ⼀、5 （2 分）】

14. 有向图的邻接矩阵是对称的。（）【⻘岛⼤学 2001 四、6 （1 分）】

15．⽆向图的邻接矩阵⼀定是对称矩阵，有向图的邻接矩阵⼀定是⾮对称矩阵。（）

【东南⼤学 2001 ⼀、3 （1 分）】【哈尔滨⼯业⼤学 1999 三、4】

16. 邻接矩阵适⽤于有向图和⽆向图的存储，但不能存储带权的有向图和⽆向图，⽽只能使⽤邻接表存

储形式来存储它。（）【上海海运学院 1995 ⼀、9（1 分） 1997 ⼀、8（1 分） 1998 ⼀、9（1 分）】

17. ⽤邻接矩阵存储⼀个图时，在不考虑压缩存储的情况下，所占⽤的存储空间⼤⼩与图中结点个数有

关，⽽与图的边数⽆关。（）【上海海运学院 1996 ⼀、8 （1 分） 1999 ⼀、9 （1 分）】

18．⼀个有向图的邻接表和逆邻接表中结点的个数可能不等。（）【上海交通⼤学 1998 ⼀、12】

19．需要借助于⼀个队列来实现 DFS 算法。（）【南京航空航天⼤学 1996 六、8 （1 分）】

20. ⼴度遍历⽣成树描述了从起点到各顶点的最短路径。（）【合肥⼯业⼤学 2001 ⼆、8 （1 分）】

21．任何⽆向图都存在⽣成树。（）【北京邮电⼤学 2000 ⼀、1 （1 分）】

22. 不同的求最⼩⽣成树的⽅法最后得到的⽣成树是相同的.（）【南京理⼯⼤学 1998 ⼆、3 （2

分）】

23．带权⽆向图的最⼩⽣成树必是唯⼀的。（）【南京航空航天⼤学 1996 六、7 （1 分）】

24. 最⼩代价⽣成树是唯⼀的。（）【⼭东⼤学 2001 ⼀、5 （1 分）】

25．⼀个⽹（带权图）都有唯⼀的最⼩⽣成树。（）【⼤连海事⼤学 2001 ⼀、14 （1 分）】

26．连通图上各边权值均不相同，则该图的最⼩⽣成树是唯⼀的。（）【哈尔滨⼯业⼤学 1999 三、

3】

27．带权的连通⽆向图的最⼩（代价）⽣成树（⽀撑树）是唯⼀的。（）【中⼭⼤学 1994 ⼀、10（2

分）】

28. 最⼩⽣成树的 KRUSKAL 算法是⼀种贪⼼法（GREEDY）。（）【华南理⼯⼤学 2002 ⼀、6（1

分）】

29. 求最⼩⽣成树的普⾥姆(Prim)算法中边上的权可正可负。（）【南京理⼯⼤学 1998 ⼆、2 （2

分）】

30．带权的连通⽆向图的最⼩代价⽣成树是唯⼀的。（）【东南⼤学 2001 ⼀、5（1 分）】

31. 最⼩⽣成树问题是构造连通⽹的最⼩代价⽣成树。（）【⻘岛⼤学 2001 四、10（1 分）】

32. 在图 G 的最⼩⽣成树 G1 中，可能会有某条边的权值超过未选边的权值。（）

【合肥⼯业⼤学 2000 ⼆、7（1 分）】

33. 在⽤ Floyd 算法求解各顶点的最短路径时，每个表示两点间路径的 path

k-1

[I,J]⼀定是 path

[I,J]的

⼦集(k=1,2,3,…,n)。（）【合肥⼯业⼤学 2000 ⼆、6 （1 分）】

34．拓扑排序算法把⼀个⽆向图中的顶点排成⼀个有序序列。（）【南京航空航天⼤学 1995 五、8（1

分）】

35．拓扑排序算法仅能适⽤于有向⽆环图。（）【南京航空航天⼤学 1997 ⼀、7 （1 分）】

36. ⽆环有向图才能进⾏拓扑排序。（）【⻘岛⼤学 2002 ⼀、7 （1 分）2001 ⼀、8 （1 分）】

37. 有环图也能进⾏拓扑排序。（）【⻘岛⼤学 2000 四、6 （1 分）】

38．拓扑排序的有向图中，最多存在⼀条环路。（）【⼤连海事⼤学 2001 ⼀、6（1 分）】

39．任何有向图的结点都可以排成拓扑排序，⽽且拓扑序列不唯⼀。（）【上海交通⼤学 1998 ⼀、

13】

40. 既使有向⽆环图的拓扑序列唯⼀，也不能唯⼀确定该图。（）【合肥⼯业⼤学 2001 ⼆、6（1

分）】

41．若⼀个有向图的邻接矩阵对⻆线以下元素均为零，则该图的拓扑有序序列必定存在。（）

【中科院软件所 1997 ⼀、5 （1 分）】

42．AOV ⽹的含义是以边表示活动的⽹。（）【南京航空航天⼤学 1995 五、7 （1 分）】

43．对⼀个 AOV ⽹，从源点到终点的路径最⻓的路径称作关键路径。【南京航空航天⼤学 1995 五、9(1

分）】

44. 关键路径是 AOE ⽹中从源点到终点的最⻓路径。（）【⻘岛⼤学 2000 四、10（1 分）】

45. AOE ⽹⼀定是有向⽆环图。（）【⻘岛⼤学 2001 ⼀、9 （1 分）】

46. 在表示某⼯程的 AOE ⽹中，加速其关键路径上的任意关键活动均可缩短整个⼯程的完成时间。

（）

【⻓沙铁道学院 1997 ⼀、2 (1 分)】

47．在 AOE 图中，关键路径上某个活动的时间缩短，整个⼯程的时间也就必定缩短。（）

【⼤连海事⼤学 2001 ⼀、15 （1 分）】

48．在 AOE 图中，关键路径上活动的时间延⻓多少，整个⼯程的时间也就随之延⻓多少。（）

【⼤连海事⼤学 2001 ⼀、16 （1 分）】

49．当改变⽹上某⼀关键路径上任⼀关键活动后，必将产⽣不同的关键路径。【上海交通⼤学 1998 ⼀、

14】

剩余25页未读，继续阅读

评论收藏

内容反馈

Python知识大全

粉丝: 23
资源: 14

考研数据结构第七章-图论必刷题

武汉理工2007考研试题------数据结构

【数据结构课件】第七章 图论

数据结构与算法考研试题：第七章 图.docx

数据结构与算法考研试题：第七章 图.pdf

数据结构与算法考研试题：第七章 图 (2).docx

数据结构考研1800典型试题+答案 共11章

数据结构考研1800典型试题共11章 第一章

数据结构-考研书目 数据结构-考研书目 数据结构-考研书目

数据结构与算法考研试题：第七章 图 (2).pdf

数据结构考研讲义 第七章 排序.pdf

南航计算机考研真题之数据结构95-98

考研杭电计算机数据结构真题答案详解-有解释

数据结构考研资料大汇总 全集 考研必备

浙大数据结构考研试题94-02

数据结构考研统考三年真题集

南师大地信考研数据结构真题03-11年

数据结构考研辅导教程-第5章 殷人昆编著

苏州大学2006计算机考研试题-----数据结构与操作系统

数据结构试题分章节考研题及答案.rar

数据结构1994-2002年考研试题

王道考研数据结构第二讲-线性表

苏州大学2005计算机考研试题-----数据结构与操作系统

《点燃我温暖你》中李峋的同款爱心代码

122版本Chrome最新驱动-122.0.6261.58

第十五届蓝桥杯大赛软件赛省赛-PythonB组题目

Python入门基础教程全套.ppt

最新资源

【数据结构课件】第七章图论

数据结构与算法考研试题：第七章图.docx

数据结构与算法考研试题：第七章图.pdf

数据结构与算法考研试题：第七章图 (2).docx

数据结构考研1800典型试题+答案共11章

数据结构考研1800典型试题共11章第一章

数据结构-考研书目数据结构-考研书目数据结构-考研书目

数据结构与算法考研试题：第七章图 (2).pdf

数据结构考研讲义第七章排序.pdf

数据结构考研资料大汇总全集考研必备

数据结构考研辅导教程-第5章殷人昆编著