欢迎来到天天文库
浏览记录
ID:6596291
大小:158.54 KB
页数:8页
时间:2018-01-19
《第6章+图习题解析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第六章图习题解析1一、选择题1、设无向图的顶点个数为n,则该无向图最多有 条边。 A、n-1 B、n(n-1)/2 C、n(n+1)/2D、0 E、n2 2、在下列两种求图的最小生成树的算法中,算法适合于求边稀疏的网的最小生成树。A、Prim B、Kruskal 3、下面的叙述中不正确的是。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成,将使整个工程提前完成C、所有关键活动都提前完成,则整个工程将提前完成D、某些关键活动若提前完成,将使整个工程提前完成 4、采用邻接表存储的图,
2、其深度优先遍历类似于二叉树的。A、中序遍历 B、先序遍历C、后序遍历 D、按层次遍历 5、采用邻接表存储的图,其广度优先遍历类似于二叉树的 。A、按层次遍历 B、中序遍历C、后序遍历 D、先序遍历 6、具有n个顶点的有向图最多有条边。 A、n B、n(n-1) C、n(n+1) D、n2 7、一个n个顶点的连通无向图,其边的个数至少为 。 A、n-1 B、n C、n+1 D、nlog2n8、下列说法中,正确的有。A、最小生成树也是哈夫曼树B、最小生成树唯一C、
3、普里姆最小生成树算法时间复杂度为O(n2)D、克鲁斯卡尔最小生成树算法普里姆算法更适合与边稠密的网。10、判定一个有向图是否存在回路,除了可以利用拓扑排序的方法外,还可以利用 。 A、求关键路径的方法 B、求最短路径的Dijkstra方法C、深度优先遍历算法 D、广度优先遍历算法 11、在一个具有n个顶点的有向图中,若所有顶点的出度之和为s,则所有顶点的入度之和为。 A、s B、s-1 C、s+1 D、n 12、在一个无向图中,若两个顶点之间的路径长度为k,则该路径上的顶点数为 。 A、k B、k+1 C、
4、k+2 D、2k 13、一个有n个顶点的无向连通图,它所包含的连通分量个数为。 A、0 B、1 C、n D、n+114、对于一个有向图,若一个顶点的入度为k1、出度k2,则对应邻接表中该顶点单链表中的结点数为。 A、k1 B、k2 C、k1-k2 D、k1+k215、对于一个有向图,若一个顶点的入度为k1、出度k2,则对应逆邻接表中该顶点单链表中的结点数为。 A、k1 B、k2 C、k1-k2 D、k1+k216、为了方便地对图状结构的数据进行存取操作,则其中数据存储结构宜采用。
5、A、顺序存储 B、链式存储C、索引存储 D、散列存储 二、填空题 1、具有10个顶点的无向图,边的总数最多为 45。 2、在有n个顶点的有向图中,每个顶点的度最大可达 2(n-1)。 3、克鲁斯卡尔算法的时间复杂度为 O(e·log2e),它对稀疏图较为适合。 4、若一个连通图中每个边上的权值均不同,则得到的最小生成树是 唯一 的。 5、深度优先搜索遍历类似于树的 前序 遍历,它所用到的数据结构是 栈 ;广度优先搜索遍历类似于树的 按层次 遍历,它所用到的数据结构是 队列 。 6、一个图的邻接矩阵 表示法是唯一的,而 邻接表 表示法是不唯一的。 7、对无向
6、图,若它有n个顶点e条边,则其邻接表中需要2e+n个结点。其中,2e 个结点构成邻接表, n个结点构成顶点表。 三、判断题 1、在n个结点的无向图中,若边数>n-1,则该图必是连通图。(错 ) 2、任何AOV网拓扑排序的结果都是唯一的。(错 ) 3、有回路的图不能进行拓扑排序。( 对 ) 4、一个图的广度优先搜索使是唯一的。( 错 ) 5、图的深度优先搜索序列和广度优先搜索序列不是唯一的。(对 )第六章图的习题解析21.填空题⑴设无向图G中顶点数为n,则图G至少有(0)条边,至多有(n(n-1)/2)条边;若G为有向图,则至少有(0)条边,至多有(n(n-1))条边。⑵任何连通图的连
7、通分量只有一个,即是(其自身)。⑶图的存储结构主要有两种,分别是(邻接矩阵)和(邻接表)。⑷已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为(O(n+e))。⑸已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是(求第j列的所有元素之和)。⑹有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的(出度)。⑺图的深度优先遍历类似于树的(前序)遍历,它所用到的数据结构是(栈);图的广度优先遍历类似于
此文档下载收益归作者所有