2022年数据结构复习题及答案 .docx

《2022年数据结构复习题及答案 .docx》由会员分享，可在线阅读，更多相关《2022年数据结构复习题及答案 .docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品_精品资料_一、判定题：中南高校现代远程训练课程考试专科）复习题及参考答案数据结构可编辑资料 - - - 欢迎下载精品_精品资料_1. 数组是一种复杂的数据结构,数组元素之间的关系既不是线性的也不是树形的. ）2. 链式储备在插人和删除时需要保持物理储备空间的次序安排,不需要保持数据元素之间的规律次序.4. 折半搜寻只适用于有序表,包括有序的次序表和有序的链表.5. 假如两个串含有相同的字符,就这两个串相等.）6. 数组可以看成线性结构的一种推广,因此可以对它进行插入、删除等运算.）7. 在用循环单链表表示的链式队列中,可以不设队头指针,仅在链尾设置队尾指针. ）8. 通常递归的算法简洁、

2、易懂、简洁编写,而且执行的效率也高. ）9. 一个广义表的表尾总是一个广义表.）10. 当从一个小根堆 最小堆）中删除一个元素时,需要把堆尾元素填补到堆顶位置,然后再按条件把它逐层向下调整,直到调整到合适位置为止. ）11. 对于一棵具有n 个结点,其高度为h 的二叉树,进行任一种次序遍历的时间复杂度为Oh ）. ）12. 储备图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关. ）13. 直接选择排序是一种稳固的排序方法.）14. 闭散列法通常比开散列法时间效率更高.16. 直接选择排序是一种不稳固的排序方法.17. 在 2048 个互不相同的关键码中选择最小的5 个

3、关键码,用堆排序比用锦标赛排序更快.18. 当 3 阶 B_树中有 255 个关键码时 ,其最大高度 包括失败结点层 不超过 8.19. 一棵 3 阶 B_ 树是平稳的 3 路搜寻树 ,反之 ,一棵平稳的 3 路搜寻树是 3 阶非 B_树. 20. 在用散列表储备关键码集合时,可以用双散列法查找下一个空桶.在设计再散列函数时,要求运算出的值与表的大小 m 互质. 21. 在索引次序表上实现分块查找,在等概率查找情形下,其平均查找长度不仅与表中元素个数有关,而且与每一块中元素个数有关.）22. 在次序表中取出第i 个元素所花费的时间与i 成正比.24. 二路归并排序的核心操作是将两个有序序列归并

4、为一个有序序列.）25. 对任意一个图,从它的某个顶点动身,进行一次深度优先或广度优先搜寻,即可拜访图的每个顶点.）26. 二叉排序树或者是一棵空二叉树,或者不是具有以下性质的二叉树：如它的左子树非空,就根结点的值大于其左孩子的值.如它的右子树非空,就根结点的值小于其右孩子的值.）27. 在执行某个排序算法过程中,显现了排序码朝着最终排序序列位置相反方向移动,就该算法是不稳固的. ）28. 一个有向图的邻接表和逆邻接表中表结点的个数肯定相等.A. OnB. On 2 C. O1D. On 22. 带头结点的单链表first 为空的判定条件是： A. first=NULLB. first 一1i

5、nk NULL可编辑资料 - - - 欢迎下载精品_精品资料_C. first 一link=firstD. first. NUlL3. 当利用大小为n 的数组次序储备一个队列时,该队列的最大长度为.A. n-2B. n-lC. nD. n+14. 在系统实现递归调用时需利用递归工作记录储存实际参数的值.在传值参数情形,需为对应形式参数安排空间,以存放实际参数的副本.在引用参数情形,需储存实际参数的 ,在被调用程序中可直接操纵实际参数.A. 空间B. 副本C. 返回的址D. 的址5. 在一棵树中, 没有前驱结点.A. 分支结点D. 叶结点C. 树根结点D. 空结点6. 在一棵二叉树的二叉链表中,

6、空指针域数等于非空指针域数加 .A. 2B. 1C. 0D. -17. 对于长度为 9 的有序次序表,如采纳折半搜寻,在等概率情形下搜寻胜利的平均搜寻长度为的值除以9.A. 20B. 18C. 25D. 228. 在有向图中每个顶点的度等于该顶点的.A. 入度B. 出度C. 入度与出度之和D. 入度与出度之差9. 在基于排序码比较的排序算法中,算法的最坏情形下的时间复杂度不高于On10g2n .A. 起泡排序B. 希尔排序C. 归并排序D. 快速排序10. 当 的值较小时,散列储备通常比其他储备方式具有的查找速度.A. 较慢B. 较快C. 相同 D. 不清晰11. 设有一个含200 个表项的散

7、列表,用线性探查法解决冲突,按关键码查询时找到一个表项的平均探查次数不超过 1.5,就散列表项应能够至少容纳个表项.可编辑资料 - - - 欢迎下载精品_精品资料_ 设搜寻胜利的平均搜寻长度为Snl 1+l 1 一 A. 400B. 526C. 624D. 6762,其中 为装填因子 可编辑资料 - - - 欢迎下载精品_精品资料_12堆是一个键值序列 k 1,k2, .kn, 对 I=1,2, .|_n/2_满|,足 A. k i k 2ik 2i+1 B. k i k2i+1 D. k i k2i 或 ki k2i+1 2i+1 n13. 如将数据结构形式定义为二元组K , R ,其中K

8、是数据元素的有限集合,就R 是 K 上 A. 操作的有限集合B.映象的有限集合C. 类型的有限集合D. 关系的有限集合14. 在长度为 n 的次序表中删除第i 个元素 1 i 时n, 元素移动的次数为 A. n-i+1B.iC. i+1D. n-i15. 如不带头结点的单链表的头指针为head,就该链表为空的判定条件是 A. head=NULLB.head-next=NULLC. head.=NULLD. head-next=head 16引起循环队列队头位置发生变化的操作是 A.出队B.入队C. 取队头元素D. 取队尾元素可编辑资料 - - - 欢迎下载精品_精品资料_17. 如进栈序列为

9、1, 2, 3,4, 5, 6,且进栈和出栈可以穿插进行,就不行能显现的出栈序列是 A.2, 4, 3, 1, 5, 6B.3, 2, 4, 1, 6, 5C. 4, 3,2, 1, 5, 6D. 2 ,3, 5, 1, 6, 4 18字符串通常采纳的两种储备方式是 A. 散列存储和索引存储B.索引存储和链式存储C. 次序储备和链式储备D. 散列储备和次序储备19. 设主串长为 n,模式串长为mm n,就在匹配失败情形下,朴实匹配算法进行的无效位移次数为 A. mB.n-mC. n-m+1D. n20二维数组 A 12 18采纳列优先的储备方法,如每个元素各占址为 150,就元素 A 9 7的

10、的址为 3 个储备单元,且第1 个元素的的A.429B.432C. 435D. 43821. 对广义表 L=a,b,c,d,e,f 执行操作 tailtailL 的结果是 A.e,fB.e,fC. fD. 22. 以下图示的次序储备结构表示的二叉树是 23. n 个顶点的强连通图中至少含有 A. n-1 条有向边B. n 条有向边C. nn-1/2 条有向边D. nn-1 条有向边24对关键字序列 56,23, 78, 92, 88,67, 19,34 进行增量为 3 的一趟希尔排序的结果为 A. 19 , 23, 56, 34, 78, 67, 88, 92B. 23 , 56,78, 66

11、,88, 92,19, 34C. 19, 23, 34, 56, 67, 78, 88, 92D. 19 , 23, 67, 56, 34, 78, 92, 8825. 如在 9 阶 B- 树中插入关键字引起结点分裂,就该结点在插入前含有的关键字个数为 A. 4B. 5C. 8D. 926. 由同一关键字集合构造的各棵二叉排序树 A. 其外形不肯定相同,但平均查找长度相同B. 其外形不肯定相同,平均查找长度也不肯定相同C. 其外形均相同,但平均查找长度不肯定相同D. 其外形均相同,平均查找长度也都相同27. ISAM 文件和 VSAM文件的区分之一是 A. 前者是索引次序文件,后者是索引非次序

12、文件B. 前者只能进行次序存取,后者只能进行随机存取C. 前者建立静态索引结构,后者建立动态索引结构D. 前者的储备介质是磁盘,后者的储备介质不是磁盘可编辑资料 - - - 欢迎下载精品_精品资料_28. 以下描述中正确选项 ）A 线性表的规律次序与储备次序总是一样的B 每种数据结构都具备三个基本运算：插入、删除和查找C 数据结构实质上包括规律结构和储备结构两方面的内容D 选择合适的数据结构是解决应用问题的关键步骤29. 下面程序段的时间复杂度是 ）i=s=0 whilesi+ .s+=i.A O1 B.On C.Olog 2n D.On 230. 对于次序表来说,拜访任一节点的时间复杂度是

13、B.On C.Olog 2n D.On 31. 在具有 n 个节点的双链表中做插入、删除运算,平均时间复杂度为 B.On C.Olog 2n D.On 232. 经过以下运算后, QueueFrontQ 的值是 .EnQueueQ,a. EnQueueQ,a. DeQueueQ,x .A.a B.b C.1 D.233. 一个栈的入栈序列是a,b,c,就栈的不行能输出序列是）A. acb B.abc C.bca D.cab34. 循环队列是空队列的条件是rear=Q-front B.Q-rear+1%maxsize=Q-front C.Q-rear=0 D.Q-front=035. 设 s3=

14、I AM,s4=A TERCHER.就 strcmps3,s4= A.0 B. 小于 0 C.大于 0 D. 不确定36. 一维数组的元素起始的址loc6=1000 ,元素长度为 4,就 loc8 为） A 1000 B.1004 C.1008 D.837. 广义表 a,b） ,c,d）的表尾是 D.c,d38. 对于二叉树来说,第I 层上至多有个节点 ） A 2i B. 2i -1 C.2i-1 D.2i-1-139. 某二叉树的前序遍历序列为ABDGCEFH, 中序遍历序列为 DGBAECHF ,就后序遍历序列为 ） A BDGCEFHA B.GDBECFHA C.BDGAECHF D.G

15、DBEHFCA40. M 叉树中,度为 0 的节点数称为 ）A 根 B.叶 C.祖先 D.子孙41. 已知一个图如下所示,如从顶点a 动身按宽度搜寻法进行遍历,就可能得到的一种顶点序列为）42. 堆的外形是一棵 ）A 二叉排序树 B.满二叉树 C. 完全二义树 D. 平稳二叉树可编辑资料 - - - 欢迎下载精品_精品资料_43. 排序方法中,从未排序序列中选择元素,并将其依次放入已排序序列初始时为空）的一端的方法, 称为）A 希尔排序 B. 归并排序 C.插入排序 D. 选择排序44. 采纳次序查找方法查找长度为n 的线性表时,每个元素的平均查找长度为/2 D.n-1/245. 散列查找是由

16、键值确定散列表中的位置,进行储备或查找） A 散列函数值 B.本身 C.平方 D.相反数46. 次序文件的缺点是 ）A 不利于修改 B.读取速度慢 C.只能写不能读 D.写文件慢47索引文件的检索方式是直接存取或按 存取A. k i k 2ik 2i+1B. k i k2i+1 D. k i k 2i 或 ki k2i+1 2i+1 n三、 运算与算法应用题 本大题每道题9 分）1.给 定表 119,14, 22,1,66,21, 83,27, 56,13, 10）请按表中元素的次序构造一棵平稳二叉树,并求其在等概率情形下查找胜利的平均长度.9 分）2. 已知一个有向图的顶点集V 和边集 G分

17、别为： V=a,b,c,d,e,f,g,hE=,.假定该图采纳邻接矩阵表示,就分别写出从顶点a 动身进行深度优先搜寻遍历和广度优先搜寻遍历得到的顶点序列. 9 分）3. 设散列表的长度为13,散列函数为Hh） = k%13,给定的关键码序列为19, 14,23, 01, 68, 20,84, 27.试画出用线性探查法解决冲突时所构成的散列表. 假 设 关 键 字 集 合 为 1,2,3,4,5,6,7, 试 举 出 能 达 到 上 述 结 果 的2 对所举序列进行快速排序,写出排序过程.分）5.如图所示二叉树,回答下列问题次 关 键 字 的 比 较 .初 始 关 键 字 序 列 .9分）6.

18、画出在一个初始为空的AVL树中依次插入 3,1,4,6,9,8,5,7时每一插入后 AVL树的外形.如做了某种旋转,说明旋转的类型.然后,给出在这棵插入后得到的AVL树中删去根结点后的结果.7. 已知一组记录的排序码为 46, 79, 56, 38, 40, 80,95, 24）,写出对其进行快速排序的每一次划分结果.8.一个线性表为 B= 12, 23, 45, 57, 20, 03, 78, 31, 15, 36）,设散列表为HT0.12,散列函数为 H 进行散列储备,采纳HK=K 9 作为散列函数,如分别采纳线性探查法和链接法处理冲突,就对应的平均查找长度分别为和.11假定一组记录的排序

19、码为46 , 79, 56, 38, 40, 80, 25, 34, 57, 21,就对其进行快速排序的第一次划分后又对左、右两个子区间分别进行一次划分,得到的结果为：.12. 下图是带权的有向图G 的邻接表表示法.从结点V1 动身,深度遍历图G 所得结点序列为 A）,广度遍历图G 所得结点序列为 B）. G 的一个拓扑序列是 C ）.从结点 V1 到结点 V8 的最短路径为 D ）.从结点 V1 到结点 V8 的关键路径为 E）.其中 A、B、 C的选择有： V1,V2,V3,V4,V5,V6,V7,V8V1,V2,V4,V6,V5,V3,V7,V8V1,V2,V4,V6,V3,V5,V7,

20、V8V1,V2,V4,V6,V7,V3,V5,V8V1,V2,V3,V8,V4,V5,V6,V7V1,V2,V3,V8,V4,V5,V7,V6V1,V2,V3,V8,V5,V7,V4,V6D、E 的选择有：V1,V2,V4,V5,V3,V8V1,V6,V5,V3,V8V1,V6,V7,V8V1,V2,V5,V7,V813. 画出对长度为 10 的有序表进行折半查找的判定树,并求其等概率时查找胜利的平均查找长度.14.已知如下列图的有向网,试利用Dijkstra算法求顶点1 到其余顶点的最短路径,并给出算法执行过程中各步的状态.可编辑资料 - - - 欢迎下载精品_精品资料_15. 假定用于通信

21、的电文由个字母a,b,c,d,e,f,g,h 组成,各字母在电文中显现的频率分别为, ,.试为这个字母设计不等长Huffman 编码,并给出该电文的总码数.16. 已知一棵二叉树的中序和前序序列如下,试画出该二叉树并求该二叉树的后序序列. 作为其储备结构.请写一算法,求该二叉树中叶结点的个数.2. 编写在以 BST 为树根指针的二叉搜寻树上进行查找值为item 的结点的非递归算法,如查找item 带回整个结点的值并返回 ture,否就返回 false.bool Find .5. 设 A=a1,.,am 和 B=b1,.,bn 均为次序表, A 和 B分别为 A 和 B 中除去最大共同前缀后的子

22、表.如 A=B= 空表, 就 A=B .如 A= 空表,而 B空表,或者两者均不为空表,且 A 的首元小于 B 的首元,就 AB .试写一个比较 A ,B 大小的算法.6. 已知单链表 a 和 b 的元素按值递增有序排列 , 编写算法归并 a和 b 得到新的单链表 c, c 的元素按值递减有序.7. 编写递归算法,对于二叉树中每一个元素值为 x 的结点,删去以它为根的子树,并释放相应的空间.8. 编写算法判别T 是否为二叉排序树.9. 试写一算法,判定以邻接表方式储备的有向图中是否存在由顶点V i 到顶点 V j 的路径 ij ）.留意：算法中涉及的图的基本操作必需在储备结构上实现.参考答案一

23、、 判定题12345 6 789 10 可编辑资料 - - - 欢迎下载精品_精品资料_11 12 13 14 15 16 17 18 19.20. 21. 22. 23. 24. 25. 26.27. 28.二、单项选择题1 A2 B 3 B 4 D5 C6 A 7 C8 C9C10 B11A12C13.B14.D15.A16.A17.D18.C19.C20.A21.B22.A23.B24.D25.C26.B27C28.D29.B30.A31.A32.B33.D34.A35.C36.C37.D 38.C 39.D 40.A 41.B42.C 43.D 44.C45.A 46.A 47.B 4

24、8. C三 运算与算法应用题解答平均长度2、解：画图 = 10 , 这 就 要 求 2 趟 快 速 排 序 后 , 算 法 结 束 .所以,列举出来的序列,要求在做 partition 的时候,正好将序列平分14132657或4137652或4537612可编辑资料 - - - 欢迎下载精品_精品资料_2搜寻胜利的平均搜寻长度为l 12*1+2+l+l+l+l+2+4+5+2+5+6： 3l 125 答案： 1djbaechif 2abdjcefhi 3jdbeihfca01078150357452031233612或 4 1 3 5 6 2 7 .2按自己序列完成01234567891011

25、1213AprAugDecFebJanMarMayJuneJulySepOctNov1211112452566.在这个 AVL树中删除根结点时有两种方案:【方案 1】在根的左子树中沿右链走究竟, 用5递补根结点中原先的6, 再删除5 所在的结点.【方案 2】在根的右子树中沿左链走究竟, 用7递补根结点中原先的6, 再删除7 所在的结点.7.划分次序划分结果第一次382440 4656809579其次次243840 4656809579第三次2438404656809579第四次2438404656809579第五次2438404656798095第六次24384046567980958 、12

26、34567891112查找胜利的平均查找长度：ASL SUCC =14/10= 1.49 、此二叉树的后序遍历结果是：EDCBIHJGFA10. 13 7 1l 711 2l 25 34 38 404679 56 578012.12.A 深度遍历： 1,2 , 3 , 8, 4, 5, 7 , 6 或 1 , 2 , 3, 8, 5, 7 , 4,（ B）广度遍历：1 ,2, 4,6 , 3, 5 , 7,8（ C）（ D）拓扑序列：最短路径：1 ,2, 4,6 , 5, 3 , 7,81 ,2, 5,7 , 813.（ E）关键路径：1 ,6, 5,3 , 8可编辑资料 - - - 欢迎下载

27、精品_精品资料_ASL succ =1+2X2+3X4+4X3） /10=2.914. 源点终点最短路径路径长度121, 3 , 21931, 31541,3 , 2 , 42951, 3, 52961,3 , 2 , 4, 64415. 已知字母集 a, b, c, d, e, f, g, h次数, , 就 Huffman 编码为 5 分）abcdefgh可编辑资料 - - - 欢迎下载精品_精品资料_电文总码数为2 分）可编辑资料 - - - 欢迎下载精品_精品资料_ * * * * * * * *图2 分）1000139610101可编辑资料 - - - 欢迎下载精品_精品资料_0171

28、22253610可编辑资料 - - - 欢迎下载精品_精品资料_71011111010345616. 树略）后序序列： c,e, d, b, i, j, h,g, f, a5+4 分）17. 方案 1.哈夫曼编码先将概率放大 100 倍,以便利构造哈夫曼树.w=7,19,2,6,32,3,21,10 ,按哈夫曼规章：【 】, 19,21,32可编辑资料 - - - 欢迎下载精品_精品资料_100 ）40 ）60 ）10 / 1401010121 329101可编辑资料 - - - 欢迎下载精品_精品资料_01 01710 601可编辑资料 - - - 欢迎下载精品_精品资料_19213228

29、）（ 17）11） 710 6+40.07+0.06+0.104+50.02+0.00131=1.44+0.09.20+60.25=2.61方案 2 的 WPL 30.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03=35100.3251006111110.0361010.320.03结方案比较：字母编号对应编码显现频率字母编号对应编码显现频率111000.0710000.072000.1920010.193111100.0230100.02论7：哈夫曼编码01优于等长二进0.制21编码71100.21811010.1081110.10四、算法设计题：1二叉树实行次序

30、结构储备,是按完全二叉树格式储备的.对非完全二叉树要补上“虚结点”.由于不是完全二叉树,在次序结构储备中对叶子结点的判定是依据其左右子女为0.叶子和双亲结点下标间的关系满意完全二叉树的性质.intLeaves inth /求深度为 h 以次序结构储备的二叉树的叶子结点数hh intBT . intlen=2 -1, count=0. /BT是二叉树结点值一维数组,容量为2fori=1.i /数组元素从下标 1 开头存放ifBTi.=0/假定二叉树结点值是整数,“虚结点”用0 填充if i*2len count+./第 i 个结点没子女,确定是叶子elseifBT2*i=0& 2*i+1coun

31、t+ . /无左右子女的结点是叶子returncount /终止 Leaves2.boolFindBtreeNode*BST , ElernType item ）whileBST ； =NULL ）ifdata） item=BST一data. return true. else ifdata BSTBST 一left .else BST=BST 一right .returnfalse .3. Lnode *P=HL .HL=NULL.可编辑资料 - - - 欢迎下载精品_精品资料_While p.=nullLnode*q=p .P=p nex.tq next=HL .HL=q .4. int

32、CountBTreeNode* BT统计出二叉树中全部叶子结点数 ifBT=NULLreturn O.else ifBT-left=NULL&BT-right=NULLreturn 1.else return CountBT-left+CountBT-right. 5. int Compare-ListSqList a, SqList b/a,b为次序表,如 ab 时,返回 1 i=0 .while i & i & a.elemi=b.elemi +i.switch case i=a.length & i=b.length : return 0. break .case i=a.length & i|i=a.length-1 & i=b.length-1 & a.elemi : return -1.break .default : return 1./Compare-List6. void MergeListLinkList &a, LinkList &b, LinkList &c /已知单链表 a 和 b 的元素按值递增有序排列/归并 a 和 b 得到新的单链表c,c 的元素按值递减有序c=a . p=a-next. q=b-next. c-next=NULL .while p & qif p-datadata pn=p-next . p-next=c-next