发布时间 : 星期日 文章数据结构复习题及参考答案更新完毕开始阅读07758f7bc850ad02df804100
5.试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。
6.已知带头结点的单链表是一个递增有序表，试写一算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。
Head 26 7 50 ^ 15 9
7.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。
8.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回true，否则返回false。
bool Find（BtreeNode*BST，ElemType&item）
9.设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A
10.已知单链表a和b的元素按值递增有序排列, 编写算法归并a和b得到新的单链表c，c的元素按值递减有序。
11.编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 12.编写算法判别T是否为二叉排序树。
第13页共22页
参考答案
一、填空题：
1.4，10 2.n
3.1，2 4.线性结构，树型结构，图型结构 5.n(n-1)/2 n(n-1) 6.增加1 7.O(log2n) O(nlog2n) 8.归并
9. n-1 10.左右子树空 11.1225 12.n(n-1)/2 13.head(A) 14.节省空间 15.L->next=L->prior 或 L->next=L 16. 1044
17. 入栈（插入） ， 出栈（删除） 18. 前驱结点 ， 后继结点 19.中序序列 20.顺序存储结构 ， 有序的 21.O(n) O(1) 22. 行号 列号
h
23. 3 x 2.4 5 ／6 －*＋ 24.(3 -1)/2
33
25. n ， O (n) 26.零个字符的串 ， 零 27.邻接矩阵 ， 邻接表 28.s, p
29.q->next, q 30.两个串的长度相等且对应位置的字符相同 31.200+（6*20+12）= 326 32.1000+((18-10)*6 +(9-5))*4 = 1208 33. (1). (b) (2). (d) 34求矩阵第i列非零元素之和 35.将矩阵第i行全部置为零 36.2. 2; 4; （23，38，15） 37.堆排序、快速排序、归并排序、归并排序、快速排序、堆排序 二、单项选择题： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B B B C B B D A C D B B A D A 16 17 18 19 20 21 22 23 24 252526 27 28 29 ① ② A C C D D B D A C B A B B D A 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 A B B A D B B D A A B B A D B 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 A B C B B D A D C D B C B C C 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 C C D C C C C B A C B A B C D 75 B 三、计算与算法应用题： A 1.普里姆算法从顶点1出发得到最小生成树为： (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 B 2.在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 3.画出下列树对应的二叉树，并写出其先根遍历序列： D C E
F G
先根遍历序列： A B D E G F C
第14页共22页
4.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。
54 29 37 86 71 91 8 31 44 26
29 54 37 86 71 91 8 31 26 44
29 37 54 86 8 31 71 91 26 44
8 29 31 37 54 71 86 91 26 44
8 26 29 31 37 44 54 71 86 91
5.全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364 6.
100 42 48
F 29 B 19
23 29
D H E 15 8 11 14
C 8
7
G A
7.
3
5
平均长度为4.
8.深度优先搜索序列：a，b，f，h，c，d，g，e
第15页共22页
广度优先搜索序列：a，b，c，f，d，e，h，g 9.计算机关键码得到的散列地址 关键码 散列地址 19 6 14 1 23 10 01 1 68 3 20 7 84 6 27 1 在散列表中散列结果
0 1 2 3 4 5 6 7 8 9 10 11 12 14 01 68 27 19 20 84 23 10.对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。这里要求10次，而7 - 1 + 2 * ( 3 - 1 ) = 10，这就要求2趟快速排序后，算法结束。所以，列举出来的序列，要求在做partition的时候，正好将序列平分 (1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2
或 4 1 3 5 6 2 7 ....... (2)按自己序列完成
11.答案：(1)djbaechif (2)abdjcefhi (3)jdbeihfca 12.在这个AVL树中删除根结点时有两种方案:
【方案1】在根的左子树中沿右链走到底,用5递补根结点中原来的6,再删除5所在的结点。 【方案2】在根的右子树中沿左链走到底,用7递补根结点中原来的6,再删除7所在的结点。 13.
划分次序 划分结果 第一次 [38 24 40] 46 [56 80 95 79] 第二次 24 [38 40] 46 [56 80 95 79] 第三次 24 38 40 46 [56 80 95 79] 第四次 24 38 40 46 56 [80 95 79] 第五次 24 38 40 46 56 79 [80 95] 第六次 24 38 40 46 56 79 80 95 14.
0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度： ASL SUCC =14/10= 1.4 15.此二叉树的后序遍历结果是： EDCBIHJGFA 16.13／7 1l／7
四、阅读下列算法，分析它的作用
1.统计单链表中结点的值等于给定值x的结点数。 2.对数组A中的n个元素进行排序，称为起泡算法。 3.该算法的输入结果是：34 91 30 45 63 78
4.该算法的功能是：交换二叉树的左右子树的递归算法。
5.该算法是顺序栈类的进栈算法。 如果栈满返回“满”；否则X元素进栈。 6.该算法是将链表的数据元素输出算法。 输出结果：
a b
第16页共22页