当前位置：文档之家 › 北京理工大学珠海学院《数据结构》习题集：第7章 图(第1次更新2012-5-1)

北京理工大学珠海学院《数据结构》习题集：第7章 图(第1次更新2012-5-1)

  • 格式：doc
  • 大小：512.50 KB
  • 文档页数：8

数据结构课后练习题 第7章 图

1/8 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

第7章 图 一、 选择题 1. 一个有n个顶点的无向图最多有（ ）条边。【＊，★】 A、n B、n(n-1) C、n(n-1)/2 D、2n 2. 具有6个顶点的无向图至少有（ ）条边才能保证是一个连通图。【＊，★】 A、5 B、6 C、7 D、8 3. 具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（ ）。【＊】 A、线性图 B、无向完全图 C、无向图 D、简单图 4. 具有4个顶点的无向完全图有（ ）条边。【＊】 A、6 B、12 C、16 D、20 5. G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。【＊＊】 A、6 B、7 C、8 D、9 6. 存储稀疏图的数据结构常用的是（ ）。【＊＊】 A、邻接矩阵 B、三元组 C、邻接表 D、十字链表 7. 对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（ ）。【＊】 A、n B、(n-1)2 C、(n+1)2 D、n2 8. 设连通图G的顶点数为n，则G 的生成树的边数为（ ）。【＊】 A、n-1 B、n C、2n D、2n-1 9. 对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（ （1） ）；所有邻接表中的结点总数是（ （2） ）。【＊，★】 （1）A、N B、N+1 C、N-1 D、N+E （2）A、E/2 B、E C、2E D、N+E 10. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（ ），所有顶点邻接表的结点总数为（ ）。【＊】 A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11. 在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（ ）。【＊，★】 A、顶点v 的度 B、顶点v 的出度 C、顶点v 的入度 D、依附于顶点v 的边数 12. 已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ ）和（ ）【＊＊，★】 （1） A、abecdf B、acfebd C、acebfd D、acfdeb （2） A、abcedf B、abcefd C、abedfc D、acfdeb a

bec

df 13. 采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ ）和（ ）。【＊＊】 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 数据结构课后练习题 第7章 图

2/8 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

14. 已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。【＊，★】 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v2 V10 V21V32V43

213V544V

13V

3V

V

V 15. 已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（ ）。【＊，★】

ABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G01010101H00001110

A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDC E、ABEHFGDC F、ABEHGFCD 16. 已知一个图如下，在该图的最小生成树中各边上权值之和为（ ），在该图的最小生成树中，从v1到v6的路径为（ ）。【＊，★】 A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6

v1v2

v4v6

v3v558

648

10

1220

9选择题16 17. 关键路径是事件结点网络中的（ ）。【＊】 A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路 18. 正确的AOE网必须是（ ），AOE网中某边权值应当是（ ）。【＊，★】 （1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图 （2）A、实数 B、正整数 C、正数 D、非负数 19. 已知一个图如下，则由该图得到的一种拓扑序列为（ ）。【＊，★】 A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5 20. 下面结论中正确的是（ ）。【＊】 数据结构课后练习题 第7章 图

3/8 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。 21. 下面结论中正确的是（ ）。【＊＊】 A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。 B、网络的最小代价生成树是唯一的。 C、在拓扑排序序列中，任意两个相继顶点vi 和vj 都存在从vi 到vj 的路径。 D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。 22. 下面结论不正确的是（ ）。【＊＊，★】 A、无向图的连通分量是该图的极大连通子图。 B、有向图用邻接矩阵表示容易实现求顶点度数的操作。 C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。 D、有向图的邻接矩阵必定不是对称矩阵。 23. 下面结论中正确的是（ ）。【＊，★】 A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按深度优先搜索遍历的结果是唯一的。 C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。 D、图的拓扑排序序列是唯一的。 24. 下面结论中不正确的是（ ）。【＊，★】 A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按广度优先搜索遍历的结果是唯一的。 C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。 D、图的多重邻接表表示法中，表中结点数目是图中边的条数。 25. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。【＊】 A、1/2 B、1 C、2 D、4 26. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。【＊】 A、1/2 B、1 C、2 D、4 27. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ）。【＊＊，★】 A、求关键路径的方法 B、求最短路径的DIJKSTRA方法 C、广度优先遍历算法 D、深度优先遍历算法 28. 任何一个带权的无向连通图的最小生成树（ ）。【＊】 A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 29. 以下说法正确的是（ ）。（注：多项选择）【＊＊，★】 A、连通图的生成树，是该连通图的一个极小连通子图。 B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C、任何一个有向图，其全部顶点可以排成一个拓扑序列。 D、有回路的图不能进行拓扑排序。 30. 以下说法错误的是（ ）。【＊＊】 A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个 数有关，而与图的边数无关。 B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。 C、存储无向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。 D、用邻接矩阵A 表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am 的第i行第j列的元素是否为0 即可。 数据结构课后练习题 第7章 图

4/8 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1

31. 以下说法正确的是（ ）。【＊＊】 A、连通分量是无向图中的极小连通子图。 B、强连通分量是有向图中的极大强连通子图。 C、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 D、对有向图G，如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定 是完全图。

二、 判断题 1. 用邻接矩阵法存储一个图时，所占用的存储空间大小仅与图中结点个数有关。【＊】 2. 对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。【＊】 3. 任何有向网拓扑排序的结果是唯一的。【＊】 4. 有回路的图不能进行拓扑排序。【＊】 5. 存储有向图的邻接矩阵是对称的。【＊】 6. 一个有向图G中若有弧、和, 则在图G的拓扑序列中，顶点vi,vj 和vk 的相对位置为vi,vj,vk。【＊】 7. 在AOE网中一定有一条关键路径。【＊】 8. 含有10个顶点的无向连通图其生成树含有9 条边。【＊】 9. 十字链表是图的一种顺序表示法。【＊】

三、 填空题 1. 对具有n个顶点的图，其生成树有且仅有（ ）条边，即生成树是图的边数（ ）的连通图。【＊】 2. 一个无向图有n个顶点和e条边，则所有顶点的度数之和为（ ），其邻接矩阵是一个关于（ ）对称的矩阵。【＊】 3. 在图形结构中，每个结点的前驱结点和后继结点可以有（ ）。【＊】 4. 设无向图G的顶点数为n，图G最少有（ ）边，最多有（ ）条边。若G为有向图，有n个顶点，则图G最少有（ ）条边，最多有（ ）条边。具有n个顶点的无向完全图，边的总数为（ ）条，而有n个顶点的有向完全图，边的总数为（ ）条。【＊】 5. 在无权图G的邻接矩阵A中，若(vi,vj)或属于G的边/弧的集合，则对应元素A[i][j]等于（ ），否则等于（ ）。【＊】 6. 在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（ ）。【＊】 7. 已知一个图的邻接矩阵表示，计算第I个顶点的入度方法为（ ）。【＊】 8. 在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（ ），而对于无向图而言等于该顶点的（ ）。【＊】 9. 已知图G的邻接表如图7.4所示，其从顶点V1出发的深度优先搜索序列为（ ），其从顶点V1出发的广度优先搜索序列为（ ）。

合集下载

数据结构操练 第七章 图

数据结构操练 第七章 图


A．n-1
C．n(n+1)/2
B．n(n-1)/2
C．0
14．设有向无环图 G 中的有向边集合 E={<1，2>，<2，3>，<3，4>，<1，4>}，
则下列属于该有向图 G 的一种拓扑排序序列的是（ ）。
1
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术关，通系电1，力过根保管据护线生高0不产中仅工资2艺料22高试2可中卷以资配解料置决试技吊卷术顶要是层求指配，机置对组不电在规气进范设行高备继中进电资行保料空护试载高卷与中问带资题负料2荷试2，下卷而高总且中体可资配保料置障试时2卷，32调需3各控要类试在管验最路；大习对限题设度到备内位进来。行确在调保管整机路使组敷其高设在中过正资程常料1工试中况卷，下安要与全加过，强度并看工且25作尽52下可22都能护可地1关以缩于正小管常故路工障高作高中；中资对资料于料试继试卷电卷连保破接护坏管进范口行围处整，理核或高对者中定对资值某料，些试审异卷核常弯与高扁校中度对资固图料定纸试盒，卷位编工置写况.复进保杂行护设自层备动防与处腐装理跨置，接高尤地中其线资要弯料避曲试免半卷错径调误标试高方中等案资，，料要编试求5写、卷技重电保术要气护交设设装底备备置。4高调、动管中试电作线资高气，敷料中课并设3试资件且、技卷料中拒管术试试调绝路中验卷试动敷包方技作设含案术，技线以来术槽及避、系免管统不架启必等动要多方高项案中方；资式对料，整试为套卷解启突决动然高过停中程机语中。文高因电中此气资，课料电件试力中卷高管电中壁气资薄设料、备试接进卷口行保不调护严试装等工置问作调题并试，且技合进术理行，利过要用关求管运电线行力敷高保设中护技资装术料置。试做线卷到缆技准敷术确设指灵原导活则。。：对对在于于分调差线试动盒过保处程护，中装当高置不中高同资中电料资压试料回卷试路技卷交术调叉问试时题技，，术应作是采为指用调发金试电属人机隔员一板，变进需压行要器隔在组开事在处前发理掌生；握内同图部一纸故线资障槽料时内、，设需强备要电制进回造行路厂外须家部同出电时具源切高高断中中习资资题料料电试试源卷卷，试切线验除缆报从敷告而设与采完相用毕关高，技中要术资进资料行料试检，卷查并主和且要检了保测解护处现装理场置。设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。
数据结构习题与答案图

数据结构习题与答案图

第7章图一、单选题01、在一个图中，所有顶点的度数之和等于图的边数的倍。

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

A．1/2B．1 C．2 D．403、有8个结点的无向图最多有条边。

A．14 B．28 C．56 D．11204、有8个结点的无向连通图最少有条边。

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

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

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

A．栈 B．队列 C．树 D．图08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A．O(n)B．O(e)C．O(n+e)D．O(n2)09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 210、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A．0 2 4 3 6 5 1 B．0 1 2 3 4 5 6C．0 4 2 3 1 5 6 D．0 1 3 4 2 5 611、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2 13、图的深度优先遍历类似于二叉树的。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历14、图的广度优先遍历类似于二叉树的。

数据结构第七章1

数据结构第七章1


} ADT Graph
详见p156~157。
7.2 图的存储结构
图的存储结构比较复杂，其复杂性主要表现在：
◆ 任意顶点之间可能存在联系，无法以数据元素 在存储区中的物理位置来表示元素之间的关系。
◆ 图中顶点的度不一样，有的可能相差很大，若 按度数最大的顶点设计结构，则会浪费很多存储单 元，反之按每个顶点自己的度设计不同的结构，又 会影响操作。 图的常用的存储结构有：邻接矩阵、邻接链表、十 字链表、邻接多重表。
图7-8 带权有向图的数组存储
⑶ 有向图邻接矩阵的特性
有向完全图：对于有向图，若图中顶点数为n ，
用e表示弧的数目，则e[0，n(n-1)] 。具有n(n-1)条边的 有向图称为有向完全图。
完全有向图另外的定义是：
对于有向图G=(V，E)，若vi，vjV ，当vi ≠vj时， 有<vi ,vj>E∧<vj , vi >E ，即图中任意两个不同的顶点 间都有一条弧，这样的有向图称为有向完全图。 有很少边或弧的图（e<n㏒n）的图称为稀疏图，反 之称为稠密图。
wij 若<vi,vj>E，即vi , vj邻接，权值为wij
∞ 若<vi,vj>E，即vi , vj不邻接时
a
2
6 3 1
b 3
4 5
e
c
d
vexs a b c d e
(b) 顶点矩阵
∞ ∞ ∞ ∞ ∞
6 2 ∞∞ 3 ∞ 4 ∞ ∞∞
∞ ∞ 1 ∞ ∞
∞ 3 ∞ 5 (v,v’)E，则称顶点v和v’ 互为邻接点，即v和w相 邻接。边(v,v’)依附(incident)与顶点v和v’ 。
对于有向图G=(V ，E)，若有向弧<v,w>E，则称 顶点v “邻接到”顶点w，顶点w “邻接自”顶点v ，弧 <v,w> 与顶点v和w “相关联” 。
数据结构练习_第七章_图

数据结构练习_第七章_图

数据结构练习第七章图一、选择题1.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.82. 设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

A. n(n-1)/2B. n(n-1)C. n2D. n2-1 3．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。

A. n-1B. nC. n+1D. 2n-1 4．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。

A. n，e B e，n C 2n，e D n，2e 5．设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

A. n(n-1)B. n+1C. nD. n(n+1) 6．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。

A .n B. e C. 2n D. 2e7．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

A. nB. n-1C. mD. m-1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。

A. abedfcB. acfebdC. aebdfcD. aedfcb 9．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。

A. O(n+e)B. O(n2)C. O(ne)D. O(n3) 10．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。

A. 第i行非0元素的个数之和B.第i列非0元素的个数之和C. 第i行0元素的个数之和D. 第i列0元素的个数之和11．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

A. 2nB. nC. n/2D. n(n-1) 12．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。

A. nB. n-1C. 2nD. 2n-113．设无向图的顶点个数为n，则该图最多有（）条边。