数据结构七图.docxVIP

数据结构习题（图）一、选择题??? 1．设完全无向图的顶点个数为n，则该图有(?B )条边。??? 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.连通图??? 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条边的无向连通图，利用普里姆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个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。??? 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。??? 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。??? 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。??? 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。??? 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。??? 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。??? 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。三、简答题??? l．回答以下问题：??? (1)有n个顶点的无向连通图最多需要多少条边？最少需要多少条边？??? (2)表示一个具有1000个顶点、1000条边的无向图的邻接矩阵有多少个矩阵元素？有多少非零元素？是否为稀疏矩阵？??? 2．题图7-1为一有向图，按要求回答问题：??? (1)写出各顶点的入度、出度和度。??? (2)给出该图的邻接矩阵。??? (3)给出该图的邻接表。??? (4)给出该图的十字链表。3．题图7-2为一无向图，请按要求回答问题：??? (1)画出该图的邻接表。??? (2)画出该图的邻接多重表。??? (3)分别写出从顶点1出发按深度优先有哪些信誉好的足球投注网站遍历算法得到的顶点序列和按广度优先有哪些信誉好的足球投注网站? 遍历算法得到的顶点序列。???????????? 4．题图7-3为一带权无向图，请按要求回答问题。(1)??? 画出该图的邻接矩阵，并按普里姆算法求其最小生成树。(2)画出该图的邻接表，并按克鲁斯卡尔算法求其最小生成树。? 5．题图7-4是一带权有向图，试采用狄杰斯特拉Dijkstra算法求从顶点1到其他各项点的最短路径，要求给出整个计算过程。?? 6．题图7-5为一个带权有向图??? (1)给出该图的邻接矩阵。??? (2)请用弗洛伊德算法求出各顶点对之间的最短