计算机专业基础综合（图）-试卷1(总分：58.00，做题时间：90分钟)一、单项选择题(总题数：18，分数：36.00)1.单项选择题1-40小题。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
（分数：2.00）__________________________________________________________________________________________ 解析：2.在有向图G的拓扑序列中，若顶点v i在顶点v j之前，则下列情形不可能出现的是( )。
（分数：2.00）A.G中有弧 i，v h>B.G中有一条从v i到v j的路径C.G中没有弧 i，v j>D.G中有一条从v j到v i的路径√解析：解析：此题考查的知识点是图的拓扑排序。
根据拓扑排序的定义，若顶点v i与顶点v j有一条弧，则拓扑序列中顶点v i必在顶点v j之前。
若有一条从v j到v i的路径，则顶点v i不可能在顶点v j之前。
所以应选D。
3.以下关于图的说法中正确的是( )。
Ⅰ．一个有向图的邻接表和逆邻接表中的结点个数一定相等Ⅱ．用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关Ⅲ．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的（分数：2.00）A.Ⅰ，Ⅱ√B.Ⅱ，ⅢC.Ⅰ，ⅢD.仅有Ⅱ解析：解析：说法Ⅰ是正确的，邻接表和逆邻接表的区别仅在于出边和入边，边表的结点个数都等于有向图中的边的个数。
说法Ⅱ是正确的，邻接矩阵的空间复杂度为D(n 2 )，与边的个数无关。
说法Ⅲ是错误的，有向图的邻接矩阵不一定是不对称的，例如，有向完全图的邻接矩阵就是对称的。
4.下列关于AOE网的叙述中，不正确的是( )。
（分数：2.00）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成√C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成解析：解析：此题考查的知识点是图的关键路径。
在AOE网中，从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并且不只一条。
关键路径上的活动称为关键活动。
A、C、D的说法都正确。
但任何一个关键活动提前完成，不一定会影响关键路径，所以根据题意应选B。
5.一个二部图的邻接矩阵A是一个( )类型的矩阵。
（分数：2.00）A.rtxn矩阵B.分块对称矩阵√C.上三角矩阵D.下三角矩阵解析：解析：此题考查的知识点是二部图的定义与存储。
二部图定义为：若能将无向图G=的顶点集V划分成两个子集V1和V2(V1∩V2=?)，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。
由于其特点，其存储矩阵必为分块对称的，所以选B。
6.求解最短路径的Floyd算法的时间复杂度为( )。
（分数：2.00）A.O(n)B.O(n+C)C.O(n 2 )D.O(n 3 ) √解析：7.下列4组含C1～C7的结点序列中，( )（分数：2.00）A.Cl，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C3，C6 √解析：解析：考查拓扑排序的算法。
以1开头的拓扑排序过程，如下图所示：以5开头的拓扑排序8.如果具有n个顶点的图是一个环，则它有( )棵生成树。
（分数：2.00）A.n 2B.n √C.n一1D.1解析：解析：因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树，共有n种情况，所以可以有n棵不同的生成树。
9.如下图所示，在下面的5个序列中，符合深度优先遍历的序列有( )个。
①aebfdc ②acfdeb③aedfcb（分数：2.00）A.5B.4C.3D.2 √解析：解析：本题中，符合深度优先遍历顺序的是1和5，其他三个序列均不符合。
10.无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有( )个顶点。
（分数：2.00）A.11B.12C.15D.16 √解析：解析：由于在具有n个顶点e条边的无向图中，有i)=2e，故可求得度为2的顶点数为7个，从而最多有16个顶点。
11.对AOE网络中有关关键路径的叙述中，正确的是( )。
（分数：2.00）A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间√B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间解析：解析：本题考查关键路径的定义。
关键路径：从起点到终点的最长路径长度(路径上各活动持续时间之和)。
关键活动：关键路径上的活动称为关键活动。
12.以下关于图的叙述中，正确的是( )。
（分数：2.00）A.强连通有向图的任何顶点到其他所有顶点都有弧B.图与树的区别在于图的边数大于或等于顶点数C.无向图的连通分量指无向图中的极大连通子图√D.假设有图G={V，{E}，顶点集V"∈V，E"∈E，则V和{E"}构成G的子图解析：解析：强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A错误。
图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。
若E"中的边对应的顶点不是V"中的元素时，则V"和{E"}无法构成图，D错误。
13.假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为( )。
（分数：2.00）A.O(n)B.O(e)C.O(n+e) √D.O(ne)解析：解析：删除与某顶点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。
故总的时间复杂度为O(n+e)。
14.若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是( )。
（分数：2.00）A.11B.10 √C.9D.8解析：解析：n个顶点构成的无向图中，边数≤n(n一1)／2，将e=36代入，有n≥9，现已知无向图是非连通的，则n至少为10。
15.已知有向图G=(V，A)，其中V={a，b，c，d，e}，A={，，，，，}。
对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。
（分数：2.00）A.a，d，c，b，eB.d，a，b，c，eC.a，b，d，c，eD.a，b，c，d，e √解析：解析：选项D中，删去a、b及其对应的出边后，c的入度不为0，因此有边，故不是拓扑序列。
选项A、B、C均为拓扑序列。
解答本类题时，建议读者根据边集合画出草图。
16.用有向无环图描述表达式(A+B)*((A+B)／A)，至少需要顶点的数目为( )。
（分数：2.00）A.5 √B.6C.8D.9解析：解析：此题考查的知识点是有向无环图的定义。
有向无环图是一个无环的有向图，可以用来表示公共子表达式，本题中出现的5个字符作为5个顶点，其中A+B和A可共用，所以至少5个即可，选A。
17.邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点关于图中各个域的说明，不正确的是( )。
（分数：2.00）A.vertex存储的是结点的数值域的内容B.firstedge域指示第一条依附于该顶点的边C.mark指向下一条依附于结点的边√为指向和边相关的各种信息的指针域解析：解析：顶点表由两个域组成，vertex域存储和该顶点相关的信息，firstedge域指示第一条依附于该顶点的边。
边表结点由六个域组成：mark为标记域，用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边;info为指向和边相关的各种信息的指针域。
18.以下关于十字链表的说法中，不正确的是( )。
（分数：2.00）A.十字链表是有向图的另一种链式存储结构B.行指针row为矩阵中的行位置，列指针col为矩阵中的列位置C.数值val为矩阵中的值D.right指针指向矩阵中的行位置，down指针指向矩阵中的列位置_ √解析：解析：right指向右侧的一个非零元素，down指向下侧的一个非零元素。
二、综合应用题(总题数：10，分数：22.00)19.综合应用题41-47小题。
__________________________________________________________________________________________ 解析：20.对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：顶点A到顶点B、C、D、E的最短路径依次是3、18、38、43，按Dijkstra所选顶点过程是B、C、D、E。
支撑树的边集合为{ ，，，}，具体分析如下表所示。
[*])解析：21.对于有向无环图，叙述求拓扑有序序列的步骤。
（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：对有向图，求拓扑序列步骤为：①在有向图中选一个没有前驱(即入度为零)的顶点并输出。
②在图中删除该顶点及所有以它为尾的弧。
③重复①和②步，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
)解析：22.对于以下的图，写出它的4（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：从入度为0的顶点开始，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑序列。
从顶点1开始的可能的拓扑序列为12345678、12354678、13456278、13546278。