第五章图习题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第五章 图,一、填空题,设无向图,G,中顶点数为,n,，则图,G,至少有（）条边，至多有（）条边；若,G,为有向图，则至少有（）条边，至多有（）条边解答,】0,，,n(n-1)/2,，,0,，,n(n-1),【,分析,】,图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边任何连通图的连通分量只有一个，即是（）解答,】,其自身,图的存储结构主要有两种，分别是（）和（）解答,】,邻接矩阵，邻接表,【,分析,】,这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等已知一个有向图的邻接矩阵表示，计算第,j,个顶点的入度的方法是（）解答,】,求第,j,列的所有元素,1,个数之和,有向图,G,用邻接矩阵,Ann,存储，其第,i,行的所有元素之和等于顶点,i,的（）解答,】,出度,如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列解答,】,回路,在一个有向图中，若存在弧,、,、,，则在其拓扑序列中，顶点,vi,vj,vk,的相对次序为（）。

解答,】vi,vj,vk,【,分析,】,对由顶点,vi,vj,vk,组成的图进行拓扑排序二、选择题,在一个无向图中，所有顶点的度数之和等于所有边数的（）倍A 1/2 B 1 C 2 D 4,【,解答,】C,【,分析,】,设无向图中含有,n,个顶点,e,条边，则 n,个顶点的强连通图至少有（）条边，其形状是（）A n B n+1 C n-1 D n(n-1)E,无回路,F,有回路,G,环状,H,树状,【,解答,】A,，,G,含,n,个顶点的连通图中的任意一条简单路径，其长度不可能超过（）A 1 B n/2 C n-1 D n,【,解答,】C,【,分析,】,若超过,n-1,，则路径中必存在重复的顶点对于一个具有,n,个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）A n B(n-1),2,C n-1 D n,2,【,解答,】D,图的生成树（），,n,个顶点的生成树有（）条边A,唯一,B,不唯一,C,唯一性不能确定,D n E n+1 F n-1,【,解答,】C,，,F,设无向图,G=(V,E),和,G=(V,E),，如果,G,是,G,的生成树，则下面的说法中错误的是（）A G,为,G,的子图,B G,为,G,的连通分量,C G,为,G,的极小连通子图且,V=V D G,是,G,的一个无环子图,【,解答,】B,【,分析,】,连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。

G,是一个非连通无向图，共有,28,条边，则该图至少有（）个顶点A 6 B 7 C 8 D 9,【,解答,】D,【,分析,】n,个顶点的无向图中，边数,en(n-1)/2,，将,e=28,代入，有,n8,，现已知无向图非连通，则,n=9,最小生成树指的是（）A,由连通网所得到的边数最少的生成树,B,由连通网所得到的顶点数相对较少的生成树,C,连通网中所有生成树中权值之和为最小的生成树,D,连通网的极小连通子图,【,解答,】C,某无向图的邻接矩阵,A=,，可以看出，该图共有（）个顶点A 3 B 6 C 9 D,以上答案均不正确,【,解答,】A,无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）,A,上三角矩阵,B,下三角矩阵,C,对称矩阵,D,无规律,【,解答,】C,，,D,下列命题正确的是（）A,一个图的邻接矩阵表示是唯一的，邻接表表示也唯一,B,一个图的邻接矩阵表示是唯一的，邻接表表示不唯一,C,一个图的邻接矩阵表示不唯一的，邻接表表示是唯一,D,一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一,【,解答,】B,在一个具有,n,个顶点的有向完全图中包含有（）条边：,A n(n-1)/2 B n(n-1)C n(n+1)/2 D n,2,【,解答,】B,三、判断题,一个有向图的邻接表和逆邻接表中的结点个数一定相等,【,解答,】,对。

邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中结点的个数图,G,的生成树是该图的一个极小连通子图,【,解答,】,错必须包含全部顶点无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的,【,解答,】,错有向图的邻接矩阵不一定对称，例如有向完全图的邻接矩阵就是对称的对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点解答,】,错只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点在一个有向图的拓扑序列中，若顶点,a,在顶点,b,之前，则图中必有一条弧解答,】,错只能说明从顶点,a,到顶点,b,有一条路径若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在解答,】,对四、已知一个连通图如图所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点,v1,出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列解答,】,邻接矩阵表示如下：,深度优先遍历序列为：,v1 v2 v3 v5 v4 v6,广度优先遍历序列为：,v1 v2 v4 v6 v3 v5,邻接表表示如下：,五、如图所示是一个无向带权图，请分别按,Prim,算法和,Kruskal,算法求最小生成树。

解答,】,按,Prim,算法求最小生成树的过程如下：,按,Kruskal,算法求最小生成树的过程如下：,六、对于如图所示的带权有向图，求从源点,v1,到其他各顶点的最短路径解答,】,从源点,v1,到其他各顶点的最短路径如下表所示源点 终点 最短路径 最短路径长度,v1 v7 v1v7 7v1 v5 v1v5 11v1 v4 v1v7v4 13v1 v6 v1v7v4v6 16v1 v2 v1v7v2 22v1 v3 v1v7v4v6v3 25,七、如图所示的有向网图，利用,Dijkstra,算法求从顶点,v1,到其他各顶点的最短路径解答,】,从源点,v1,到其他各顶点的最短路径如下表所示源点 终点 最短路径 最短路径长度,v1 v3 v1v3 15v1 v5 v1v5 15v1 v2 v1v3v2 25v1 v6 v1v3v2v6 40v1 v4 v1v3v2v4 45,八、已知无向图,G,的邻接表如图所示，分别写出从顶点,1,出发的深度遍历和广度遍历序列，并画出相应的生成树解答,】,深度优先遍历序列为：,1,，,2,，,3,，,4,，,5,，,6,对应的生成树为：,广度优先遍历序列为：,1,，,2,，,4,，,3,，,5,，,6,对应的生成树为：,九、已知已个,AOV,网如图所示，写出所有拓扑序列。

解答,】,拓扑序列为：,v0 v1 v5 v2 v3 v6 v4,、,v0 v1 v5 v2 v6 v3 v4,、,v0 v1 v5 v6 v2 v3 v4,第六章 排序,一、填空题,排序的主要目的是为了以后对已排序的数据元素进行（）解答,】,查找,【,分析,】,对已排序的记录序列进行查找通常能提高查找效率对,n,个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）在（）情况下比较次数最多，其比较次数为（）解答,】,正序，,n-1,，反序，,n(n-1)/2,对一组记录（,54,38,96,23,15,72,60,45,83,）进行直接插入排序，当把第,7,个记录,60,插入到有序表时，为寻找插入位置需比较（）次解答,】3,【,分析,】,当把第,7,个记录,60,插入到有序表时，该有序表中有,2,个记录大于,60,利用简单选择排序对,n,个记录进行排序，最坏情况下，记录交换的次数为（）解答,】n-1,如果要将序列（,50,，,16,，,23,，,68,，,94,，,70,，,73,）建成堆，只需把,16,与（）交换解答,】50,评价基于比较的排序算法的时间性能，主要标准是（）和（）。

解答,】,关键码的比较次数，记录的移动次数,对,n,个记录组成的任意序列进行简单选择排序，所需进行的关键码间的比较次数总共为（）解答,】,比较次数,=(n-1)+(n-2)+2+1=n(n-1)/2,二、选择题,下列序列中，（）是执行第一趟快速排序的结果A da,，,ax,，,eb,，,de,，,bb ff ha,，,gc B cd,，,eb,，,ax,，,da ff ha,，,gc,，,bbC gc,，,ax,，,eb,，,cd,，,bb ff da,，,ha D ax,，,bb,，,cd,，,da ff eb,，,gc,，,ha【,解答,】,A【,分析,】,此题需要按字典序比较，前半区间中的所有元素都应小于,ff,，,后半区间中的所有元素都应大于,ff,堆的形状是一棵（）A,二叉排序树,B,满二叉树,C,完全二叉树,D,判定树,【,解答,】C【,分析,】,从逻辑结构的角度来看，堆实际上是一种完全二叉树的结构对数列（,25,84,21,47,15,27,68,35,20,）进行排序，元素序列的变化情况如下：,25,84,21,47,15,27,68,35,20 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84,则采用的排序方法是（）。

A,希尔排序,B,简单选择排序,C,快速排序,D,归并排序,【,解答,】C,三、判断题,如果某种排序算法是不稳定的，则该排序方法没有实际应用价值解答,】,错一种排序算法适合于某种特定的数据环境，有时对排序的稳定性没有要求当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素解答,】,对此时着重考虑元素的移动次数堆排序所需的时间与待排序的记录个数无关解答,】,错堆排序最好、最坏及平均时间均为,(nlog2n),，是待排序的记录个数,n,的函数一般来说，待排序的记录个数越多，排序所消耗的时间也就越多四、已知数据序列为,(12,，,5,，,9,，,20,，,6,，,31,，,24),，对该数据序列进行排序，写出插入排序、起泡排序、快速排序、简单选择排序、堆排序每趟的结果解答,】,用上述排序方法的每趟结果如下：,五、判别下列序列是否为堆，如不是，按照堆排序思想把它调整为堆，用图表示建堆的过程1,，,5,，,7,，,25,，,21,，,8,，,8,，,42,）（,3,，,9,，,5,，,8,，,4,，,17,，,21,，,6,）,【,解答,】,序列是堆，序列不是堆，调整为堆（假设为大根堆）的过程如图所示。