第6章 图习题解析.doc

第六章 图习题解析1 一、选择题 1、设无向图的顶点个数为n，则该无向图最多有? ?B ????条边。 ??? A、n-1???????? B、n（n-1）/2??????? C、n（n+1）/2 D、0?????????? E、n2 ?2、在下列两种求图的最小生成树的算法中，B 算法适合于求边稀疏的网的最小生成树。 A、Prim????????????? B、Kruskal ?3、下面的叙述中不正确的是? ?B ????。 A、关键活动不按期完成就会影响整个工程的完成时间 B、任何一个关键活动提前完成，将使整个工程提前完成 C、所有关键活动都提前完成，则整个工程将提前完成 D、某些关键活动若提前完成，将使整个工程提前完成 ?4、采用邻接表存储的图，其深度优先遍历类似于二叉树的?? ?B? ??。 A、中序遍历?????????????? B、先序遍历 C、后序遍历?????????????? D、按层次遍历 ?5、采用邻接表存储的图，其广度优先遍历类似于二叉树的??? A??? 。 A、按层次遍历??????B、中序遍历 C、后序遍历??????????? D、先序遍历 ?6、具有n个顶点的有向图最多有? ?B? ???条边。 ??? A、n?????? B、n（n-1）????? C、n（n+1）???? D、n2 ?7、一个n个顶点的连通无向图，其边的个数至少为 ??A? ???。 ??? A、n-1????? B、n??????????? C、n+1????????? D、nlog2n 8、下列说法中，正确的有?? ?C ???。 A、最小生成树也是哈夫曼树 B、最小生成树唯一 C、普里姆最小生成树算法时间复杂度为O（n2） D、克鲁斯卡尔最小生成树算法普里姆算法更适合与边稠密的网。 10、判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用?? C ?。 ??? A、求关键路径的方法????? B、求最短路径的Dijkstra方法 C、深度优先遍历算法????? D、广度优先遍历算法 ?11、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为?? ?A??? 。 ???? A、s??????? B、s-1?????? C、s+1?????? D、n ?12、在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为?? B ??。 ??? A、k??????? B、k+1????? C、k+2?????? D、2k ?13、一个有n个顶点的无向连通图，它所包含的连通分量个数为?? B ????。 ??? A、0??????? B、1???????? C、n??????? D、n+1 14、对于一个有向图，若一个顶点的入度为k1、出度k2，则对应邻接表中该顶点单链表中的结点数为?? B???? 。 ??? A、k1????? B、k2???? C、k1-k2? ????D、k1+k2 15、对于一个有向图，若一个顶点的入度为k1、出度k2，则对应逆邻接表中该顶点单链表中的结点数为? ?A? ???。 ??? A、k1????? B、k2???? C、k1-k2????? D、k1+k2 16、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用?? B 。 ??? A、顺序存储??????????? B、链式存储 C、索引存储??????????? D、散列存储 ?二、填空题 ?1、具有10个顶点的无向图，边的总数最多为? 45 。 ?2、在有n个顶点的有向图中，每个顶点的度最大可达 ?2（n-1） 。 ?3、克鲁斯卡尔算法的时间复杂度为? O（e·log2e） ,它对稀疏图较为适合。 ?4、若一个连通图中每个边上的权值均不同，则得到的最小生成树是? 唯一 ?的。 ?5、深度优先有哪些信誉好的足球投注网站遍历类似于树的? 前序? 遍历，它所用到的数据结构是? ?栈? ?；广度优先有哪些信誉好的足球投注网站遍历类似于树的? 按层次? 遍历，它所用到的数据结构是? 队列? 。 ?6、一个图的邻接矩阵? 表示法是唯一的，而? 邻接表 ?表示法是不唯一的。 ?7、对无向图，若它有n个顶点e条边，则其邻接表中需要 2e+n 个结点。其中， 2e ?个结点构成邻接表，? n 个结点构成顶点表。 ?三、判断题 ?1、在n个结点的无向图中，若边数n-1，则该图必是连通图。（错? ） ?2、任何AOV网拓扑排序的结果都是唯一的。（错?? ） ?3、有回路的图不能进行拓扑排序。（? 对? ） ?4、一个图的广度优先有哪些信誉好的足球投注网站使是唯一的。（? 错? ） ?5、图的深度优先有哪些信誉好的足球投注网站序列和广度优先有哪些信誉好的足球投注网站序列不是唯一的。（对?? ） 第六章图的习题解析2 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（