数据结构练习(标准答案)

第8章图一、单项选择题在个具有个顶点的有向图中，若所有顶点的出度数之和为s所顶点的度数之和(A)AB．CD．在个具有n个点的无向图中若有条，则所有顶点的度数之和为（DAnB．e．D在个具有个顶点的无向完全图中，所含的边数为（CAnBn(n-1)C．Dn(n+1)/2在个具有个顶点的有向完全图中，所含的边数为（AnB．n(n-1)n(n-1)/2D．在个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（BAkB．k+1C．k+2D．2k对一个具有个点无向连通图，它包含的连通分量的个数为（BA0B．．Dn+1若个图中包含有k个通分量，若要按照深度优先搜索的方法访问所有顶点须调A）次深度优先搜索遍历的算法。AkB．k-1Dk+1若把个点连接为一个连通图，则至少需要（）条边。AnB．．n-1D．在个具有n个点和e条的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（DAnB．n．D．210.在一个有个点条的有向图的邻接矩阵中，表示边存在的元素个数为（AnB．n．D．211.在一个有个点条的无向图的邻接表中，边结点的个数为（DAnB．n．D．212.在一个有个点条的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（AAnB．2nC．eD13.在一个权图的邻接表表示中，每个边结点至少包含（）域。A1B．．D14.对于一有向图，若一个顶点的度为，出度为

k2，对应邻表中该顶点单链表中的边结点数为（BAk1B．C．Dk1+k215.对一有向图，若一个顶点的度为k1出度为k2，对应逆接表中该顶点单链表中的边结点数为（Ak1B．CDk1+k216.对一无向图，下面（A）说法是正确的。A每个顶点的入度等于出度B每个顶点的度等于其入度与出度之和C．个顶点的入度为D．个顶点出度为017.在个向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（AA出边数B入边数．数D．度数减118.若个的边集{B),C),(B,(C,F),(D,E),F)}，从顶点A始对该图进行深度优先搜索，得到的顶点序列可能为（BAB,C,D,E．A,C,F,D,E,BC．A,B,F,D．A,B,D,E,19.若个的边集{B),C),(B,(C,F),(D,E),F)}，从顶点A始对该图进行广度优先搜索，得到的顶点序列可能为（DAB,C,E,B．A,C,F,EC．A,B,E,D．A,C,B,D,20.若个的边集{<1,<1,4>,<2,5>,1>,5>,<4,，从顶点1始对该图进行深度优先搜索，得到的顶点序列可能为（AA1,2,5,4,3B．．D21.若个的边集{<1,<1,4>,<2,5>,1>,5>,<4,，从顶点1始对该图进行广度优先搜索，得到的顶点序列可能为（A1,2,3,4,5B．．D22.由个有n个顶点的连通图生成的最小生成树中，具有（B）条边。AnB．n-1．D．223.已一有向图的边集{c>,d>,<b,e>,<d,e>}则由该图产生的一种可能的拓扑序列为（AAc,B．d,e,bC．c,e,dD．a,c,二、填空题在一个图中，所有顶点的度数之和等于所有边数的倍在一个具有个点的无向完全图有-1)/2条，在一个具有n个点的有向完图中，包含有1)条。假定一个有向图的顶点集为{a,b,c,d,e,f}边集为

{<a,<a,f>,<e,<e,出度为0的点个数为2入为1的顶点个数为。在个具有个顶点的无向图中，要连通所有顶点则至少需要条边。表图的三种种存储结构为邻接矩阵、邻接表和邻接多重表。

解答：深度优先搜索序列：0,2,3,1,10.11.12.

在一个连通图中存在着1个通分量。图中的一条路径长度为k径所含的顶点数为。若一个图的顶点集为{c,e,f}{(a,b),c),(b,c),(d,，则该图含有个通分量。对于一个具有个点的图，若用邻接矩阵表示，则矩阵大小至少为nn。对于具有个点条的无向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为和。对于具有个点条的有向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为和。在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有出边和入边结点。

广度优先搜索序列：3,5,对于一个有向图，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。解答：深度优先搜索序列：0,3,6,5,广度优先搜索序列：2,6,13.对于一具有个点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为O(n)和O(e)。14.假定一图具有n个点和条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为和。15.图的深度优搜索遍历算法是种递归算法，

已知下图所示的一个网）按照Prim方，从顶点出，求该网的最小生成树的产生过程。（2按照方法，求该网的最小生成树的产生过程。图的广度优搜索遍历算法需要使用队列。16.对于一具有个点和e条边的连通图，其生成树中的顶点数和边数分别为n和n-1。17.若一个通图中每个边上的权值均不同，则得到的最小生成树是唯一（唯一不唯一）的。根据图的存储结构进行某种次序的遍历，得到的顶点

序列是不唯一（唯一/不唯一）的。18.假定一有向图的边集{<a,e>,<c,f>,<e,b>,d>}，该进行拓扑排序得到

解答）

的顶点序列为aebdcf。三、应用题对一个无向图，假定采用邻接矩阵表示，试分别写出从顶点出按深度优先索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。

V5V6(a)

V7V6

(e)

V6(f)

下图所示为一个有向网图及其带权邻接矩阵，要求对有向图采用算从V0到其余各顶点的最短路径。

V3

V6

(a)有向带权图（2

∞∞

∞

100

∞∞

∞∞∞∞∞∞

∞∞

V7

∞∞∞∞∞

(a)

∞∞∞20∞∞∞∞∞∞∞带权邻接矩阵

V3

解答：终

从v0到终点的D值和最短路径的求解过程V4

V4

点

i=i=i=i=i5

V1

∞∞∞∞

∞无

V2

10(v0,v2)V430(e)

V4(f)

V3V4V5

6050∞(v0,v2,v3)(v0,v4,v3)30(v0,v4)(v0,v4)100100(v0,v5)(v0,v5)VjV2V4V3V5{v0,v2}{v0,v2,v4}{v0,v2,v3,v4}{v0,v2,v3,v4,v5}上图给出了一个具有个动个件的工程的网求关键路径。

v8v9222v8v9222

v4

活动：

==11vl(9)–1011v2v1

v7

a11=7

v1a5=3v3

v8

v11a15=6

v3

a12=4v6v10a10=2a14=1v9

v11a15=6

v10a14=1活动：==解答：①事件的最早发生时间ve[k]ve(1)=0ve(2)=ve(3)=ve(4)=+2=ve(5)=max{ve(2)1,ve(3)+3}=7ve(6)=+5=ve(7)=max{ve(4)6,ve(5)+8}=ve(8)=+4=ve(9)=max{ve(8)10,ve(6)+2}=21ve(10)=+4,ve(9)+1}22ve(11)=+7,ve(10)+6}=28②事件的最迟发生时间vl[k]：vl(11)==vl(10)–622vl(9)==21vl(8)=min{4,vl(9)11vl(7)=–=21vl(6)vl(9)=19vl(5)=min{vl(7)-vl(8)-4}=vl(4)=vl(7)–6=vl(3)=min{vl(5)-vl(6)-5}=vl(2)=min{vl(4)-vl(5)-1}=vl(1)=-vl(3)-4}=③活动ai最早开始时间和最晚开始时间l[i]：活动a1e(1)==0l(1)=vl(2)–33活动a2e(2)==0l(2)=vl(3)–40活动a3e(3)==3l(3)=vl(4)–213活动a4e(4)==3l(4)=vl(5)–16活动a5e(5)==4l(5)=vl(5)–34活动a6e(6)==4l(6)=vl(6)–514活动a7e(7)==5l(7)=vl(7)–615活动a8e(8)==7l(8)=vl(7)–813活动a9e(9)==7l(9)=vl(8)–47活动a10e(10)=vl(9)=19活动a11：==–21活动a12e(12)=–

活动：e(15)=ve(10)=-=22④最后，比较和l[i]的可判断出a2,a9,a13,a14,a15是键活动，关键路径如下图所示。第9章排序一、单项选择题若对n个素进行直接插入排序行i趟序时，假定元素的插入位置为r[j]，则需要移动元素的次数为（DAj-iBC．i-jD．若对个素行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（BAO(1)BO(n)C．O(n)D．O(logn)2在对个素行直接插入排序的过程中，共需要进行（）趟。AnB．n+1．D对元素进行直接插入排序时间复杂度AO(1)BO(n)．O(n)D．2在对个素行冒泡排序的过程中，第一趟排序至多需要进行（B）对相邻元素之间的交换。AnB．n-1．D．n/2在对个素行冒泡排序的过程中，最好情况下的时间复杂度为（DAO(1)BO(log．O(n)D．O(n)2在对个素行快速排序的过程中，第一次划分最多需要移（D次元素括开始把支点元素移动到临时变量的一次在内。An/2B．n-1．nD．在对个素行快速排序的过程中，最好情况下需要进行（C）躺。AnB．．logD2n2在对个素行快速排序的过程中，最坏情况

2222222下需要进行（B）躺。2222222AnB．．Dlogn210.在对个素进行快速排序的过程中，平均情况下的时间复杂度为（DAO(1)B．n)．O(n)D．O(nlogn)211.在对个素进行快速排序的过程中，最坏情况下的时间复杂度为（CAO(1)B．n)．O(n)D．n)212.在对个素进行快速排序的过程中，平均情况下的空间复杂度为（DAO(1)B．n)．O(n)D．n)213.在对个素进行直接插入排序的过程中，算法的空间复杂度为（AAO(1)BCO(n)DO(nlogn)214.对下列个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（DA1,5,9B．9,7,1C．5,1,9D7,9,15.假定对素序列5,9,15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（BA2B．．D16.在对个素进行简单选择排序的过程中，需要进行（C）趟选择和交换。AnB．．n-1D．

23.若对个素排序，要求既快又稳定，则最好采用（B）方法。A直接插入排序B．归并序C．排序D．速排序24.若对个素排序求既快又节省存储空间，则最好采用（C）方法。A直接插入排序B．归并序C．排序D．速排序25.在均况下速度最快的排序方法为（DA简单选择排序B．归并序C．排序D．速排序二、填空题每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置种序法叫做直插入排次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做选择排序。每次直接或通过支点元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做快速排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做归排。在简单选择排序中，记录比较次数的时间复杂度为，录移动次数的时间复杂度为O(n)。对n个录进行冒泡排序时的较次数为n-1，最少的趟数为。17.在对个素进行堆排序的过程中，时间复杂度为（AO(1)B．n)．O(n)D．O(nlogn)218.在对个素进行堆排序的过程中，空间复杂度为（AAO(1)B．n)．O(n)DO(nlog219.假定对素序列3,5,12）行堆排序，采用小根堆初始数据构成的始堆（BA1,5,9,12B．1,3,5,12C．1,3,9,12D．5,7,1220.假定一初始堆(1,9,12,7,15,10)进第一趟堆排序后得到的结果为（AA3,7,10,B9,7,12,15,C．3,5,10,D．7,12,9,10,15,21.若对个素进行归并排序，则进行归并的趟数为（AnB．．Dn222.若一个素序列基本有序选A较。A直接插入排序B希尔排序C．排序D快速排序

10.11.12.

快速排序在平均情况下的时间复杂度为n)，最坏情况下的时间复杂度为O(n)。若对一组记(79,38,80,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较次假定一组记录为(46,79,56,40,84)，则利用堆排序方法建立的初始小根堆为(38,40,79,。假定一组记录为(46,79,56,40,84)，在冒泡排序的过程中进行第一趟排序后的结果为56,38,79,。假定一组记录为(46,79,56,38,84,43)，冒泡排序的过程中进行第一趟排序时素79将最终下沉到其后第个素的位从0开假定一组记录为(46,79,56,40,80)，对其进行快速排序的过程中，共需要3趟序。假定一组记录为(46,79,56,76,40,80)，其进行快速排序的第一次划分后，右区间内元素的个数为4。假定一组记录为(46,79,56,40,80)，对其进行快速排序的第一次划分后的结果为[40,[56,79,80]。

213.假定一记录为46,79,56,38,40,46,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为。214.假定一记录为46,79,56,38,40,46,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个表为46]。15.假定一记录为46,79,56,38,40,46,28,对其进行归并排序的过程中，供需要4趟完成。16.在时间杂度为的所有排序方法中，归2并排序方法是稳定的。17.在时间杂度为O(n)的所有排序方法中，直接选择排方法是不稳定的。18.在所有序方法中，快速排方法采用的是二分法的思想。19.在所有序方法中，堆排序方使数据的组织采用的是完全二叉树的思想。20.在所有序方法中，归并排序方采用的是两两有序表合并的思想。21.冒泡排方法使键值大的记录渐下沉，使键值小的记录逐渐上浮。22.直接入排序方法能够每次使序表中的第一个记录插入到有序表中。23.直接择排序方法能够每次从序表中顺序查找出一个最小值。三、应用题已知一组记录为46,74,14,38,65,34)，给出采用下列各种排序法进行排序时每一趟的排序结果）接入法）冒泡排序法）快速排序法）单选择排序法）排序法）并排序法。解答：（1）直接插入排序[46]2638866527341426388665273474]1426388665273474]26388665273438866527348665657486]2734657453657486]（2）冒泡排序法86652734]65272734]7486

2634]7486266526657486[1434]4653657486[1434]4653（快速排序法7486652734]27[865374]2714]34[7453]14