当前位置：文档之家 › 数据结构第7章图习题

数据结构第7章图习题

  • 格式：docx
  • 大小：187.79 KB
  • 文档页数：9

第七章图习题1 单项选择题1、图中有关路径的定义是（）。

A、由顶点和相邻顶点序偶构成的边所形成的序列B、由不同顶点所形成的序列C、由不同边所形成的序列D、上述定义都不对2、设无向图的顶点个数为n，则该图最多有（）条边。

A、n– 1B、n (n– 1)/2C、n (n+1)/2D、n23、一个n个顶点的连通无向图，其边的个数至少为（）。

A、n– 1B、nC、n+1D、n log n4、下面结构中最适于表示稀疏无向图的是（）。

A、邻接矩阵B、逆邻接表C、邻接多重表D、十字链表5、下列哪一种图的邻接矩阵是对称矩阵？（）A、有向图B、无向图C、AOV网D、AOE网6、当一个有N个顶点的图用邻接矩阵A表示时，顶点V i的度是（）。

A、第j列所有元素之和B、第i行所有元素之和C、不确定D、第j列所有元素之和+第i行所有元素之和7、下面哪一方法可以判断出一个有向图是否有环（回路）（）。

A、深度优先遍历B、拓扑排序C、求最短路径D、求关键路径8、在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。

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

A、O(n)B、O(n+e)C、O(n2)D、O(n3)10、已知有向图G=(V, E)，其中V={v1, v2, v3, v4, v5, v6, v7}，E={<v1,v2>, <v1,v3>, <v1,v4>, <v2,v5>, <v3,v5>, <v3,v6>, <v4,v6>, <v5,v7>, <v6,v7>}, G的拓扑序列是（）。

A、v1,v3,v4,v6,v2,v5,v7B、v1,v3,v2,v6,v4,v5,v7C 、v 1,v ,v 4,v 5,v 2,v 6,v 7D 、v 1,v 2,v 5,v 3,v 4,v 6,v 711、在用邻接表表示图时，拓扑排序算法时间复杂度为( )。

A 、O(n )B 、O(n +e )C 、O(n 2)D 、O(n 3)12、关键路径是事件结点网络中（ ）。

A 、从源点到汇点的最长路径B 、从源点到汇点的最短路径C 、最长路径D 、最短路径13、下面关于求关键路径的说法不正确的是（ ）。

A 、求关键路径是以拓扑排序为基础的B 、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C 、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D 、关键活动一定位于关键路径上14、下列关于AOE 网的叙述中，不正确的是（ ）。

A 、关键活动不按期完成就会影响整个工程的完成时间B 、任何一个关键活动提前完成，那么整个工程将会提前完成C 、所有的关键活动提前完成，那么整个工程将会提前完成D 、某些关键活动提前完成，那么整个工程将会提前完成 15、采用邻接表存储图的深度优先遍历算法类似于二叉树的（）。

A 、层序遍历B 、先序遍历C 、中序遍历D 、后序遍历 16、图G 中，所有顶点的度数之和等于所有边数的（）倍。

A 、1B 、2C 、3D 、1/217、一个具有n 个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是（）。

A 、n – 1B 、n +1C 、(n – 1)2D 、n 218、要连通n 个顶点的有向图，至少需要（ ）条边。

A 、n – 1B 、nC 、n +1D 、n log n19、从图的邻接矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=01010110o A 中可以看出，该图有（ ① ）个顶点，如果是有向图，该图有（ ② ）条弧，如果是无向图，则有（ ③ ）条边。

① A 、9B 、3C 、6D 、1②A、5 B、4 C、3 D、2③A、5 B、4 C、3 D、220、设图V={a, b, c, d, e, f}，E={(a,b), (a, e),(a, c),(b, e),(c, f), (f, d),(e, d)}，对该图进行深度优先遍历，得到的顶点序列是（）。

A、abecdfB、acfebdC、aebcfdD、aedfcb21、在有向图G的拓扑序列中，若顶点v i在顶点v j之前，则下面情况不可能出现的是（）。

A、G中有弧<v i,v j>B、G中有一条从v i到v j的路径C、G中没有弧<v i,v j>D、G中有一条从v j到v i的路径2 填空题1、如果含n个顶点的图形成一个环，则它有（）棵生成树。

2、下图所示的强连通分量有（）个。

3、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。

4、求图的最小生成树有两种算法，其中（）算法适合求解稀疏图的最小生成树。

5、有向图G可以拓扑排序的判别条件是（）。

6、在AOV网中，存在环意味着（）；对程序的数据流图来说，它表明存在（）。

7、已知一个图的广度优先生成树如下图所示，则与此相应的广度优先遍历序列为（）。

8、在有n个顶点的有向图中，每个顶点的度最大可达（）。

9、已知一无向图G = (V, E)，其中V = {a, b, c, d, e}，E = {(a, b), (a, d), (a, c), (d, c), (b, e)}，现用某种遍历方法从顶点a开始遍历图，得到的遍历序列为abedc，则采用的方法是（）。

10、为了实现图的广度优先遍历，除了一个标志数组标志已访问的图的结点外，还需要（）存放被访问的结点一实现遍历。

11、在图的最小生成树算法中，Prim（普里姆）算法适合于求（）的网的最小生成树，Kruskal（克鲁斯卡尔）算法适合于求（）的网的最小生成树。

12、图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

13、图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

3 问答题1、对于稀疏图和稠密图，采用邻接矩阵和邻接表哪个更好？2、根据下图回答问题：(1) 如果每个指针需要4个字节，每个顶点的标号占2个字节，每条边的权值占2个字节。

下面的图采用哪种表示法所需要的空间较多，为什么？(2) 写出从顶点1开始的DFS树。

第2题图3、有向图的邻接表存储如下：(1) 画出其邻接矩阵；(2) 写出图的所有强连通分量；(3) 写出顶点a到顶点i的全部简单路径。

4、设有逻辑结构B ={K, R}，K = {k1, k2,…, k9 }，R = {<k1, k3>, <k1, k8>, <k2, k3>, <k2, k4>, <k2, k5>, <k3, k9>, <k5, k6>, <k8, k9>, <k9, k7>, <k4, k7>, <k4, k6>}，回答下列问题：(1) 画出这个逻辑结构的图示；(2) 相对于关系r，指出所有的开始结点和终端结点；(3) 分别对应关系r中的开始结点，举出一个拓扑排序的例子；(4) 画出这个逻辑结构的正向邻接表和逆向邻接表。

5、下面的邻接表表示一个给定的无向图，请回答：(1) 给出从顶点1开始，对图G用深度优先搜索法进行遍历时的顶点序列；(2) 给出从顶点1开始，对图G用广度优先搜索法进行遍历时的顶点序列。

6、根据下面的图回答问题：(1) 从顶点A出发，求它的深度优先生成树；(2) 从顶点E出发，求它的广度优先生成树；(3) 根据普里姆算法求由A点开始构造最小生成树。

第6题图 第8题图7、请问在什么情况下，普里姆算法与克鲁斯卡尔算法生成不同的最小生成树？8、用迪杰斯特拉算法求图中从顶点a 到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。

9、已知一个带权网如图所示，利用克鲁斯卡尔算法构造该图的最小生成树。

第9题图10、已知图G 的邻接矩阵如下所示：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞62466325546551356516654321 (1) 求从顶点1出发的广度优先搜索序列；(2) 根据prim 算法，求图G 从顶点1出发的最小生成树，要求表示出其每步生成过程。

11、在下图所示的AOE 网中，求： (1) 完成工程至少需要多少时间？(2) 哪些活动是关键活动？关键路径是什么？第11题图12、已知世界六大城市北京(PE)、纽约(N)、巴黎(PA)、伦敦(L)、东京(T)、墨西哥(M)，下表给出了这六大城市之间的交通里程：世界六大城市交通里程表（单位：百公里）(1) (2) 画出该图按权值递增的顺序来构造的最小代价生成树。

13、已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址在何处？给出解题过程。

⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞052301101404230320654321v v v v v v4 算法阅读题下面函数是在无向图的邻接表章删除一条边的算法，请完善该程序。

【东南大学2005三】void deledge(ALGraph *G, inti , int j){EdgeNode *p, *q;p = G->adjlist[i].firstedge;if( (1) ){G->adjlist[i].firstedge = p->next;free(p);}else{while(p->next->adjvex != j && p->next)(2) ;if(p->next!=NULL){q = p->next; (3) ; free(q);} }p = G->adjlist[j].firstedge;if(p->adjvex ==i){G->adjlist[j].firstedge = p->next; free{p};}else{while(p->next->adjvex!= i && p->next)(4) ;if(p->next!=NULL){ q = p->next;(5) ;free(q);}}}5 算法设计题1、设计算法，将一个有向图的邻接矩阵表示转换为邻接表。

2、假设图采用邻接表存储，写出基于DFS算法判定顶点i到顶点j是否有路径，若有路径，返回TRUE，否则返回FALSE。

3、已知有向图采用邻接表存储方式，编写算法删除边(v i, v j)。

合集下载

数据结构-期末复习题及参考答案+-+第7章图

数据结构-期末复习题及参考答案+-+第7章图

《数据结构》期末复习题及参考答案- 第7章图//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 注意：做复习题时，请结合阅读教材，钻研教材，参考课件////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、以下数据结构中，哪种具有非线性结构？A．栈B．队列C．双向链表D．十字链表2、下面关于图的存储的叙述中正确的是（）。

A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。

C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。

D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历4、图的广度优先遍历算法类似于树的（）。

A. 中根遍历B. 先根遍历C. 后根遍历D. 按层次遍历5、设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．06、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A．n-1 B．n C．n+1 D．nlogn；7、一个含有n个顶点的非连通图，则（）：A．它的边一定不大于n-1 B．它的边一定不大于nC．它的边一定小于n-1 D．它的边一定大于08、要连通具有n个顶点的有向图，至少需要（）条边。

数据结构第7章图习题

数据结构第7章图习题

、单项选择题1．在一个无向图 G 中，所有顶点的度数之和等于所有边数之和的 _________ 倍A ．l/2B ．1D ．42．在一个有向图中， 所有顶点的入度之和等于所有顶点的出度之和的 ________倍A ．l/2 C ．2D ．43．一个具有 n 个顶点的无向图最多包含 _____ 条边。

A ．nB ．n ＋1C ．n-1D ．n(n-1)/24．一个具有 n 个顶点的无向完全图包含 _____ 条边。

A ．n(n-l)B ．n(n+l)C ．n(n-l)/2D ．n(n-l)/25．一个具有 n 个顶点的有向完全图包含 _____ 条边。

A ．n(n-1)B ．n(n+l)C ．n(n-l)/2D ．n(n+l)/2 6．对于具有 n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为A. nB. n><h C ．n-17 ．无向图的邻接矩阵是一个 ______A ．对称矩阵 C ．上三角矩阵8．对于一个具有 n 个顶点和 e 条边的无 (有)向图，若采用邻接表表示，则表头 向量的大小为 。

A ．n C ． 2nD ． 2e 9．对于一个具有 n 个顶点和 e 条边的无 (有)向图，若采用邻接表表示，则所有 顶C ．2B ．1 D . (n-I)也-I)B ．零矩阵 D ．对角矩阵 B ．e点邻接表中的结点总数为_________ 。

B. eC. 2nD. 2e10.在有向图的邻接表中，每个顶点邻接表链接着该顶点所有邻接点。

A .入边B.出边C.入边和出边 D .不是入边也不是出边11.在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有邻接点。

A .入边B.出边C.入边和出边 D .不是人边也不是出边12.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是A .完全图B.连通图C.有回路 D .一棵树13.采用邻接表存储的图的深度优先遍历算法类似于二叉树的算法。

图习题及标准答案

图习题及标准答案

图习题及标准答案————————————————————————————————作者：————————————————————————————————日期：第7章图一、选择题1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n)【答案】B2．设无向图的顶点个数为n，则该图最多有（）条边。

A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2【答案】B3．连通分量指的是（）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图【答案】B4．n个结点的完全有向图含有边的数目（）A）n*n B）n（n+1）C）n/2 D）n*（n-1）【答案】D5．关键路径是（）A） AOE网中从源点到汇点的最长路径B） AOE网中从源点到汇点的最短路径C） AOV网中从源点到汇点的最长路径D） AOV网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的（）A）入度 B）出度 C）入度与出度之和 D）（入度+出度）/2 【答案】C7．有e条边的无向图，若用邻接表存储，表中有（）边结点。

A） e B） 2e C） e-1 D） 2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈 B）队列 C）二叉树 D）树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈 B）队列 C）二叉树 D）树【答案】A10．存储无向图的邻接矩阵一定是一个（）A）上三角矩阵 B）稀疏矩阵 C）对称矩阵 D）对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A） 1/2 B）1 C） 2 D） 4【答案】B12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）A） O(n) B） O(n+e) C） O(n2) D） O(n3)【答案】B13．下列关于AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B14．具有10个顶点的无向图至少有多少条边才能保证连通（）A） 9 B）10 C） 11 D） 12【答案】A15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A） e B）2e C） n2-e D）n2-2e【答案】D16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表头向量的大小为。

数据结构 第7章习题答案

数据结构 第7章习题答案

第7章 《图》习题参考答案一、单选题（每题1分，共16分）（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列 C. 树 D. 图 （）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2C. 0 4 2 3 1 6 5D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（A）12. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）13. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）14. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。