第7章自测题详细版.docx

《第7章自测题详细版.docx》由会员分享，可在线阅读，更多相关《第7章自测题详细版.docx（5页珍藏版）》请在第一文库网上搜索。

1、第七章图一、 填空题1 .假设顶点的偶对是有序的，此图为 图；假设顶点偶对是无序的，此图为图。有向，无向）2 .设x, y WV,假设x, yE,那么x, y表示有向图G中从x到y的一条, x称为点,y称为 点。假设（x, y） eE,那么在无向图G中x和y间有一条。弧（或有向边），初始，终端，关联边）3 .在无向图中，假设顶点x与y间有边（x,y）,那么x与y互称 ，边（x, y）称为与顶点x和y o （邻接点，相关联）4 . 一个具有n个顶点的完全无向图的边数为 o 一个具有n个顶点的完全有向图的弧度数为 o （n*（n-l）/2, n*（n-D）5 .图的边或弧附带的数值叫 o每条边或弧

2、都带权的图称为 o （权，网络）6 .无向图中的顶点V的度是 o假设G是一个有向图，那么把以顶点V为终点的弧的数目称为V的；把以顶点V为始点的弧的数目称为V的 o （和V相关联的边的数目，入度，出度）7 .路径长度定义为 o第一个顶点和最后一个顶点一样的路径称为 或。序列中顶点不重复出现的路径称为。除了第一个顶点和最后一个顶点外,其余顶点不重复的回路，称为O （路径上边或弧的数目，回路，环，简单路径，简单回路）8 .在无向图中，如果从顶点v到顶点V，有路径，那么称v和V，是 的。如果对于图中的任意两个顶点v“VjV, H和力都是连通的，那么称G为 o （连通，连通图）9 .连通分量是无向图中的

3、 连通子图。（极大10 . 一个连通图的生成树是含有该连通图的全部顶点的一个 o （极小连通子图）11 .假设连通图G的顶点个数为n,那么G的生成树的边数为 o （n-1）12 .图的存储构造主要有 和 两种。（邻接矩阵，邻接表）13 .无向图的邻接矩阵是一个 矩阵，有向图的邻接矩阵不一定是 矩阵。（对称，对称）14 .对于无向图的邻接矩阵，顶点vi的度是 对于有向图的邻接矩阵，顶点vi的出度OD（vi）为,顶点vi的入度ID（vi）是 o第i行或第i列中1的个数，第i行1的个数，第i列1的个数）15 .邻接表表示法是借助 来反映顶点间的邻接关系,所以称这个单链表为邻接表。（每个顶点的各邻接点

4、所构成的单链表）16 .对无向图，假设它有n个顶点和e条边，那么其邻接表中需要个结点。其中，个结点构成邻接表，个结点构成顶点表。（n+2e, 2e, n）17 .对有向图，假设它有n个顶点和e条边，那么其邻接表中需要 个结点。其中，个结点构成邻接表，个结点构成顶点表。（n+e, e, n）18 .在邻接表上，无向图中顶点vi的度恰为 o对有向图，顶点vi的出度是。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为 的结点的个数是顶点Vi的入度。（vi的邻接表长度，vi的邻接表长度，vi）19 .遍历图的根本方法有 优先搜索和 优先搜索两种。深度，广度）20 . 一个有向图G中假设

5、有弧Vi, V、Vj, V，和孔,那么在图G的拓扑序列中，顶点5、%和Vk的相对位置为。（匕、八二、单项选择题1 . 一个无向连通网络的最小生成树（）只有一棵有一棵或多棵一定有多棵可能不存在2 .含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）1n/2n-1 n3 .在无向图中，所有顶点的度数之和是所有边数的（）倍。0.51244 .在有向图中，所有顶点的入度之和是所有顶点出度之和的（）倍。0.51245 .以下说法正确的选项是（）连通图的生成树，是该连通图的一个极小连通子图。无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。任何一个有向图，其全部顶点可以排成一个拓扑序列。

6、在一个有向图的拓扑序列中，假设顶点a在顶点b之前，那么图中必有一条弧a,b。6 . 以 下 说 法 错 误 的 选 项 是（）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角局部就可以了用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，那么只要检查A的第i行第j列的元素是否为0即可。三、简答及应用1、假设某有向图共有5个节点v0-v4,它的邻接矩阵如下:1 00 00

7、 00 10 JL0 1 00 0 10 0 00 0 10 0 1试写出该有向图的两个拓扑序列。2、以下图表示一个地区的通信网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的1条线路，即求该图的最小生成树，试分别用Prim算法和Kruskal算法求该图的最小生成树，要求给出过程和最后结果。3、如以下图所示的有向图，请给出该图的：（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。4、二维数组表示的图的邻接矩阵如以下图所示。试分别画出自顶点1出发进展遍历所得的深度优先生成树和广度优先生成树。1234567891010000001

8、01020010001000300010001004000010001050000010001611000000007001000000181001000010900001010011010000100005、试利用Dijkstra算法求以下图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。6.一有向带权图的邻接矩阵如下:Viv2V3v4V、V6v7v8V,002300000000cov20000004000000coV3co00co310Vco00v4co000000004co00v50000000000003cov6CO0000002COCO6v7000000000000001v8co00000000coco00以匕为源点，以Vs为汇点，求出所有的关键路径。