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

1、个人收集整理仅供参考学习第8章图一、单项选择题1 .在一个具有n个顶点地有向图中，若所有顶点地 出度数之和为s,则所有顶点地入度数之和为（A）.A. s B. s-1 C. s+1 D. n2 .在一个具有n个顶点地无向图中，若具有e条边, 则所有顶点地度数之和为（D）.A . n B. eC. n+e D. 2e3 .在一个具有n个顶点地无向完全图中，所含地边 数为（C）.A. n B. n（n-1）C, n（n-1）/2 D. n（n+1）/24 .在一个具有n个顶点地有向完全图中，所含地边 数为（B）.A. n B. n（n-1）C. n（n-1）/2 D. n（n+1）/25 .在一个

2、无向图中，若两顶点之间地路径长度为k,则该路径上地顶点数为（B）.A. k B. k+1 C, k+2 D. 2k6 .对于一个具有n个顶点地无向连通图，它包含地 连通分量地个数为（B）.A. 0 B. 1C, n D, n+17 .若一个图中包含有 k个连通分量，若要按照深度 优先搜索地方法访问所有顶点，则必须调用（ A） 次深度优先搜索遍历地算法.b5E2RGbCAPA. k B. 1C. k-1 D, k+18 .若要把n个顶点连接为一个连通图，则至少需要 （C）条边.A. n B. n+1 C. n-1 D. 2n9 .在一个具有n个顶点和e条边地无向图地邻接矩 阵中，表示边存在地元素

3、（又称为有效元素）地 个数为（D）.A. n B. nXe C. eD. 2心10 .在一个具有n个顶点和e条边地有向图地邻接矩 阵中，表示边存在地元素个数为（C）.A. n B. n><e C. eD. 2g11 .在一个具有n个顶点和e条边地无向图地邻接表 中，边结点地个数为（D）.A. n B. n* C. eD. 2g12 .在一个具有n个顶点和e条边地有向图地邻接表 中，保存顶点单链表地表头指针向量地大小至少 为（A）.A. n B. 2n C. eD. 2e13 .在一个无权图地邻接表表示中，每个边结点至少 包含（B）域.A. 1 B. 2C. 3D. 414 .对于一

4、个有向图，若一个顶点地度为k1 ,出度为k2,则对应邻接表中该顶点单链表中地边结点数 为（B）.A. k1 B. k2 C. k1-k2 D, k1+k215 .对于一个有向图，若一个顶点地度为k1 ,出度为k2,则对应逆邻接表中该顶点单链表中地边结点 数为（C）.A. k1 B. k2 C. k1-k2 D, k1+k216 .对于一个无向图，下面（A）说法是正确地.A.每个顶点地入度等于出度B.每个顶点地度等于其入度与出度之和C.每个顶点地入度为0 D.每个顶点地出度为017. 在一个有向图地邻接表中，每个顶点单链表中结 点地个数等于该顶点地（A）.A.出边数 B.入边数 C.度数 D.度

5、数减118. 若一个图地边集为（A, B）, （A, C）, （B, D）, （C, F）, （D, E）, （D, F）,则从顶点A开始对该图进行深度 优先搜索，得到地顶点序列可能为（B ） .p1EanqFDPwA. 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 ） .DXDiTa9E3dA. A, B, C, D, E,

6、 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） .RTCrpUDGiTA. 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>, &l

7、t;3, 1>, <3, 5>, <4, 3>,则从顶点1开始对该图进行广度 优先搜索，得到地顶点序列可能为（C）巧PCzVD7HxAA. 1,2,3,4,5B . 1,2,4,3,5C. 1,2,4,5,3D. 1,4,2,5,322. 由一个具有n个顶点地连通图生成地最小生成树 中，具有（B）条边.A. n B. n-1 C. n+1 D. 2叼23. 已知一个有向图地边集为<a, b>, <a, c>, <a, d>,<b, d>, <b, e>, <d, e>,则由该图产生地一种可能

8、地拓扑序列为（A） .jLBHrnAILgA. a, b, c, d, eB . a, b, d, e, bC. a, c, b, e, dD . a, c, d, b, e二、填空题1 .在一个图中，所有顶点地度数之和等于所有边数 地2倍.2 .在一个具有n个顶点地无向完全图中，包含有nn-1）/2条边，在一个具有 n个顶点地有向完全图 中，包含有 n（n - 1）条边.xHAQX74J0X3 .假定一个有向图地顶点集为a,b,c,d,e,f,边集为<a, c>, <a, e>, <c,f>, <d, c>, <e, b>, <

9、;e, d>,贝U出 度为0地顶点个数为2,入度为1地顶点个数为 4.LDAYtRyKfE4 .在一个具有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_个连通分量.Zzz6ZB2Ltk9 .对于一个具有n个顶点地图，若采用邻接矩阵表 示，则矩阵大小至少为n n.10 .对于具有n个

10、顶点和e条边地无向图，在它们对 应地邻接表中，所含顶点个数和边结点地个数分 别为n和2e.11 .对于具有n个顶点和e条边地有向图，在它们对 应地邻接表中，所含顶点个数和边结点地个数分 别为n和e.12 .在有向图地邻接表和逆邻接表表示中，每个顶点 邻接表分别链接着该顶点地所有心和出结点.13 .对于一个具有n个顶点和e条边地无向图，当分 别采用邻接矩阵和邻接表表示时，求任一顶点度 数地时间复杂度分别为O(n)和O(e).dvzfvkwMI114 .假定一个图具有 n个顶点和e条边，则采用邻接 矩阵和邻接表表示时，其相应地空间复杂度分别为 O(n2)和 O(n+2e).rqyn14ZNXI15

11、 .图地途亶优先搜索遍历算法是一种递归算法，图 地广度优先搜索遍历算法需要使用队列.16 .对于一个具有n个顶点和e条边地连通图，其生 成树中地顶点数和边数分别为0_和n-1.17 .若一个连通图中每个边上地权值均不同，则得到 地最小生成树是唯二(唯一 /不唯一)地.根据图地 存储结构进行某种次序地遍历，得到地顶点序列 是不唯一(唯一/不唯一)地.EmxvxOtOco18 .假定一个有向图地边集为 <a, c>, <a, e>, <c, f>, <d, c>, <e, b>, <e, d>,对该图进行拓扑排序得到 地顶点序

12、列为 aebdcf. SixE2yXPq5三、应用题1.对于一个无向图，假定采用邻接矩阵表示，试分 别写出从顶点0出发按深度优先搜索遍历得到地 顶点序列和按广度优先搜索遍历得到地顶点序歹U .6ewMyirQFL注：每一种序列都是唯一地，因为都是在存储结构上 得到地.解答：深度优先搜索序列: 广度优先搜索序列:34561000、01D 11 O 10 D 11 OOI101 1 口 一0,2,3, 5,6, 1,40,2,3, 5,6, 1,42 .对于一个有向图，假定采用邻接表表示，并且假 定每个顶点单链表中地边结点是按出边邻接点序号从大到小地次序链接地，试分别写出从顶点0出发按深度优先搜索

13、遍历得到地顶点序列和按广 度优先搜索遍历得到地顶点序列.kavU42VRUs注：每一种序列都是唯一地，因为都是在存储结构上 得到地.解答：深度优先搜索序列：0, 3, 6,4,1,5,2广度优先搜索序列：0, 3, 2, 6, 5, 4, 13 .已知下图所示地一个网，(1)按照Prim方法，从 顶点1出发，求该网地最小生成树地产生过程(2)按照Kruskal方法，求该网地最小生成树地产生过程.y6V3ALoS89(a)(b)4/8个人收集整理(c)V74.下图所示为一个有向网图及其带权邻接矩阵，要求对有向图采用 Dijkstra算法，求从V0到其余各顶点地最短路径.eUts8ZQVRd(a)

14、有向带权图(2)V2V4V7(a)OOOO10OO30100OOOO5OOOOOOOOOOOO50OOOOOOOOOOOOOO10OOOOOO20OO60OOOOOOOOOOOO(b)带权邻接矩阵V1V1终占 八、从v0到各终点地D值和最短路径地求解过程i = 1i = 2i = 3i = 4i = 5V1OOOOOOOOOO无V210(v0,v2)V3OO60(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)VjV2V4V3V5Sv0,v2v0,v2,v4v0,

15、v2,v3,v4v0,v2,v3,v4,v5sQsAEJkW5T解答:5.上图给出了一个具有 15个活动、11个事件地工程地AOE网，求关键路径6 / 8个人收集整理仅供参考学习- 3 = 3- 4 = 0- 2 = 13- 1 = 6- 3 = 4- 5 = 14- 6 = 15-8 = 13-4 = 7ve(1) = 0ve(2) = 3ve(3) = 4ve(4) = ve(2) + 2 = 5ve(5) = maxve(2) + 1, ve(3) + 3 = 7ve(6) = ve(3) + 5 = 9ve(7) = maxve(4) + 6, ve(5) + 8 = 15ve(8)

16、= ve(5) + 4 = 11ve(9) = maxve(8) + 10, ve(6) + 2 = 21ve(10) = maxve(8) + 4, ve(9) + 1 = 22ve(11) = maxve + 7, ve(10) + 6 = 28事件地最迟发生时间vlk: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 = 21 vl(6) = vl(9) - 2 = 19vl(5) = min

17、 vl-8, vl(8) - 4 = 7vl(4) = vl-6 = 15vl(3) = min vl(5) - 3, vl(6) - 5 = 4vl(2) = min vl(4) - 2, vl(5) - 1 = 6vl(1) = minvl(2) - 3, vl(3) - 4 = 0 活动ai地最早开始时间ei和最晚开始时间li:活动a1:e(1)=ve(1) = 0l(1)=vl(2)活动a2：e(2)=ve(1) = 0l(2)=vl(3)活动a3:e(3)=ve(2) = 3l(3)=vl(4)活动a4：e(4)=ve(2) = 3l(4)=vl(5)活动a5:e(5)=ve(3)

18、= 4l(5)=vl(5)活动a6:e(6)=ve(3) = 4l(6)=vl(6)活动a7:e(7)=ve(4) = 5l(7)=vl(7)活动a8:e(8)=ve(5) = 7l(8)=vl (7)活动a9:e(9)=ve(5) = 7l(9)=vl(8)活动 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) = 11活动

19、a14:e(14) = ve(9) = 21 TIrRGchYzgl(14) = vl(10) -1 = 21活动 a15:e(15) = ve(10) = 22l(15) = vl(11) - 6 = 22最后，比较ei和li地值可判断出a2, a5, a9, a13, a14, a15是关键活动，关键路径如下图所 示.7EqZcWLZNX第9章排序一、单项选择题1 .若对n个元素进行直接插入排序，在进彳T第i趟排序时，假定元素ri+1地插入位置为rj,则需要 移动元素地次数为(D ) .lzq7IGf02EA. j-i B. i-j-1 C. i-j D. i-j+12 .若对n个元素进行

20、直接插入排序，则进行任一趟 排序地过程中，为寻找插入位置而需要地时间复 杂度为(B ) .zvpgeqJ1hkA. O(1) B. O(n) C. O(n2) D. O(log 2n)3 .在n个元素进行直接插入排序地过程中，共需 要进彳T ( C )趟.A. n B. n+1 C. n-1 D. 2n4 .对n个元素进行直接插入排序时间复杂度为(C).A. 0(1) B. O(n) C. O(n2)D. O(log2n)5 .在n个元素进行冒泡排序地过程中，第一趟排 序至多需要进行(B )对相邻元素之间地交换.A. n B. n-1 C, n+1 D. n/26 .在n个元素进行冒泡排序地过

21、程中，最好情况 下地时间复杂度为(D ).A. 0(1) B. O(log 2n) C. 0(n2)D, 0(n)7 .在n个元素进行快速排序地过程中，第一次划 分最多需要移动(D )次元素，包括开始把支点 兀素移动到临时变量地一次在内.NrpoJac3v1A. n/2 B. n-1 C. nD, n+18 .在n个元素进行快速排序地过程中，最好情况 下需要进行(C )躺.A. n B. n/2 C. log2n D. 2n9 .在n个元素进行快速排序地过程中，最坏情况 下需要进行(B )躺.A. n B . n-1 C. n/2 D. log2n10 .在n个元素进行快速排序地过程中，平均情

22、况 下地时间复杂度为( D ).A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)11 .在n个元素进行快速排序地过程中，最坏情况 下地时间复杂度为( C ).A. O(1) B. O(log2n) C. O(n2)D. O(nlog2n)12 .在n个元素进行快速排序地过程中，平均情况 下地空间复杂度为( D ).A. O(1) B. O(log2n) C. O(n2)D. O(nlog2n)13 .在n个元素进行直接插入排序地过程中，算法 地空间复杂度为(A ).A. O(1) B. O(log2n)C. O(n2) D. O(nlog2n)14 .对下列四

23、个序列进行快速排序，各以第一个元素 为基准进行第一次划分，则在该次划分过程中需 要移动元素次数最多地序列为( D ) .1nowfTG4KIA. 1,3, 5, 7, 9B. 9, 7, 5, 3, 1C. 5, 3, 1,7, 9D. 5, 7, 9, 1,315 .假定对元素序列(7, 3, 5, 9, 1, 12, 8, 15)进行快速 排序，则进行第一次划分后，得到地左区间中元素地个数为(B ) .fjnFLDa5ZoA. 2 B. 3C. 4D. 516 .在n个元素进行简单选择排序地过程中，需要 进行(C )趟选择和交换.A. n B. n+1 C. n-1 D. n/217 .在

24、n个元素进行堆排序地过程中，时间复杂度 为(D ).A. 0(1) B. O(log2n) C. O(n2) D. O(nlog2n)18 .在n个元素进行堆排序地过程中，空间复杂度为(A ).A. 0(1) B. 0(log2n)C, 0(n2) D, 0(nlog2n)19 .假定对元素序列(7, 3, 5, 9, 1, 12 )进行堆排序， 采用小根堆，则初始数据构成地初始堆为(B ) .tfnNhnE6e5A . 1,3, 5, 7, 9, 12B. 1,3, 5, 9, 7, 12C. 1,7, 3, 5, 9, 12D, 1,3, 5, 7, 9, 1220 .假定一个初始堆为(1

25、,5, 3, 9, 12, 7, 15, 10),则进行 第一趟堆排序后得到地结果为(A ) .HbmVN777sLA .3,5,7, 9,12,10,15,1B. 3,5,9, 7,12,10,15,1C. 3,7,5, 9,12,10,15,1D. 3,5,7, 12, 9,10,15,121 .若对n个元素进行归并排序，则进行归并地趟数 为(D ).A . n B . n-1 C. n/2 D. log2nl22 .若一个元素序列基本有序，则选用(A )法较快.A.直接插入排序B.希尔排序C.堆排序D.快速排序23 .若要对1000个元素排序，要求既快又稳定，则最 好采用(B )方法.A

26、.直接插入排序B .归并排序C.堆排序D.快速排序24 .若要对1000个元素排序，要求既快又节省存储空 间，则最好采用(C )方法.A.直接插入排序B .归并排序C.堆排序D.快速排序25 .在平均情况下速度最快地排序方法为( D ).A.简单选择排序B .归并排序C.堆排序D.快速排序二、填空题1 .每次从无序子表中取出一个元素，把它插入到有 序子表中地适当位置，此种排序方法叫做直接插人排序；每次从无序子表中挑选出一个最小或最 大元素，把它交换到有序表地一端，此种排序方 法叫做选择排序.V7l4jRB8Hs2 .每次直接或通过支点元素间接比较两个元素，若 出现逆序排列时就交换它们地位置，此

27、种排序方 法叫做快速排序;每次使两个相邻地有序表合并 成一个有序表地排序方法叫做归并排 序.83lcPA59W93 .在简单选择排序中，记录比较次数地时间复杂度 为0(n2),记录移动次数地时间复杂度为On).4 .对n个记录进行冒泡排序时，最少地比较次数为 n 最少地趟数为.5 .快速排序在平均情况下地时间复杂度为O(nlog?n),在最坏情况下地时间复杂度为0(n2).6 . 若对一组记录(46, 79, 56, 38, 40, 80, 35, 50, 74)进 行直接插入排序，当把第 8个记录插入到前面已 排序地有序表时，为寻找插入位置需比较4 次.mZkklkzaaP7 .假定一组记录

28、为(46, 79, 56, 38, 40, 84),则利用堆 排序方法建立地初始小根堆为(38, 40, 56, 79, 46,84) .AVktR43bpw8.假定一组记录为(46, 79, 56, 38, 40, 84),在冒泡排 序地过程中进行第一趟排序后地结果为(46, 56,38, 40, 79, 84) . ORjBnOwcEd9 假定一组记录为(46, 79, 56, 64, 38, 40, 84, 43),在 冒泡排序地过程中进行第一趟排序时，元素79将最终下沉到其后第二£个元素地位置(从 0开始).2MiJTy0dTT10.假定一组记录为(46, 79, 56, 3

29、8, 40, 80),对其进行 快速排序地过程中，共需要3_趟排序.gliSpiue7A9 / 8个人收集整理仅供参考学习11 .假定一组记录为(46, 79, 56, 25, 76, 38, 40, 80),对 其进行快速排序地A次划分后，右区间内元素 地个数为 4.uEh0U1Yfmh12 .假定一组记录为(46, 79, 56, 38, 40, 80),对其进行 快速排序地A次划分后地结果为40, 38 4656, 79, 80 . IAg9qLsgBX13 .假廿组记包 (46, 79, 56, 38, 40, 80, 46, 75, 28, 46),对其进行归并排序地过程中，第二趟归

30、并后 地子表个数为 3 .WwghWvVhPE14 . 假廿组记包 (46, 79, 56, 38, 40, 80, 46, 75, 28, 46),对其进行归并排序地过程中，第三趟归并后 地第 2 个子表为 28, 46 . asfpsfpi4k15 .假廿组记包 (46, 79, 56, 38, 40, 80, 46, 75, 28, 46),对其进行归并排序地过程中，供需要_4jt完成.ooeyYZTjj116 .在时间复杂度为O(nlog2n)地所有排序方法中，归 土排序方法是稳定地.17 .在时间复杂度为O(n2)地所有排序方法中，直接选 段 排序方法是不稳定地.18 .在所有排序方

31、法中，快速排序方法采用地是二分法地思想.19 .在所有排序方法中，堆排序方法使数据地组织采用地是完全二叉树地思想.20 .在所有排序方法中，归并排序方法采用地是两两有序表合并地思想.21 .冒泡排序方法使键值大地记录逐渐下沉,使键值 小地记录逐渐上浮.22 .直接插入排序方法能够每次使无序表中地A个 记录插入到后序表中 .23 .直接选择排序方法能够每次从无序表中顺序查找 出一个最小值.三、应用题已知一组记录为(46, 74, 53, 14, 26, 38, 86, 65, 27, 34), 给出采用卜列各种排序法进行排序时每一趟地排序结 果：(1)直接插入法，(2)冒泡排序法，(3)快速排

32、序法，(4)简单选择排序法，(5)堆排序法，(6)归 并排序法.BkeGuInkxI 解答：(1)直接插入排序(0)46745314263886652734(1) 46745314263886652734(2) 46537414263886652734(3) 14465374263886652734(4) 14264653743886652734(5) 14263846537486652734(6) 14263846537486652734(7) 14263846536574862734(8) 14262738465365748634(9) 14262734384653657486(2)冒泡排

33、序法(0)46745314263886652734(1) 46531426387465273486(2) 46142638536527347486(3) 14263846532734657486(4) 14263846273453657486(5) 1426382734 4653657486(6) 14262734384653657486(7) 14262734384653657486(3)快速排序法(0)467453 142638 86652734(1) 342738 142646 86655374(2) 262714343846 74655386(3) 14262734384653 65

34、74 86(4) 14262734384653 65 74 86(4)简单选择排序(0) 46 74 53 14 26 38 86 65 27 34(1) 14745346263886652734(2) 14265346743886652734(3) 14262746743886655334(4) 14262734743886655346(5) 14262734387486655346(6) 14262734384686655374(7) 14262734384653658674(8) 14262734384653658674(9) 14 26 27 34 38 46 53 65 74 86(

35、5)堆排序法构成初始堆(即建堆)地过程：(0)46745314263886652734(1) 46745314263886652734(2) 46745314263886652734(3) 46743814265386652734(4) 46143827265386657434(5) 14263827345386657446进行堆排序地过程：(0)14263827345386657446(1) 26273846345386657414(2) 27343846745386652614(3) 34463865745386272614(4) 38465365748634272614(5) 46655

36、386743834272614(6) 53657486463834272614(7) 65867453463834272614(8) 74866553463834272614(9) 86746553463834272614(6)归并排序法10 / 8仅供参考学习个人收集整理(0)46 74 53 1426 38 86 65 2734 PgdO0sRlMo(1) 4674 1453 2638 6586 2734(2) 14465374 26386586 2734(3) 14263846 53657486 2734(4) 14262734 38465365 7486版权申明本文部分内容，包括文字、图片、 以及设计等在网上搜集整理.版权为个 人所有