计算机专业基础综合图模拟试卷4_真题-无答案

计算机专业基础综合（图）模拟试卷4

(总分50,考试时间90分钟)

单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。 1. 在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是( )。 A. G中有弧＜vi，vj＞

B. G中有一条从vi到vj的路径 C. G中没有弧＜vi，vj＞

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

2. 以下关于图的说法中正确的是( )。 I．一个有向图的邻接表和逆邻接表中的结点个数一定相等 Ⅱ．用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关 Ⅲ．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的

A. I，Ⅱ B. Ⅱ，Ⅲ C. I，Ⅲ D. 仅有Ⅱ

3. 下列关于．AOE网的叙述中，不正确的是( )。 A. 关键活动不按期完成就会影响整个工程的完成时间

B. 任何一个关键活动提前完成，那么整个工程将会提前完成 C. 所有的关键活动提前完成，那么整个工程将会提前完成 D. 某些关键活动提前完成，那么整个工程将会提前完成 4. 一个二部图的邻接矩阵A是一个( )类型的矩阵。 A. n×n矩阵 B. 分块对称矩阵 C. 上三角矩阵 D. 下三角矩阵

5. 求解最短路径的Floyd算法的时间复杂度为( )。 A. O(n) B. O(n+c) C. O(n2) D. O(n3)

6. 下列4组含C1—C7的结点序列中，( )是下图所示的有向图的拓扑序列。

A. C1，C2，C6，C7，C5，C4，C3 B. C1，C2，C6，C3，C4，C5，C7 C. C1，C4，C2，C3，C5，C6，C7 D. C5，C7，C4，C1，C2，C3，C6

7. 如果具有n个顶点的图是一个环，则它有( )棵生成树。 A. n2 B. n C. n一1 D. 1

8. 如下图所示，在下面的5个序列中，符合深度优先遍历的序列有( )个。①aebfdc ②acfdeb③aedfcb④aefdbc ⑤aecfdb

A. 5 B. 4 C. 3 D. 2

9. 无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有( )个顶点。 A. 11 B. 12 C. 15 D. 16

10. 对AOE网络中有关关键路径的叙述中，正确的是( )。

A. 从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间

B. 从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间

C. 从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间

D. 从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间

11. 以下关于图的叙述中，正确的是( )。

A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 图与树的区别在于图的边数大于或等于顶点数 C. 无向图的连通分量指无向图中的极大连通子图

D. 假设有图G={V，{E}}，顶点集V’∈V，E’∈E，则V’和{E’}构成G的子图

12. 假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。 A. O(n) B. O(e) C. O(n+e) D. O(ne)

13. 若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是( )。 A. 11 B. 10 C. 9 D. 8

14. 已矢口有向图G=(V，A)，其中V={a，b，c，d，e}，A={，，，，，}。对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。 A. a，d，c，b，e B. d，a，b，c，e C. a，b，d，c，e D. a，b，c，d，e

15. 用有向无环图描述表达式(A+B)*((A+B)／A)，至少需要顶点的数目为( )。 A. 5 B. 6 C. 8 D. 9

16. 邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：关于图中各个域的说明，不正确的是( )。

A. vettex存储的是结点的数值域的内容 B. firstedge域指示第一条依附于该顶点的边 C. mark指向下一条依附于结点的边

D. info为指向和边相关的各种信息的指针域

17. 以下关于十字链表的说法中，不正确的是( )。 A. 十字链表是有向图的另一种链式存储结构

B. 行指针row为矩阵中的行位置，列指针col为矩阵中的列位置 C. 数值val为矩阵中的值

D. right指针指向矩阵中的行位置，down指针指向矩阵中的列位置

综合应用题41-47小题。

1. 对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。

2. (1)对于有向无环图，叙述求拓扑有序序列的步骤。 (2)对于以下的图，写出它的4个不同的拓扑有序序列。

3. 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)

4. 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)

5. 已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则打印出该路径上的顶点。

6. “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)

7. 设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为： MAx{从w到v的最短距离|w属于V(G)} 如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。

8. 对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减1，并对其未访问的、入度为0的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2)定义在算法中使用的全局辅助数组。 (3)写出在遍历图的同时进行拓扑排序的算法。