第七章∶图练习题

第七章：图练习题

一、选择题

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个顶点的无向图的邻接表中结点总数最多有（）个。

A、2n

B、n

C、n/2

D、n(n-1)

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

13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的

（）和（）。

A、中序遍历

B、先序遍历

C、后序遍历

D、层次遍历

14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。

A、v1,v2,v3,v4,v5

B、v1,v3,v2,v4,v5

C、v1,v2,v3,v5,v4

D、v1,v4,v3,v5,v2

15、已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存

A B C D E F G H

A 0 1 0 1 0 0 0 0

B 1 0 1 0 1 1 1 0

C 0 1 0 1 0 0 0 0

D 1 0 1 0 0 0 1 0

E 0 1 0 0 0 0 0 1

F 0 1 0 0 0 0 1 1

G 0 1 0 1 0 1 0 1

H 0 0 0 0 1 1 1 0

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

17、关键路径是事件结点网络中的（）。

A、从源点到汇点的最长路径

B、从源点到汇点的最短路径

C、最长的回路

D、最短的回路

18、正确的AOE网必须是（），AOE网中某边权值应当是（），权值为0的边表示（）。

（1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图

（2）A、实数 B、正整数 C、正数 D、非负数

（3）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、下面结论中正确的是（）

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、图的多重邻接表表示法中，表中结点数目是图中边的条数。

二、填空题

1、n个顶点的连通图至少有（）条边。

2、一个无向图有n个顶点和e条边，则所有顶点的度数之和为（）。

3、在图形结构中，每个结点的前驱结点和后继结点可以有（）。

4、若无向图G的顶点度数的最小值大于或等于（）时，G至少有一条回路。

5、设无向图G的顶点数为n，图G最少有（）边，最多有（）条边。若G为有向图，有n个顶点，则图G最少有（）条边，最多有（）条边。具

有n个顶点的无向完全图，边的总数为（）条，而有n个顶点的有向完全图，边的总数为（）条。

6、在无权图G的邻接矩阵A中，若(vi,vj)或属于G的边/弧的集合，则对应元素A[i][j]等于（），否则等于（）。

7、在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（）。

8、已知一个图的邻接矩阵表示，计算第I个顶点的入度方法为（）

9、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（），而对于无向图而言等于该顶点的（）。10、已知图G的邻接表如下，从顶点v1出发的深度优先搜索遍历序列为（），广度优先序列为（）。

11、n个顶点的弱连通有向图G最多有（）条弧，最少有（）条弧。

12、在n个顶点e条边的连通图中，连通分量个数为（）。

13、任何（）的有向图，其所有结点都可以排在一个拓扑序列中，拓扑排序的方法是先从图中选一个（）为0的结点且输出，然后从图中删除该结点及其（），反复执行，直到所有结点都输出为止。

14、一个连通图的（）是一个极小连通子图。

15、在AOE网中，从源点到汇点各活动时间总和最长的路径为（）。

三、简答题

1、对于一个具有n个顶点的连通无向图，如果它有且只有一个简单回路，

此图有几条边？一个具有n个顶点的弱连通图至少有几条边？

2、已知某图的邻接表，如何建立该图的邻接矩阵？

3、有4个顶点A，B，C，D的无向连通图，按广度和深度搜索遍历结果都

为ABCD，画出所有可能的结构图？

4、简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操

作中有什么优越性？

5、什么是AOE网的关键路径？

6、给出下图邻接矩阵、邻接表和邻接多重表存储结构。从顶点1出发进行

广度个深度优先搜索遍历。

7、对下图，请给出（1）对应的邻接矩阵，并给出v1,v2,v3三个顶点的出

度和入度；（2）邻接表和逆邻接表表示；（3）强连通分量。

8、试列出图中全部可能的拓扑排序序列。

答案：

1 2 3 4 5 6 7 8

C A B A

D C D A

9 10 11 12 13 14 15 16

D AG C DB B D CB B

17 18 19 20 21 22 23 24

A CD

B A B A D

C B

1 n-1 9 出度数，度数

2 2e 10 V1v2v3v6v5v4,v1v2v5v4v3v6

3 任意多个11 N(n-1),n-1

4 4 12 等于1

5 0,n(n-1)/2,0,n(n-1),n(n-1)/2,n(n-

1) 13 无环，前驱，所有以它为尾的

弧

6 1,0 14 生成树

7 1 15 关键路径

8 求矩阵第I列非零元素之和

三、简答题

1、（1）n条边（2）n-1条边

2、根据邻接表中表向量的大小确定邻接矩阵的行列数；由第I个顶点指向

的单链表中结点j来确定邻接矩阵中第I行j列元素为1，其余为0。

3、略

4、图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。

借助于邻接矩阵容易判断任意两个顶点是否有边/弧相连，并容易求出顶点的度。对无向图，顶点vi的度是邻接矩阵中第I行或第j列的元素之和；

对有向图，第I行的元素之和为顶点vi的出度，第j列的元素之和为顶点vj 的入度。

在无向图的邻接表中，第I个链表中表结点个数恰好为顶点vi的度；而在有向图中，第I个链表中表结点个数只是顶点vi的出度。

利用十字链表容易求得顶点的出度和入度。

邻接多重表适合于对边进行操作，如在遍历时对边作记号或在拓扑排序中对边进行删除。

5、在AOE网中完成工程的最短时间是从开始点到完成点的最长路径的长度，这条路径长度最长的路径叫关键路径。

后面题答案略。

《数据结构》习题汇编07 第七章 图 试题

第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。

数据结构第七章图

数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题：

数据结构第7章 图习题

第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。

A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量

数据结构第七章图练习及答案

1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧表示，持续时间记为dut，则有下式成立 e(i)=ve(j) l(i)=vl(k)-dut() （4）找出e(i)-l(i)=0的活动既是关键活动。 【答案】

关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）

数据结构第七章图练习及答案

数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧表示，持续时间记为dut，则有下式成立 e(i)=ve(j) l(i)=vl(k)-dut()

(4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径

机械制图图样表达法试题

《机械制图》课程试题库 第六章机械图样的基本表示方法 一、填空题 ★1、按剖切范围分，剖视图可分为、和 三类。 *2、断面图分为：和两种。 3、同一零件各剖视图的剖面线方向间隔 *4、六个基本视图的名称 为：。 二、选择题 ★1、下列局部剖视图中，正确的画法是。 A B C D ★2、下列四组视图中，主视图均为全剖视图，其中的主视图有缺漏的线。

A B C. D *3、在半剖视图中，剖视图部分与视图部分的分界线为： A.、细点画线 B 粗实 线、 C、双点画线 4、重合剖面的轮廓线都是用 A.、细点画线绘制 B 、粗实线绘 制 C 、细点画线绘制 5、当需要表示位于剖切平面前的结构时，这些结构按假想投影的轮廓线用： A.、细点画线 B、粗实线、 C、双点画线 三、判断题 ★1、非回转体类零件的主视图一般应选择工作位置。（v ） 2、在剖视图中，切根线用细实线绘制。（x） 四、画图题

★1、用单一剖切面，将主视图画成全剖视图。（20分） 3、用单一剖切面，将主视图画成全剖视图。（20分） 4、用单一剖切面，将主视图画成全剖视图。（20分）

★4、将物体的主视图改画成剖视图。（20分）

★5、在轴的小孔及键槽处，画移出断面图。（15分） ★6、在指定位置画出断面图并标记。（10分）

7、在指定位置画出断面图并标记。（10分） 8、在轴的指定位置作剖面图（A处键槽深为4mm，C处键槽宽为8mm。） （15分） 第七章机械图样中的特殊表示法 一、填空题 ★1、内外螺纹只有当_牙型_；_公称直径_；_螺距___；__线数______；___旋向_____等五要素完全相同时，才能旋合在一起。

数据结构第7章 图习题

习题7 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e 10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b

数据结构第七章图练习及答案

一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、B、1C、2D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、B、1C、2D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、n D、n*n

11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1C、n-1D、n+e (2)A、e/2B、e C、2eD、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀罕图G，则G采用（邻接表）存储较省空间。 3、设有一粘稠图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I行）。

第七章 零件图 习题答案

第七章 零件图
第一章 制图基本知识 第二章 正投影法基础 第三章 换面法 第四章 组合体 1. 组合体视图的画法 2. 平面与回转面的交线
3. 两回转面的交线
4. 组合体视图及其尺寸注法 5. 读组合体视图 第五章 轴测图 第六章 机件形状的基本表示 方法 1. 视图、剖视 2. 断面、简化画法 第七章 零件图 第八章 常用标准件和齿轮、 弹簧表示法 第九章 装配图
P 60
P 61
P 62
P 63
P 64
P 65
P 66
P 67
首 页
下一页

极限与配合、形状和位置公差
第一章 制图基本知识 第二章 正投影法基础 第三章 换面法 第四章 组合体 1. 组合体视图的画法 2. 平面与回转面的交线
3. 两回转面的交线
4. 组合体视图及其尺寸注法 5. 读组合体视图 第五章 轴测图 第六章 机件形状的基本表示 方法 1. 视图、剖视 2. 断面、简化画法 第七章 零件图 第八章 常用标准件和齿轮、 弹簧表示法 第九章 装配图
首 页
下页题
答 案
P60

极限与配合、形状和位置公差
第一章 制图基本知识 第二章 正投影法基础 第三章 换面法 第四章 组合体 1. 组合体视图的画法 2. 平面与回转面的交线
3. 两回转面的交线
4. 组合体视图及其尺寸注法 5. 读组合体视图 第五章 轴测图 第六章 机件形状的基本表示 方法 1. 视图、剖视 2. 断面、简化画法 第七章 零件图 第八章 常用标准件和齿轮、 弹簧表示法 第九章 装配图
首 页
题 目
下页题
返 回
P60

数据结构第7章 图习题

习题7 图 7.1 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ②A. e/2 B. e C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ②A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。