第7章自测空题new--数据结构课件(吴伟民-严蔚敏编著)

《第7章自测空题new--数据结构课件(吴伟民-严蔚敏编著)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图自测卷姓名班级题号一二三四五总分题分1620241030100得分一、单选题（每题1分，共16分）（）1.在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2B.1C.2D.4（）2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B.1C.2D.4（）3.有8个结点的无向图最多有条边。A．14B.28C.56D.112（）4.有8个结点的无向连通图最少有条边。A．5B.6C.7D.8（）5.有8个结点的有向完全图有条边。A．14B.28C.56D.112（）6.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.

2、树D.图（）7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.树D.图A．0243156B.0136542C.0423165D.0361542（）8.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（）9.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A．0243156B.0135642C.0423165D.0134256（）10.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243651B.0136425C.0423156D.0134256（）11.已

3、知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243165B.0135642C.0123465D.01234565（）12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是A．0132B.0231C.0321D.0123（）13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A．0321B.0123C.0132D.0312（）14.深度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（）15.广度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历

4、（）16.任何一个无向连通图的最小生成树A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在二、填空题（每空1分，共20分）1.图有、等存储结构，遍历图有、等方法。2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。3.如果n个顶点的图是一个环，则它有棵生成树。4.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为。5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为。6.设有一稀疏图G，则G采用存储较省空间。7.设有一稠密图G，则G采用存储较省空间。8.图的逆邻接表存储结构只适用于图。9.已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是。1

5、0.图的深度优先遍历序列惟一的。511.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为。12.n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为。13.图的BFS生成树的树高比DFS生成树的树高。14.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为；用克鲁斯卡尔(Kruskal)算法的时间复杂度是。15.若要求一个稀疏图G的最小生成树，最好用算法来求解。16.若要求一个稠密图G的最小生成树，最好用算法来求解。17.用Dijkstra

6、算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。18.拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。三、简答题（每题6分，共24分）1.【严题集7.1①】已知如图所示的有向图，请给出该图的:顶点123456入度出度（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。2.【严题集7.7②】请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。53.【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度

7、优先生成树和广度优先生成树。4.【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。四、给定下列网G:（10分）1试着找出网G的最小生成树，画出其逻辑结构图；2用两种不同的表示法画出网G的存储结构图；3用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。五、算法设计题（每题10分，共30分）1.【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。解：StatusBuil