数据结构 第七章图：习题

《数据结构 第七章图：习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章图：习题习   题一、选择题   1．设完全无向图的顶点个数为n，则该图有( )条边。   A.n-l   B.n(n-l)/2     C.n(n+l)/2   D.n(n-l)   2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。   A.3   B.2   C.1   D.1/2   3．有向图的一个顶点的度为该顶点的( )。   A.入度   B.出度   C.入度与出度之和   D.(入度+出度)/2   4．在无向图G(V，E)中，如果图中任意两个顶点vi、vj(vi、vj∈V，vi≠vj)都的，则称该图是( )。   A.强连通图   B

2、.连通图   C.非连通图   D.非强连通图   5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。   A.上三角矩阵   B.稀疏矩阵   C.对角矩阵   D.对称矩阵   6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵   A.第i列元素之和   B.第i行元素之和减去第i列元素之和   C.第i行元素之和   D.第i行元素之和加上第i列元素之和    7．对于具有e条边的无向图，它的邻接表中有( )个边结点。   A.e-l   B.e   C.2(e-l)   D.2e   8．对于含有n个顶点和e条边的

3、无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。   A.O(n2)   B.O(n*e)   C.O(n*logn)   D.O(e)   9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( )   A.n   B.n+l   C.n-l   D.n+e   10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。   A.最小   B.任何    C.广度优先   D.深度优先二、填空题   1．在一个具有n个顶点的无向完

4、全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。   2．对于无向图，顶点vi的度等于其邻接矩阵____的元素之和。   3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。   4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。   5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另

5、一种方法。   6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。   7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______，边数为_______。   8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。三、简答题   l．回答以下问题：   (1)有n个顶点的无向连通图最多需要多少条边？最少需要多少条边？   (2)表示一个具有1000个

6、顶点、1000条边的无向图的邻接矩阵有多少个矩阵元素？有多少非零元素？是否为稀疏矩阵？   2．题图7-1为一有向图，按要求回答问题：   (1)写出各顶点的入度、出度和度。   (2)给出该图的邻接矩阵。   (3)给出该图的邻接表。   (4)给出该图的十字链表。3．题图7-2为一无向图，请按要求回答问题：   (1)画出该图的邻接表。   (2)画出该图的邻接多重表。   (3)分别写出从顶点1出发按深度优先搜索遍历算法得到的顶点序列和按广度优先搜索 遍历算法得到的顶点序列。            4．题图7-3为一带权无向图，请按要求回答问题。(1)   画出该图

7、的邻接矩阵，并按普里姆算法求其最小生成树。(2)画出该图的邻接表，并按克鲁斯卡尔算法求其最小生成树。 5．题图7-4是一带权有向图，试采用狄杰斯特拉Dijkstra算法求从顶点1到其他各项点的最短路径，要求给出整个计算过程。  6．题图7-5为一个带权有向图   (1)给出该图的邻接矩阵。   (2)请用弗洛伊德算法求出各顶点对之间的最短路径长度，要求写出其相应的矩阵序列。   7．对于有向无环图，   (1)叙述求拓扑有序序列的步骤。   (2)对于题图7-6所示的有向图，写出它的4个不同的拓扑有序序列。   8．题图7-7