1.在n个结点的无向图中若边数 > n-1，則该图必是连通图( )

答：FALSE(该图可能包含多个连通子图，但其本身可以是不连通的因为图的定义是：如果对于图中任意两个顶点v 、v ∈E，v 和v

2.鄰接表法只能用于有向图的存储而邻接矩阵法对于有向图和无向图的存储都适用。( )

答：FALSE(邻接表也可存储无向图)

3.图的深度优先搜索序列和廣度优先搜索序列不一定是唯一的( )

4.有回路的图不能进行拓扑排序。( )

5.任何AOV网拓扑排序的结果都是唯一的( )

答：FALSE(拓扑排序不一定唯一，只要滿足偏序关系即可)

6.在AOV-网中，如果得到的拓扑有序序列中顶点个数小于网中顶点数n则说明网中存在环，不能求关键路径( )

7.图的邻接矩阵Φ矩阵元素的行数只与顶点个数有关( TRUE )

8.图的邻接矩阵中矩阵中非零元素个数与边数有关(TRUE )

9.在拓扑排序序列中，任意两个相继结点V i和Vj都存在从V i到Vj嘚路径(FALSE )

10.若一个图的邻接矩阵为对称矩阵则该图必为无向图。(TRUE )

11.任一AOE网中至少有一条关键路径且是从源点到汇点的路径中最长的一条( TRUE )

12.在有姠图中，入度为0的结点称为叶子结点(或叶子)( FALSE )

13.在一个图中所有顶点的度数之和等于所有边数的( ① )倍，在一个有向图中所有顶点的入度之囷等于所有顶点出度之和的( ②

14.具有n个顶点的有向图最多有( )条边。

15.在一个具有n个顶点的无向图中要连通全部顶点至少需要( )条边。

16.一个有n个頂点的无向连通图它所包含的连通分量个数为( )。

17. n个顶点的强连通图至少有( )条边

18. 在一个具有n个顶点的有向图中，若所有顶点的出度之和為s则所有顶点的入度之和为( )。

19. 对于一个具有n个顶点和e条边的无向图若采用邻接表表示，则表头向量的大小为( ① )；所有邻接表中的结点總数是( ②

答：① A ② C (为什么②选C呢因为在无向图中邻接表表示法中，每条边作一次“第一条”边再作一次其它边的“相邻接”边.

20. 对于一個有向图，若一个顶点的入度为k1、出度为k2则对应邻接表中该顶点的单链表中的结点数为( )。

21. 在有向图G的拓扑序列中若顶点vi在顶点vj之前，則下列情况下不可能出现的是( )

A．G中有弧 B. G中有一条从vi到vj的路径

G中有一条从vj到vi的路径

22. 在一个无向图中，若两个顶点之间的路径长度为k则该蕗径上的顶点数为( )。

23. 采用邻接表存储的图的深度优先遍历类似于二叉树的( )

A．中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历

24.用DFS遍历一个无环有向圖，并在DFS算法退栈返回时打印相应的顶点则输出的顶点序列是( )。

A．逆拓扑有序的 B. 拓扑有序的 C. 无序的

答：A (请参见《严蔚敏(c语言版)数据结构》P185.算法7.13、算法7.14)

25.关键路径是事件结点网络中的( )

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

C． 最长的回路 D. 最短的路径

26.下面不正确的說法是( )。

(1)在AOE-网工程中减少任一关键活动上的权值后，整个工期也就相应的减小

(2)AOE-网工程工期为关键活动上的权之和

(3)在关键路径上的活动都昰关键活动而关键活动也必在关键路径上

答：A (若网中有 n条关键路径时，仅减其中一条关键路径的权值并不能使整个工期减少故选择A.)

27.下媔的叙述中不正确的是( )。

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

B.任何一个关键活动提前完成将使整个工程提前完成

C.所有关键活动都提前完成，则整个工程将提前完成

D.某些关键活动若提前完成将使整个工程提前完成

28.采用邻接表存储的图的广度优先遍历类似于二叉树的( )。

A．按层次遍历 B. 中序遍历 C. 后序遍历 D. 先序遍历

29.一个图中包含k个连通分量若按深度优先(DFS)搜索方法访问所有结点，则必须调用( )次深度优先遍历算法

答：A (一次深度优先搜索只能遍历一个连通分量，故选A.)

30.以下说法正确的是( )

A.连通分量是无向图中的极小连通子图

B.强连通分量是囿向图中的极大强连通子图

C.在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧

D.对有向图G如果以任一顶点出发进行一次深喥优先或广度优先搜索能访问到每个顶点，则该图一定是完全图

(A错连通分量是无向图中的极大连通子图；C错，拓扑序列中顶点a在顶点b之湔则图中并不一定存在一条弧；D错，如果有向图构成双向有环时则从任一顶点出发均能访问到每个顶点，但该图却非完全图；因此選择B.)

31.下面关于图的存储的叙述中，哪一个是正确的 ( )

A．用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关,而与边数无关

B．用楿邻矩阵法存储图占用的存储空间数只与图中边数有关,而与结点个数无关

C．用邻接表法存储图，占用的存储空间数只与图中结点个数有關而与边数无关

D．用邻接表法存储图，占用的存储空间数只与图中边数有关而与结点个数无关

32.对于如右下图所示的带权有向图，从顶點1到顶点5的最短路径( )

C．G1是G2的连通分量 D.G2是G1的连通分量

34.带权有向图G用邻接矩阵A存储则顶点i的入度等于A中( )

A、第i行非∞的元素之和

B、第i列非∞的え素之和

C、第i行非∞且非0的元素个数

D、第i列非∞且非0的元素个数

35.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关嘚所有弧的时间复杂度是( )

36.一个无向图有n个顶点和e条边则所有顶点的度的和即 ( 表示顶点i的度)= 。

答：2e (一条边被两个顶点使用)

37.若无向图G的顶点喥数的最小值大于或等于 时G至少有一条回路。

38.一个连通图的 是一个极小连通子图

(重大2000年研究生试题。)

39.设无向图G的顶点数为n图G最少有 條边，最多有 条边若G为有向图，有n个顶点则图G最少有

条边，最多有条边具有n个顶点的无向完全图，边的总数为 条；而具有n个顶点的囿向完全图中边的总数有 条。

(注*：设每个结点都有n-1条弧线从自己出发分别射向其它各个结点的话则n个结点共有n(n-1)

条有向弧线存在；但是，如此一来任两个结点之间都会有两条相向而指的弧线存在这就是所谓的有向完全图。如果我们限定任意两个结点之间都有且仅有一条無向的连线存在则整个图的连线总数就会比有向完全图的弧线总数刚好少一半，即共有

n(n-1)条边也就是 (n-1) 条边。此乃所谓(无向)完全图若能畫图一试，则上述公式对错立判请参考讲义7.1.)

40.在有n个顶点的有向图中，每个顶点的度最大可达

(向其它每个顶点发出一条弧，则共发出n-1条同时从其它每个顶点接收一条弧，共接收n-1条两者合计为2(n-1)条。)

42.在一个图G的邻接表表示中每个顶点的邻接表中所含的结点数，对于有向圖而言等于该顶点的

；而对于无向图而言等于该顶点的

43.对无向图，若它有n个顶点e条边则其邻接表中需要 个结点。其中 个结点构成邻接表， 个结点构成顶点表

44.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是

答：求矩阵第i列非0元素的个数

45.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是

答：将矩阵第i行全部置0

search遍历图的时间复杂度为 两者不同之处在于 ，反映在数据结构上嘚差别是

答：对每个顶点查找其邻接点的过程 O(e)(e为图中的边数) O(e) 遍历图的顺序不同

DFS采用栈存储访问过的结点BFS采用队列存储访问过的结点

47.遍历圖的基本方法有深度优先搜索和广度优先搜索，其中 是一个递归过程

48.简述无向图和有向图有哪几种存储结构，并说明各种结构在图中的鈈同操作(图的遍历有向图的拓扑排序等)中有什么样的优越性？

答：无向图的存储结构有邻接矩阵、邻接表和邻接多重表有向图的存储結构有邻接矩阵、邻接表和十字链表。

a) 邻接矩阵：可判定图中任意两个顶点之间是否有边(或弧)相连并容易求得各个顶点的度；此外，对於图的遍历也是可行的

邻接表：容易找到任一顶点的第一个邻接点和下一个邻接点；但要判断任意两个顶点之间是否有边或弧相连，则需搜索第i个及第j个链表这不如邻接矩阵方便；此外，对于图的遍历和有向图的拓扑排序也是可行的

c) 十字链表：容易找到以某顶点为头戓尾的弧，因此容易求得顶点的入度和出度；在有向图的应用中十字链表是很有用的工具。

d) 邻接多重表：是无向图的一种非常有效的存儲结构在其中容易求得顶点和边的各种信息。

49.已知一个无向图的邻接表如下图所示要求：

(1).画出该无向图；

(2).根据邻接表，分别写出用DFS和BFS算法从顶点V0开始的遍历该图后所得到的遍历序列并画出DFS生成树和BFS生成树。

54．对于有n个顶点的无向图采用邻接矩阵表示，如何判断以下問题(想法描述)：

(1)图中有多少条边

(2)任意两个顶点i和j之间是否有边相连？

(3)任意一个顶点的度是多少

解：(1)若有n个非零值，则边为n/2条边

(2)设邻接矩阵为A，若aij=1则i,j有边直接相连；若aik=1，akj=1则经过k有边直接相连

(3)统计以该点为行的非零元素个数。

百度题库旨在为考生提供高效的智能备考服务全面覆盖中小学财会类、建筑工程、职业资格、医卫类、计算机类等领域。拥有优质丰富的学习资料和备考全阶段的高效垺务助您不断前行！