1、第六章图习题解析1一、选择题1、设无向图的顶点个数为n,则该无向图最多有 B 条边。 A、n-1 B、n(n-1)/2 C、n(n+1)/2D、0 E、n2 2、在下列两种求图的最小生成树的算法中,B算法适合于求边稀疏的网的最小生成树。A、Prim B、Kruskal 3、下面的叙述中不正确的是 B 。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成,将使整个工程提前完成C、所有关键活动都提前完成,则整个工程将提前
2、完成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个顶点
3、的连通无向图,其边的个数至少为 A 。 A、n-1 B、n C、n+1 D、nlog2n8、下列说法中,正确的有 C 。A、最小生成树也是哈夫曼树B、最小生成树唯一C、普里姆最小生成树算法时间复杂度为O(n2)D、克鲁斯卡尔最小生成树算法普里姆算法更适合与边稠密的网。10、判定一个有向图是否存在回路,除了可以利用拓扑排序的方法外,还可以利用 C 。 A、求关键路径的方法 B、求最短路径的Dijkstra方法C、深度优先遍历算法 D、广度优先遍历
4、算法 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+114、对于一个有向图,若一个顶点的
5、入度为k1、出度k2,则对应邻接表中该顶点单链表中的结点数为 B 。 A、k1 B、k2 C、k1-k2 D、k1+k215、对于一个有向图,若一个顶点的入度为k1、出度k2,则对应逆邻接表中该顶点单链表中的结点数为 A 。 A、k1 B、k2 C、k1-k2 D、k1+k216、为了方便地对图状结构的数据进行存取操作,则其中数据存储结构宜采用 B。 A、顺序存储 B、链式存储C、索引存储 D、散列存储 二、填空题