1、计算机学科专业基础综合数据结构-6 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：21，分数：64.00)在无向图中定义顶点的度为与它相关联的_的数目，所有顶点的度数之和等于所有边数的_。（分数：4.00）A.顶点B边C权D.权值A.3 倍B.2 倍C.1 倍D.1/2图的简单路径是指_不重复的路径。一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵中共有_个零元素，该邻接矩阵是一个_。而用邻接矩阵存储有向图时某一个顶点 i 的入度等于该矩阵的_。（分数：8.00）A.权值B.顶点C边D.边与顶点均AeB.2eC.n2-eD.n2-2eA.上三角矩阵B.
2、稀疏矩阵C.对角矩阵D.对称矩阵A.第 i 行中值为 1 的元素个数B.所有值为 1 的元素总是C.第 i 行及第 i 列中值为 1 的元素总个数D.第 i 列中值为 1 的元素个数图的深度优先搜索类似于树的_次序遍历，图的广度优先搜索类似于树的_次序遍历。（分数：4.00）A.先根B.中根C.后根D.层次A.先根B.中根C.后根D.层次一个连通图的生成树是包含图中所有顶点的一个_子图。n(n1)个顶点的强连通图中至少含有_条有向边。（分数：4.00）A.极小B.连通C.极小连通D.无环A.n-1BnC.n(n-1)/2D.n(n-1)1.在一个带权连通图 G 中，权值最小的边一定包含在 G
3、的_生成树中。（分数：2.00）A.最小B.任何C.广度优先D.深度优先在用 Dijkstra 算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是_。对于如下图所示的带权有向图，从顶点 1 到顶点 5 的最短路径为_。 （分数：4.00）A.非零B.非整C.非负D.非正A.1，4，5B.1，2，3，5C.1，4，3，5D.1，2，4，3，5设 AOV 网有 n 个顶点和 e 条边，如果采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为_；如果采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为_。（分数：4.00）A.O(nlog2e)B.O(n+e)C.O(n
4、e)D.O(n2)A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)2.在 AOE 网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为_，如果加速这样的关键路径就能使整个工程提前完成。（分数：2.00）A汇B源C桥D潭3.在下列有关图的存储结构的说法中错误的是_。（分数：2.00）A.用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关B.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用C.邻接矩阵只适用于稠密图(边数接近于顶点树的平方)，邻接表适用于稀疏图(边数远小于顶点数的平方)D.存储无向图的邻接矩阵是对称的，
5、因此只要存储邻接矩阵的下(上)三角部分就可以了在一个有向图的邻接矩阵表示中，删除一条边v i ，v j 需要耗费的时间是_，要计算某个顶点的出度所耗费的时间是_。与邻接矩阵相比，邻接表更适合于存储_图。（分数：6.00）A.极小B.连通C.极小连通D.无环A.n-1BnC.n(n-1)/2D.n(n-1)A.n-1BnC.n(n-1)/2D.n(n-1)对应具有 e 条边的无向图，它的邻接表中有_个边结点。一个有 n 个顶点和 n 条边的无向图一定是_的。（分数：4.00）A.e-1BeC.2(e-1)D.2eA.重连通的B.不连通的C.无环的D.有环的4.若一个具有 N 个顶点、K 条边的无
6、向图是一个森林(NK)，则该森林必有_棵树。（分数：2.00）AKBNC.N-KD.15.Dijkstra 算法是按_方法求出图中从某顶点到其余顶点最短路径的。（分数：2.00）A.按长度递减的顺序求出图的某顶点到其余顶点的最短路径B.按长度递增的顺序求出图的某顶点到其余顶点的最短路径C.通过深度优先遍历求出图中从某顶点到其余顶点的所有路径D.通过广度优先遍历求出图的某顶点到其余顶点的最短路径6.使用 DFS 算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是_。（分数：2.00）A.逆拓扑有序B.拓扑有序C.无序的D.都不是7.当各边上的权值_时，BFS 算法可用
7、来解决单源最短路径问题。（分数：2.00）A.都相等B.都互不相等C.不一定相等D.都大于 08.设有一个有向图 G=(V，E)，其中 V=v 1 ，v 2 ，v 3 ，v 4 ，v 5 ，v 6 E=v 1 ，v 2 ，v 2 ，v 3 ，v 3 ，v 4 ，v 5 ，v 2 ，v 5 ，v 6 ，v 6 ，v 4 不属于该图的拓扑有序序列是_。（分数：2.00）A.v1，v5，v2，v3，v6，v4B.v5，v6，v1，v2，v3，v4C.v1，v2，v3，v4，v5，v6D.v5，v1，v6，v4，v2，v39.在下列有关关键路径的说法中错误的是_。（分数：2.00）A.在 AOE 网络
8、中可能存在多条关键路径B.关键活动不按期完成就会影响整个工程的完成时间C.任何一个关键活动提前完成，那么整个工程将会提前完成D.所有的关键活动都提前完成，那么整个工程将会提前完成10.下列哪一种图的邻接矩阵是对称矩阵?（分数：2.00）A.有向图B.无向图C.AOV 网D.AOE 网11.判断以下叙述正确的是_。 对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图 连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点 图的深度优先搜索中一般要采用栈来暂存访问过的顶点（分数：2.00）A.，B.，C.，D.，12.判断有向图是否存在回路，除了可以
9、利用拓扑排序方法外，还可以利用的是_。（分数：2.00）A.求关键路径的方法B.求最短路径的 Dijkstra 方法C.深度优先遍历算法D.广度优先遍历算法13.下列 4 组含 C1C7 的结点序列中，_是下图所示的有向图的拓扑序列。 （分数：2.00）A.C1，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二、综合应用题(总题数：3，分数：36.00)对于下图所示的 AOE 网络： （分数：18.00）(1).这个工程最终可能在什么时间结束?（分数：9.00）_(2).确定
10、哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。（分数：9.00）_14.计算连通网的最小生成树 Dijkstra 算法可简述如下：将连通网所有的边以方便的次序逐条加入到初始为空的生成树的边集合 T 中。每次选择并加入一条边时，需要判断它是否会与先前加入 T 中的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。如果以邻接矩阵作为连通网的存储结构(仅适用矩阵的上三角部分)，并在邻接矩阵的下三角部分记录最小生成树的边信息。试以下图所示的图 G 为例，画出构造出的最小生成树及其邻接矩阵，并列出每次选择的边和可能去掉的边。 （分数：9.00）_15.
11、下面是求无向连通图最小生成树的一种算法： /设图中总顶点数为 n，总边数为 m 将图中所有的边按其权值从大到小排序为(e 1 ，e 2 ，e 3 ，e m ) i=1; while(m=n) 从图中删去 e i ；(m=m-1) 若图不再连通，则恢复 e i ；(m=m+1) i=i+1; 试问这个算法是否正确，并说明原因。 （分数：9.00）_计算机学科专业基础综合数据结构-6 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：21，分数：64.00)在无向图中定义顶点的度为与它相关联的_的数目，所有顶点的度数之和等于所有边数的_。（分数：4.00）A.顶点B边 C
12、权D.权值解析：A.3 倍B.2 倍 C.1 倍D.1/2解析：解析 根据定义，一个顶点的度为与该顶点相关联的边的数目。对应无向图，顶点 v i 到顶点 v j 的边与顶点 v j 到顶点 v i 的边是同一条边(不考虑重边)，计算顶点度数之和时每条边被统计了两次，无向图所有顶点的度数之和为边数的 2 倍。图的简单路径是指_不重复的路径。一个含有 n 个顶点和 e 条边的简单无向图，在其邻接矩阵中共有_个零元素，该邻接矩阵是一个_。而用邻接矩阵存储有向图时某一个顶点 i 的入度等于该矩阵的_。（分数：8.00）A.权值B.顶点 C边D.边与顶点均解析：AeB.2eC.n2-eD.n2-2e 解
13、析：A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵 解析：A.第 i 行中值为 1 的元素个数B.所有值为 1 的元素总是C.第 i 行及第 i 列中值为 1 的元素总个数D.第 i 列中值为 1 的元素个数 解析：解析 根据定义，图中顶点之间的路径是指顶点之间的一个顶点序列，而简单路径是顶点不重复的路径。如果用邻接矩阵存储有 n 个顶点和 e 条边的无向图，则矩阵中有 n 2 个矩阵元素，2e 个是 1(因为无向的邻接矩阵是对称的)，n 2 -2e 个 0。对于有向图来说，顶点的度要区分出度和入度，顶点的入度是指进入该顶点的有向边的条数，所以统计第 i 列的 1 的个数，就能得到顶点 i
14、 的入度。图的深度优先搜索类似于树的_次序遍历，图的广度优先搜索类似于树的_次序遍历。（分数：4.00）A.先根 B.中根C.后根D.层次解析：A.先根B.中根C.后根D.层次 解析：解析 图的深度优先搜索类似于树的先根次序遍历，都是先访问结点，再递归向外层结点遍历，都采用回溯算法。图的广度优先搜索类似于树的层次次序遍历，都是一层一层向外层扩展遍历，都需要采用队列来辅助算法的实现。一个连通图的生成树是包含图中所有顶点的一个_子图。n(n1)个顶点的强连通图中至少含有_条有向边。（分数：4.00）A.极小B.连通C.极小连通 D.无环解析：A.n-1 BnC.n(n-1)/2D.n(n-1)解析
15、：解析 一个连通图的生成树是包含图中所有顶点的一个极小连通子图，用 n-1 条边连通 n 个顶点。n(n1)个顶点的强连通图中至少含有 n 条有向边。如果这 n 条边形成一个有向环，就能强连通。1.在一个带权连通图 G 中，权值最小的边一定包含在 G 的_生成树中。（分数：2.00）A.最小 B.任何C.广度优先D.深度优先解析：解析 求解最小生成树的原则是要选择权值最小的 n-1 条边连通 n 个顶点，并要求选出的边不能构成回路。权值最小的边是第一个选择的边，它应在最小生成树的边集合中。在用 Dijkstra 算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是_。对于如下图所
16、示的带权有向图，从顶点 1 到顶点 5 的最短路径为_。 （分数：4.00）A.非零B.非整C.非负 D.非正解析：A.1，4，5B.1，2，3，5C.1，4，3，5D.1，2，4，3，5 解析：解析 应用 Dijkstra 算法求解最短路径时，要求各条边的权值非负，否则求解结果不对，理由在正文中已有说明。对于图例，从顶点 1 到顶点 5 有 4 条路径，只有 1，2，4，3，5 这条路径的路径长度最短，等于 11。设 AOV 网有 n 个顶点和 e 条边，如果采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为_；如果采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为_。（分
17、数：4.00）A.O(nlog2e)B.O(n+e) C.O(ne)D.O(n2)解析：A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2) 解析：解析 采用邻接表作为 AOV 网的存储结构进行拓扑排序，需要对 n 个顶点做进栈、出栈、输出各一次，在处理 e 条边时，需要检测这 n 个顶点的边链表的 e 个边结点，总共需要的时间代价为 O(n+e)。采用邻接矩阵作为 AOV 网的存储结构进行拓扑排序，在处理 e 条边时需要对每一个顶点检测相应矩阵中的某一行，寻找与它相关联的边，以便对这些边的入度减 1，需要的时间代价为 O(n 2 )。2.在 AOE 网络中，可能同时存在几条关键
18、路径，称所有关键路径都需通过的有向边为_，如果加速这样的关键路径就能使整个工程提前完成。（分数：2.00）A汇B源C桥 D潭解析：解析 在 AOE 网中，如果加速桥的进度，就可以加速整个工程的完成。“源”“汇”“潭”都是数据流图中的词汇，与关键路径法无关。3.在下列有关图的存储结构的说法中错误的是_。（分数：2.00）A.用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关B.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用 C.邻接矩阵只适用于稠密图(边数接近于顶点树的平方)，邻接表适用于稀疏图(边数远小于顶点数的平方)D.存储无向图的邻接矩阵是
19、对称的，因此只要存储邻接矩阵的下(上)三角部分就可以了解析：解析 用邻接表可以存储一个无向图，只不过同一条边如(v i ，v j )在邻接表的与 v i 相关的边链表和与 v j 相关联的边链表中都出现。而在存储有向图时，各定点的边链表是由该顶点发出的有向边构成的，所以称为“出边表”。另外的逆邻接表的各顶点的边链表则是由进入该顶点的有向边构成，因而称为“入边表”。在一个有向图的邻接矩阵表示中，删除一条边v i ，v j 需要耗费的时间是_，要计算某个顶点的出度所耗费的时间是_。与邻接矩阵相比，邻接表更适合于存储_图。（分数：6.00）A.极小 B.连通C.极小连通D.无环解析：A.n-1 Bn
20、C.n(n-1)/2D.n(n-1)解析：A.n-1BnC.n(n-1)/2 D.n(n-1)解析：解析 有向图的邻接矩阵不是对称矩阵，边v i ，v j ，在矩阵中仅第 i 行第 j 列为 1，且矩阵可以按其下标直接存取，所以要删除边v i ，v j ，只要在相应位置置零即可。要计算顶点 i 的出度必须把第 i 行所有的 n 个矩阵元素中的 1 加起来，要检测 n 次。稀疏图指的是矩阵中非零元素个数远远小于 n 2 的图，如果用邻接矩阵存储，要存放大量的零元素，所以改用邻接表存储更经济些。对应具有 e 条边的无向图，它的邻接表中有_个边结点。一个有 n 个顶点和 n 条边的无向图一定是_的。
21、（分数：4.00）A.e-1BeC.2(e-1)D.2e 解析：A.重连通的B.不连通的C.无环的D.有环的 解析：解析 在一个具有 e 条边的无向图的邻接表中，若顶点 v i 与顶点 v j 之间有边，在顶点 v i 的边链表和顶点 v j 的边链表中都有这条边的边结点，所以总共有 2e 个边结点。最后，如果一个无向图有n 个顶点和 n-1 边，可以使它连通但没有环(即生成树)，但再加一条边，在不考虑重边的情形下，就会构成环。4.若一个具有 N 个顶点、K 条边的无向图是一个森林(NK)，则该森林必有_棵树。（分数：2.00）AKBNC.N-K D.1解析：解析 设此森林有 m 棵树，每棵树
22、具有的顶点数为 v i (1im)。根据树的性质，每棵树的边数为 v i -1，则有： v 1 +v 2 +v m =N (v 1 -1)+(v 2 -1)+(v m -1)=K 用-，得 m=N-K。5.Dijkstra 算法是按_方法求出图中从某顶点到其余顶点最短路径的。（分数：2.00）A.按长度递减的顺序求出图的某顶点到其余顶点的最短路径B.按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C.通过深度优先遍历求出图中从某顶点到其余顶点的所有路径D.通过广度优先遍历求出图的某顶点到其余顶点的最短路径解析：解析 Dijkstra 算法是按长度递增的顺序，求图的某顶点到其余顶点的最短路径
23、的。6.使用 DFS 算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是_。（分数：2.00）A.逆拓扑有序 B.拓扑有序C.无序的D.都不是解析：解析 DFS 算法对一个有向图做深度优先遍历，并未专门判断有向图是否有环(有向回路)存在，无论图中有环还是无环，都得到一个顶点序列。如果无环，这个顶点序列就是一个拓扑有序的序列。在退出递归过程中输出的应是逆拓扑有序序列。如果有环，这个顶点序列不是拓扑有序序列。7.当各边上的权值_时，BFS 算法可用来解决单源最短路径问题。（分数：2.00）A.都相等 B.都互不相等C.不一定相等D.都大于 0解析：解析 BFS 算法是按
24、“层次”遍历图的。只要对算法稍做修改，在每个顶点进队列时记录它的层次，在顶点输出时就能得到它到源顶点的最短路径。应该了解，在各边上权值都是相等的场合，使用 DFS算法也能求得源顶点到其他各顶点的最短路径。8.设有一个有向图 G=(V，E)，其中 V=v 1 ，v 2 ，v 3 ，v 4 ，v 5 ，v 6 E=v 1 ，v 2 ，v 2 ，v 3 ，v 3 ，v 4 ，v 5 ，v 2 ，v 5 ，v 6 ，v 6 ，v 4 不属于该图的拓扑有序序列是_。（分数：2.00）A.v1，v5，v2，v3，v6，v4B.v5，v6，v1，v2，v3，v4C.v1，v2，v3，v4，v5，v6 D.v
25、5，v1，v6，v4，v2，v3解析：解析 对应的有向图 G 如下图所示，拓扑排序可得到 7 种不同的结果。 9.在下列有关关键路径的说法中错误的是_。（分数：2.00）A.在 AOE 网络中可能存在多条关键路径B.关键活动不按期完成就会影响整个工程的完成时间C.任何一个关键活动提前完成，那么整个工程将会提前完成 D.所有的关键活动都提前完成，那么整个工程将会提前完成解析：解析 在 AOE 网络中可能存在多条关键路径，因此，任何一个关键活动提前完成，只影响到其中某一条关键路径，整个工程不一定能提前完成。但如果 AOE 网络中存在“桥”，即所有关键路径都要通过的关键活动，它提前完成，整个工程可以
26、提前。10.下列哪一种图的邻接矩阵是对称矩阵?（分数：2.00）A.有向图B.无向图 C.AOV 网D.AOE 网解析：解析 无向图的邻接矩阵是 n 阶对称矩阵。11.判断以下叙述正确的是_。 对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图 连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点 图的深度优先搜索中一般要采用栈来暂存访问过的顶点（分数：2.00）A.，B.， C.，D.，解析：解析 I 叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图。、叙述显然是正确的。12.判断有向图是否存
27、在回路，除了可以利用拓扑排序方法外，还可以利用的是_。（分数：2.00）A.求关键路径的方法B.求最短路径的 Dijkstra 方法C.深度优先遍历算法 D.广度优先遍历算法解析：解析 当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出 DFSTraverse算法)即为逆向的拓扑序列。13.下列 4 组含 C1C7 的结点序列中，_是下图所示的有向图的拓扑序列。 （分数：2.00）A.C1，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 解析：解析 考查拓扑
28、排序的算法。 以 C1 开通的拓扑排序过程，如下图所示 以 C5 开通的拓扑排序过程，答案中的过程如下图所示。 二、综合应用题(总题数：3，分数：36.00)对于下图所示的 AOE 网络： （分数：18.00）(1).这个工程最终可能在什么时间结束?（分数：9.00）_正确答案：()解析：各顶点(事件)的最早可能开始时间 Ve(i)和最迟运行开始时间 Vl(i)参考下表(a)。 表(a) 顶点 1 2 3 5 5 6 Ve 0 19 15 29 38 43 Vl 0 19 15 37 38 43 各边(活动)的最早可能开始时间 Ee(k)和最迟运行开始时间 El(k)参看表(b)： 表(b)
29、边1，21，33，22，53，52，44，65，6Ee00151915192938El170151927273738整个工程最早在 43 天完成。(2).确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。（分数：9.00）_正确答案：()解析：如果活动 k 的最早可能开始时间 Ee(k)与最迟运行开始时间 El(k)相等，则该活动是关键活动。本题的关键活动为1，3，3，2，2，5，5，6，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。 由关键活动组成的 AOV 网络如下图所示。 14.计算连通网的最小生成树 Dijkstra 算法
30、可简述如下：将连通网所有的边以方便的次序逐条加入到初始为空的生成树的边集合 T 中。每次选择并加入一条边时，需要判断它是否会与先前加入 T 中的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。如果以邻接矩阵作为连通网的存储结构(仅适用矩阵的上三角部分)，并在邻接矩阵的下三角部分记录最小生成树的边信息。试以下图所示的图 G 为例，画出构造出的最小生成树及其邻接矩阵，并列出每次选择的边和可能去掉的边。 （分数：9.00）_正确答案：()解析：最小生成树及其邻接矩阵图如下图所示，每次选择的边和可能去掉的边如下表所示。 15.下面是求无向连通图最小生成树的一种算法： /设图中总顶点数为 n，总边数为 m 将图中所有的边按其权值从大到小排序为(e 1 ，e 2 ，e 3 ，e m ) i=1; while(m=n) 从图中删去 e i ；(m=m-1) 若图不再连通，则恢复 e i ；(m=m+1) i=i+1; 试问这个算法是否正确，并说明原因。 （分数：9.00）_正确答案：()解析：算法正确。一个无向连通图的边数 m 可以大于顶点数 n，此时图中必然存在回路。在回路上依次删去权值最大的边 e1，权值稍小的边 e2，直到不能再删除为止。剩下的不能构成回路，又不能再减少的边就应是最小生成树的边了。如下图所示。
