第7章图习题和参考答案解析

第7章图习题和参考答案解析

ID:27286658

大小:244.00 KB

页数:8页

时间:2018-12-02

第7章图习题和参考答案解析_第1页
第7章图习题和参考答案解析_第2页
第7章图习题和参考答案解析_第3页
第7章图习题和参考答案解析_第4页
第7章图习题和参考答案解析_第5页
资源描述:

《第7章图习题和参考答案解析》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、.WORD.格式.第7章习题一、单项选择题1.在无向图中定义顶点的度为与它相关联的()的数目。A.顶点B.边C.权D.权值2.在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个()。A.顶点序列B.边序列C.权值总和D.边的条数3.图的简单路径是指()不重复的路径。A.权值B.顶点C.边D.边与顶点均4.设无向图的顶点个数为n,则该图最多有()条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)5.n个顶点的连通图至少有()条边。A.n-1B.nC.n+1D.06.在一个无向图中,所有顶点的度数之和等于所有边数的()倍。A.3B.2C.1D.1/27

2、.若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个()。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵8.图的深度优先搜索类似于树的()次序遍历。A.先根B.中根C.后根D.层次9.图的广度优先搜索类似于树的()次序遍历。A.先根B.中根C.后根D.层次10.在用Kruskal算法求解带权连通图的最小(代价)生成树时,选择权值最小的边的原则是该边不能在图中构成()。A.重边B.有向环C.回路D.权值重复的边11.在用Dijkstra算法求解带权有向图的最短路径问题时,要求图中每条边所带的权值必须是()。A.非零B.非整C.非负D.非正12.设G1=(V1,E1)和

3、G2=(V2,E2)为两个图,如果V1ÍV2,E1ÍE2,则称()。A.G1是G2的子图B.G2是G1的子图C.G1是G2的连通分量D.G2是G1的连通分量13.有向图的一个顶点的度为该顶点的()。A.入度B.出度C.入度与出度之和D.(入度﹢出度))/214.一个连通图的生成树是包含图中所有顶点的一个()子图。A.极小B.连通C.极小连通D.无环15.n(n>1)个顶点的强连通图中至少含有()条有向边。A.n-1B.nn(n-1)/2D.n(n-1)16.在一个带权连通图G中,权值最小的边一定包含在G的()生成树中。A.某个最小B.任何最小C.广度优先D.深度优先17.对于具有

4、e条边的无向图,它的邻接表中有()个结点。A.e-1B.eC.2(e-1)D.2e18.对于如图所示的带权有向图,从顶点1到顶点5的最短路径为()。A.1,4,5B.1,2,3,5C.1,4,3,5D.1,2,4,3,512613819554123.专业资料.整理分享..WORD.格式.14.一个有n个顶点和n条边的无向图一定是()。A.连通的B.不连通的C.无环的D.有环的15.对于有向图,其邻接矩阵表示比邻接表表示更易于()。A.求一个顶点的度B.求一个顶点的邻接点C.进行图的深度优先遍历D.进行图的广度优先遍历16.与邻接矩阵相比,邻接表更适合于存储()图。A.无向B.连通

5、C.稀疏D.稠密图17.为了实现图的广度优先遍历,BFS算法使用的一个辅助数据结构是()。A.栈B.队列C.二叉树D.树二、填空题1.用邻接矩阵存储图,占用存储空间数与图中顶点个数________关,与边数________关。2.n(n﹥0)个顶点的无向图最多有________条边,最少有________条边。3.n(n﹥0)个顶点的连通无向图最少有________条边。4.若3个顶点的图G的邻接矩阵为,则图G一定是________向图。5.n(n﹥0)个顶点的无向图中顶点的度的最大值为________。6.(n﹥0)个顶点的连通无向图的生成树至少有________条边。7.在使

6、用Kruskal算法构造连通网络的最小生成树时,只有当一条候选边的两个端点不在同一个________上,才有可能加入到生成树中。8.求解带权连通图最小生成树的Prim算法适合于________图的情形,而Kruskal算法适合于________图的情形。三、判断题1.一个图的子图可以是空图,顶点个数为0。2.存储图的邻接矩阵中,矩阵元素个数不但与图的顶点个数有关,而且与图的边数也有关。3.对一个连通图进行一次深度优先搜索(depthfirstsearch)可以遍访图中的所有顶点。4.有n(n≥1)个顶点的无向连通图最少有n-1条边。5.如果无向图中各个顶点的度都大于2,则该图中必

7、有回路。6.如果有向图中各个顶点的度都大于2,则该图中必有回路。7.图的广度优先搜索(breadthfirstsearch)算法不是递归算法。8.有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。9.对于一个边上权值任意的带权有向图,使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。10.有回路的有向图不能完成拓扑排序。11.对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一的。12.用边表示活动的网络(AOE网)的关键路径是指

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。