图习题及参考答案.docx

《图习题及参考答案.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图习题及参考答案第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.正在一个无背图中，一切极点

2、的度数之以及即是一切边数的()倍。A.3B.2C.1D.1/27.若接纳毗邻矩阵法存储一个n个极点的无背图，则该毗邻矩阵是一个()。A.上3角矩阵B.密疏矩阵C.对于角矩阵D.对于称矩阵8.图的深度劣先搜刮相似于树的（）序次遍历。A.先根B.中根C.后根D.条理9.图的广度劣先搜刮相似于树的（）序次遍历。A.先根B.中根C.后根D.条理10.正在用Kruskal算法供解带权连通图的最小（价值）死成树时，取舍权值最小的边的本则是该边没有能正在图中形成（）。A.重边B.有背环C.回路D.权值反复的边11.正在用Dijkstra算法

3、供解带权有背图的最短途径成绩时，请求图中每一条边所带的权值必需是（）。A.非整B.非整C.非背D.非正12.设G1=(V1,E1)以及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)个极点的强连通图中最少露有（

4、）条有背边。A.n-1B.nn(n-1)/2D.n(n-1)16.正在一个带权连通图G中，权值最小的边必定包孕正在G的（）死成树中。A.某个最小B.任何最小C.广度劣先D.深度劣先17.对于于具备e条边的无背图，它的毗邻表中有（）个结面。A.e-1B.eC.2(e-1)D.2e18.对于于如图所示的带权有背图，从极点1到极点5的最短途径为（）。,4,5B.1,2,3,5C.1,4,3,5D.1,2,4,3,519.一个有n个极点以及n条边的无背图必定是（）。A.连通的B.没有连通的C.无环的D.有环的20.对于于有背图，其毗邻

5、矩阵暗示比毗邻表暗示更容易于（）。A.供一个极点的度B.供一个极点的毗邻面C.举行图的深度劣先遍历D.举行图的广度劣先遍历21.取毗邻矩阵比拟，毗邻表更合适于存储（）图。A.无背B.连通C.密疏D.稀稀图22.为了真现图的广度劣先遍历，BFS算法利用的一个帮助数据布局是（）。A.栈B.行列C.2叉树D.树2、挖空题1.用毗邻矩阵存储图，占用存储空间数取图中极点个数________闭，取边数________闭。2.n(n﹥0)个极点的无背图至多有________条边，至少有________条边。3.n(n﹥0)个极点的连通无背图

6、至少有________条边。4.若3个极点的图G的毗邻矩阵为??????????010001010，则图G必定是________背图。5.n(n﹥0)个极点的无背图中极点的度的最年夜值为________。6.(n﹥0)个极点的连通无背图的死成树最少有________条边。7.正在利用Kruskal算法机关连通收集的最小死成树时，只要当一条候选边的两个端面没有正在统一个________上，才有大概减进到死成树中。8.供解带权连通图最小死成树的Prim算法合适于________图的情况，而Kruskal算法合适于________图

7、的情况。3、判别题1.一个图的子图能够是空图，极点个数为0。2.存储图的毗邻矩阵中，矩阵元素个数没有但取图的极点个数无关，并且取图的边数也无关。3.对于一个连通图举行一次深度劣先搜刮（depthfirstsearch）能够遍访图中的一切极点。4.有n(n≥1)个极点的无背连通图至少有n-1条边。5.假如无背图中各个极点的度皆年夜于2，则该图中必有回路。6.假如有背图中各个极点的度皆年夜于2，则该图中必有回路。7.图的广度劣先搜刮（breadthfirstsearch）算法没有是递回算法。8.有n个极点、e条边的带权有背图的最小

8、死成树一样平常由n个极点以及n-1条边构成。9.对于于一个边上权值恣意的带权有背图，利用Dijkstra算法能够供一个极点到别的各个极点的最短途径。10.有回路的有背图没有能实现拓扑排序。11.对于任何用极点暗示举动的收集（AOV网）举行拓扑排序的了局皆是仅有的。12.用边暗