数据结构练习(答案)-8&9

第8章图一、单项选择题1.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(A)。A．sB．s-1C．s+1D．n2.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（D）。A．nB．eC．n+eD．2e3.在一个具有n个顶点的无向完全图中，所含的边数为（C）。A．nB．n(n-1)C．n(n-1)/2D．n(n+1)/24.在一个具有n个顶点的有向完全图中，所含的边数为（B）。A．nB．n(n-1)C．n(n-1)/2D．n(n+1)/25.在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（B）。A．kB．k+1C．k+2D．2k6.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（B）。A．0B．1C．nD．n+17.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（A）次深度优先搜索遍历的算法。A．kB．1C．k-1D．k+18.若要把n个顶点连接为一个连通图，则至少需要（C）条边。A．nB．n+1C．n-1D．2n9.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（D）。A．nB．neC．eD．2e10.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为（C）。A．nB．neC．eD．2e11.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（D）。A．nB．neC．eD．2e12.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（A）。A．nB．2nC．eD．2e13.在一个无权图的邻接表表示中，每个边结点至少包含（B）域。A．1B．2C．3D．414.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（B）。A．k1B．k2C．k1-k2D．k1+k215.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为（C）。A．k1B．k2C．k1-k2D．k1+k216.对于一个无向图，下面（A）说法是正确的。A．每个顶点的入度等于出度B．每个顶点的度等于其入度与出度之和C．每个顶点的入度为0D．每个顶点的出度为017.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（A）。A．出边数B．入边数C．度数D．度数减118.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（B）。A．A,B,C,F,D,EB．A,C,F,D,E,BC．A,B,D,C,F,ED．A,B,D,F,E,C19.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（D）。A．A,B,C,D,E,FB．A,B,C,F,D,EC．A,B,D,C,E,FD．A,C,B,F,D,E20.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（A）。A．1,2,5,4,3B．1,2,3,4,5C．1,2,5,3,4D．1,4,3,2,521.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（C）。A．1,2,3,4,5B．1,2,4,3,5C．1,2,4,5,3D．1,4,2,5,322.由一个具有n个顶点的连通图生成的最小生成树中，具有（B）条边。A．nB．n-1C．n+1D．2n23.已知一个有向图的边集为{a,b,a,c,a,d,b,d,b,e,d,e}，则由该图产生的一种可能的拓扑序列为（A）。A．a,b,c,d,eB．a,b,d,e,bC．a,c,b,e,dD．a,c,d,b,e二、填空题1.在一个图中，所有顶点的度数之和等于所有边数的2倍。2.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。3.假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为-2-{a,c,a,e,c,f,d,c,e,b,e,d}，则出度为0的顶点个数为2，入度为1的顶点个数为4。4.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要n-1条边。5.表示图的三种种存储结构为邻接矩阵、邻接表和邻接多重表。6.在一个连通图中存在着1个连通分量。7.图中的一条路径长度为k，该路径所含的顶点数为k+1。8.若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有3个连通分量。9.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为nn。10.对于具有n个顶点和e条边的无向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为n和2e。11.对于具有n个顶点和e条边的有向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为n和e。12.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有出边和入边结点。13.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为O(n)和O(e)。14.假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为O(n2)和O(n+2e)。15.图的深度优先搜索遍历算法是一种递归算法，图的广度优先搜索遍历算法需要使用队列。16.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为n和n-1。17.若一个连通图中每个边上的权值均不同，则得到的最小生成树是唯一（唯一/不唯一）的。根据图的存储结构进行某种次序的遍历，得到的顶点序列是不唯一（唯一/不唯一）的。18.假定一个有向图的边集为{a,c,a,e,c,f,d,c,e,b,e,d}，对该图进行拓扑排序得到的顶点序列为aebdcf。三、应用题1.对于一个无向图，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。解答：深度优先搜索序列：0,2,3,5,6,1,4广度优先搜索序列：0,2,3,5,6,1,42.对于一个有向图，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。解答：深度优先搜索序列：0,3,6,4,1,5,2广度优先搜索序列：0,3,2,6,5,4,13.已知下图所示的一个网，（1）按照Prim方法，从顶点1出发，求该网的最小生成树的产生过程。（2）按照Kruskal方法，求该网的最小生成树的产生过程。解答：（1）V1V2V3V4V5V6V750(b)V1V2V3V4V5V6V7(a)V1V2V3V4V5V6V760506540457050524230-3-（2）4.下图所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0到其余各顶点的最短路径。解答：终点从v0到各终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5V1∞∞∞∞∞无V210(v0,v2)V3∞60(v0,v2,v3)50(v0,v4,v3)V430(v0,v4)30(v0,v4)V5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)VjV2V4V3V5S{v0,v2}{v0,v2,v4}{v0,v2,v3,v4}{v0,v2,v3,v4,v5}5.上图给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞(b)带权邻接矩阵(a)有向带权图V1V0V5V4V3V25106030100502010V1V2V3V4V5V6V7(g)304042455050V1V2V3V4V5V6V7(e)30404245V1V2V3V4V5V6V7(c)3040V1V2V3V4V5V6V7(a)V1V2V3V4V5V6V7(f)3040424550V1V2V3V4V5V6V7(d)304042V1V2V3V4V5V6V7(b)30V1V2V3V4V5V6V7504045504230(g)V1V2V3V4V5V6V75040504230(f)V1V2V3V4V5V6V750405030(e)V1V2V3V4V5V6V7504050(d)V1V2V3V4V5V6V75040(c)-4-解答：①事件的最早发生时间ve[k]：ve(1)=0ve(2)=3ve(3)=4ve(4)=ve(2)+2=5ve(5)=max{ve(2)+1,ve(3)+3}=7ve(6)=ve(3)+5=9ve(7)=max{ve(4)+6,ve(5)+8}=15ve(8)=ve(5)+4=11ve(9)=max{ve(8)+10,ve(6)+2}=21ve(10)=max{ve(8)+4,ve(9)+1}=22ve(11)=max{ve(7)+7,ve(10)+6}=28②事件的最迟发生时间vl[k]：vl(11)=ve(11)=28vl(10)=vl(11)–6=22vl(9)=vl(10)–1=21vl(8)=min{vl(10)-4,vl(9)-10}=11vl(7)=vl(11)–7=21vl(6)=vl(9)–2=19vl(5)=min{vl(7)-8,vl(8)-4}=7vl(4)=vl(7)–6=15vl(3)=min{vl(5)-3,vl(6)-5}=4vl(2)=min{vl(4)-2,vl(5)-1}=6vl(1)=min{vl(2)-3,vl(3)-4}=0③活动ai的最早开始时间e[i]和最晚开始时间l[i]：活动a1：e(1)=ve(1)=0l(1)=vl(2)–3=3活动a2：e(2)=ve(1)=0l(2)=vl(3)–4=0活动a3：e(3)=ve(2)=3l(3)=vl(4)–2=13活动a4：e(4)=ve(2)=3l(4)=vl(5)–1=6活动a5：e(5)=ve(3)=4l(5)=vl(5)–3=4活动a6：e(6)=ve(3)=4l(6)=vl(6)–5=14活动a7：e(7)=ve(4)=5l(7)=vl(7)–6=15活动a8：e(8)=ve(5)=7l(8)=vl(7)–8=13活动a9：e(9)=ve(5)=7l(9)=vl(8)–4=7活动a10：e(10)=ve(6)=9l(10)=vl(9)–2=19活动a11：e(11)=ve(7)=15l(11)=vl(11)–7=21活动a12：e(12)=ve(8)=11l(12)=vl(10)–4=18活动a13：e(13)=ve(8)=11l(13)=vl(9)–10=11活动a14：e(14)=ve(9)=21l(14)=vl(10)-1=21活动a15：e(15)=ve(10)=22l(15)=vl(11)-6=22④最后，比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如下图所示。第9章排序一、单项选择题1.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（D）。A．j-iB．i-j-1C．i-jD．i-j+12.若对n