《数据结构课后习题(第7章)》由会员分享，可在线阅读，更多相关《数据结构课后习题(第7章)（10页珍藏版）》请在金锄头文库上搜索。
1、计科系 2011 级网络工程 1 班、计算机科学与技术 2 班算法与数据结构课后习题（第 7 章）第 1 页 共 11 页【课后习题】第 7 章 图2011 级（ ）班 学号： 姓名： A题 号 一 二 三 四 五 总分得 分一、判断题（如果正确，在对应位置写 T，否则写 F。每题 0.5 分，共 5 分) 1 2 3 4 5 6 7 8 9 101. 图 G 由两个集合 V（G）和 E（G）所组成，其中顶点集 V（G）不能为空集，而边集 E(G) 可以为空集。 2. 一般情况下，对于稠密图 G，采用邻接表存储比采用邻接矩阵存储节省省空间。3. 生成树是一个连通图的极小连通子图，它含有图中全部
2、 n 个顶点，但只有 n-1 条边。4. 从不同顶点出发进行 DFS 或 BFS，得到的生成树不同，即：图的生成树不惟一。但具有 n 的结点，n-1 条边的连通图其生成树是唯一的。5. 求最小生成树的算法有 Prim（普里姆）算法和 Dijkstra（迪杰斯特拉算法） 。6. “关键活动 ”指的是：该弧上的权值增加 将使有向图上的最长路径的长度增加。7. 整个工程完成的时间为：从有向图的源点到汇点的最短路径长度。8. 有 n 个顶点的无向连通图至少有 n-1 条边, 有 n 个顶点的强连通图至少有 n 条边。9. 若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系, 则这样
3、的有向图叫做用顶点表示活动的网络，简称 AOV 网。10.十字链表是无向图的另一种链式结构。二、单项选择（请将正确答案的代号填写在下表对应题号下面。每题 1 分，共 30 分)题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15答案 题号 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30计科系 2011 级网络工程 1 班、计算机科学与技术 2 班算法与数据结构课后习题（第 7 章）第 2 页 共 11 页答案 1. 在一个图中，所有顶点的度数之和等于图的边数的( )倍。A).1/2 B) 1 C) 2 D). 42. 在一个有向
4、图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。A) 1/2 B) 1 C) 2 D) 43. 若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（ ） 。A图中每个顶点的入度 B图中每个顶点的出度C图中弧的条数 D图中连通分量的数目4. 图的邻接矩阵表示法适用于表示（ ） 。A无向图 B有向图 C稠密图 D稀疏图5. 任何一个无向连通图的最小生成树（ ） 。A.只有一棵 B.有一棵或多棵 C.一定有多棵 D. 可能不存在6. 一个有 n 个顶点的无向图最多有（ ）条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n7. 具有 4 个顶点的有向完全图有（ ）条
5、边。A. 6 B. 12 C. 16 D. 208. n 个顶点 e 条边的带权无向连通图的最小生成树包含（ ）个顶点A.n-1 B.n C. n/2 D.n+19. 在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要( )条边。A. n B. n+1 C. n-1 D. n/210. 对于一个具有 n 个顶点 e 条边的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） 。A. n B. n*e C. n+e D. n*n11. 对于一个具有 n 个顶点 e 条边的无向图，若采用邻接表表示，则该邻接表包含（ ）个边结点。A. e B. 2e C. n+e D. n212. 已知一有向图
6、的邻接表存储结构如图 2 所示。 根据有向图的深度优先遍历算法，从顶点 v1 出发， 所得到的顶点序列是( )。A. v1,v2,v3,v5,v4 计科系 2011 级网络工程 1 班、计算机科学与技术 2 班算法与数据结构课后习题（第 7 章）第 3 页 共 11 页a6=1V5V4V1V2V6V3a8=5a2=10a1=3a5=1a4=20a7=7a3=18图 4B. v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v213. 已知一有向图的邻接表存储结构如图 2 所示。根据有向图的广度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是( )。
7、A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v214. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历15. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历16. 关键路径是 AOE 网络中( )。A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路 D.最短的回路17. 对于一个有向图，若一个顶点的入度为 k1,、出度为 k2，则对应邻接表
8、中该顶点单链表中的结点数为( )。A.k1 B.k2 C.k1-k2 D.k1+k218. 对于一个有向图，若一个顶点的入度为 k1,、出度为 k2，则对应逆邻接表中该顶点单链表中的结点数为( )。A.k1 B.k2 C.k1-k2 D.k1+k219. 在图 3 所示的拓朴排列的结果序列为( )。A.125634 B.516234 C.123456 D.52163420. 一个有 n 个顶点的无向连通图，它所包含的连通分量个数为 ( )。A.0 B.1 C.n D.n+121. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用( )。A. 求关键路径的方法 B. 求最短路径的
9、 Dijkstra 方法C. 广度优先遍历算法 D. 深度优先遍历算法22. 如果图 4 是一交通图，其中 Vi 表示城市，计科系 2011 级网络工程 1 班、计算机科学与技术 2 班算法与数据结构课后习题（第 7 章）第 4 页 共 11 页ai 表示城市之间交通费用，则从 V1 到 V4 中转站最少的路径可为（ ） 。A、V1V2V4； B、V1V2V5V6V4；C、V1V3V5V6V4； D、V1V5V6V4。23. 如果图 4 当做一交通图，Vi 表示城市，a i 表示城市之间交通费用，则 V1 到 V4 交通费用最省路径可为（ ） 。A、V1V2V4； B、V1V2V5V6V4；
10、C、V1V3V5V6V4 ； D、V1V5V6V4。24. 如果图 4 是一 AOE-网 , 其一关键路径为（ ） 。A、V1V2V4； B、V1V2V5V6V4； C、V1V3V5V6V4 ； D、V1V5V6V4。25. 求关键路径的算法中，关键活动是指最早发生时间（ ）最迟发生时间的活动。A.等于 B.大于 C.小于 D.不确定26. 已知一个图右如下所示，从顶点 a 出发进行广度优先遍历可能得到的序列为( )A.a c e f b d B.a c b d f eC.a c b d e f D.a c d b f e27. 给定下面有向图(题 27)，从顶点 1 出发，其深度优先搜索序列
11、为（ ）A）12534 B）12435 C） 14325 D）1234528. 对于上图所示的 AOV 网( 题 28)，不能出现的拓扑序列为（ ）A） 2 4 1 3 5 B）1 2 4 3 5 C）1 2 3 4 5 D）2 1 4 3 529. 已知一个有向图如右所示，则从顶点出发能得到拓朴序列为( ) A B. C. D. 30. 下列为顶点表示活动的有向图如下图所示，其有向边表示活动之间发生的先后顺序，则其拓朴序列为（ ） 。题 271 5 4 3 2 1 3 5 4 2 题 28 计科系 2011 级网络工程 1 班、计算机科学与技术 2 班算法与数据结构课后习题（第 7 章）第
12、5 页 共 11 页A、FBCAED； B、FBCEDA； C、BCAFED； D、BFCAED。二、填空题（每空 1 分，共 40 分)1. 若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为 。2. 带权图的路径长度是指路径上 3. 图的存储结构主要有： 、 、十字链表、邻接多重表。对于一个确定的图，其 是唯一的， 不惟一，因各个边结点的链入顺序是任意。4. 邻接矩阵的空间复杂度为 ，而邻接表的空间复杂度为 。邻接矩阵多用于 的存储，邻接表多用于 的存储。5. 深度优先搜索是模仿树的 过程，算法是递归的。广度优先搜索是一种分层的搜索过程，是模仿树的 过程，算法是 的。6. Prime 算法特点: 将顶点归并，与边数无关，适于求 的最小生成树。Kruskal 算法特点：将边归并，适于求 的最小生成树。7. 若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为 。8. 若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为 ， 没有 的连通图为双连通图。EABCDF计科系 2011 级网络工程 1 班、计算机科学与技术 2 班算法与数据结构课后习题（第 7 章）第 6 页 共 11 页9. 求单源最短路径，用 算法；求所有顶点间的最短路径，用 算
