2022年数据结构习题第九章查找答案 .pdf

学习必备欢迎下载第 9 章集合一选择题1.C 2.A 3.1D 3.2C 4.D 5.B 6.D 7.D 8.C 9.A 10.D 11.B 12.1C 12.2C 13.1C 13.2D 13.3G 13.4H 14.1E 14.2B 14.3E 14.4B 14.5B 15.1B 15.2A 16.A 17.C 18.C 19.C 20.D 21.B 22.C 23.B 24.C 25.1B 25.2F 25.3I 26.A 27.D 28.C 29.1A 29.2C 30.B 31.D 32.D 33.C 34.D 35.1D 35.2C 36.C 二判断题1. 2. 3. 4. 5. 6. 7. 8. 9. 10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.部分答案解释如下。4不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。8哈希表的结点中可以包括指针，指向其元素。11单链表不能使用折半查找方法。20按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。 这种插入就不是插入到叶子下面。21 从平衡因子定义看， 完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。 但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。23某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。24在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。26只有被删除结点是叶子结点时命题才正确。三填空题1n n+1 24 36,9,11,12 45 526（第 4 层是叶子结点， 每个结点两个关键字） 61,3,6,8,11,13,16,19 75,96 8m-1, m/2 -1 92,4,3 10 (1) 哈希函数 (2) 解决冲突的方法 (3) 选择好的哈希函数 (4) 处理冲突的方法 (5) 均匀 (6)简单11 AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。12小于等于表长的最大素数或不包含小于20 的质因子的合数 1316 14 2n+1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 34 页学习必备欢迎下载15 (1)45 (2)45 (3)46 （块内顺序查找） 16k(k+1)/2 1730， 31.5 （块内顺序查找）18 (1) 顺序存储或链式存储 (2)顺序存储且有序 (3) 块内顺序存储，块间有序 (4) 散列存储19 (n+1)/2 20(n+1)/n*log2(n+1)-1 21结点的左子树的高度减去结点的右子树的高度22 (1) 顺序表 (2) 树表 (3) 哈希表 (4) 开放定址方法(5) 链地址方法 (6) 再哈希 (7) 建立公共溢出区23直接定址法 24 logm/2()+1 25O(N) 26n(n+1)/2 27 54 2831 2937/12 30主关键字 31左子树右子树32插入删除 33 14 34(1)126 (2)64 (3)33 (4)65 35（ 1）low=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=0 36 (1) k (2) Irear 38 (1)p!=null (2)pf=p (3)p!=*t (4)*t=null 四应用题1概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。2（ 1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址（ 2）散列表存储中解决碰撞的基本方法：开放定址法形成地址序列的公式是：Hi=（ H（key）+di）% m ，其中 m是表长，di是增量。根据di取法不同，又分为三种：adi =1 ，2， m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。bdi =12，-12，22，-22，k2（km/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3 （j 为整数）的素数时才有可能。cdi = 伪随机数序列，称为随机探测再散列。再散列法 Hi=RHi（key） i=1 ， 2， k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。链地址法将关键字为同义词的记录存储在同一链表中，散列表地址区间用H0.m-1表示， 分量初始值为空指针。凡散列地址为i （0 i m-1）的记录均插在以Hi为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是元素个数受表长限制。建立公共溢出区设 H0.m-1为基本表，凡关键字为同义词的记录，都填入溢出区O0.m-1。（3） 用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i （0i m-1）的第一精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 34 页学习必备欢迎下载个关键字存储在地址空间向量第i 个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表， 具有上面的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以指针相连。节省了空间，但易产生“堆积”，查找效率低。（4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。（5）记录负载因子3评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2 题。4哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.650.9 。解决冲突方法见上面2 题。5不一定相邻。哈希地址为i （0i m-1）的关键字，和为解决冲突形成的探测序列i 的同义词，都争夺哈希地址i 。6散列地址0 1 2 3 4 5 6 7 8 9 关键字14 01 9 23 84 27 55 20 比较次数1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字 27 为例： H（27）=27%7=6 （冲突） H1=（6+1）%10=7 （冲突）H2=（6+22）%10=0 （冲突） H3=（6+33）%10=5 所以比较了4 次。7由于装填因子为0.8 ，关键字有8 个，所以表长为8/0.8=10 。（1）用除留余数法，哈希函数为H（key）=key % 7 （2）散列地址0 1 2 3 4 5 6 7 8 9 关键字21 15 30 36 25 40 26 37 比较次数1 1 1 3 1 1 2 6 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i （0i m-1）时的查找次数。本例中m=10 。故查找失败时的平均查找长度为：ASLunsucc=（9+8+7+6+5+4+3+2+1+1）/10=4.6 ASLsucc =16/8=2（4）int Delete （int hn，int k ） / 从哈希表hn 中删除元素k，若删除成功返回1，否则返回0 i=k%7；/ 哈希函数用上面（1），即 H（key） =key % 7 if （hi= maxint）/maxint解释成空地址printf（“无关键字 %dn”， k）； return （0）； if （hi=k）hi=-maxint ；return （1）； /被删元素换成最大机器数的负数else / 采用线性探测再散列解决冲突 j=i ; for （d=1；d n-1 ；d+） i=（j +d）%n ； / n为表长，此处为10 if （hi= maxint）return (0); /maxint解释成空地址if （hi=k） hi=-maxint；return （1）； / for printf（“无关键字%dn”， k）； return (0)精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 34 页学习必备欢迎下载 8散列地址0 1 2 3 4 5 6 7 8 9 关键字15 24 10 19 17 38 18 40 比较次数1 1 2 1 4 5 5 5 哈希表 a: ASLsucc=24/8=3 ；散列地址0 1 2 3 4 5 6 7 8 9 关键字15 17 24 10 19 40 38 18 比较次数1 3 1 2 1 2 4 4 哈希表 b: ASLsucc =18/8 9（ 1）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字13 22 53 1 41 67 46 51 30 比较次数1 1 1 2 1 2 1 1 1 （2）装填因子 =9/13=0.7 （3）ASLsucc =11/9 （ 4）ASLunsucc =29/13 10 11ASLsucc=19/12 12常用构造哈希函数的方法有：（1）数字分析法该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。（2）平方取中法将关键字值的平方取中间几位作哈希地址。（3）除留余数法 H （key）=key%p，通常 p 取小于等于表长的最大素数。（4）折叠法将关键字分成长度相等（最后一段可不等）的几部分，进行移位叠加或间界叠加，其值作哈希地址。（5）基数转换法两基数要互素，且后一基数要大于前一基数。在哈希表中删除一个记录，在拉链法情况下可以物理地删除。 在开放定址法下，不能物理地删除， 只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 关键字14 01 68 27 55 19 20 84 79 23 11 10 比较次数1 2 1 4 3 1 1 3 9 1 1 3 13（ 1）散列地址0 1 2 3 4 5 6 7 8 9 10 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 34 页学习必备欢迎下载关键字4 12 49 38 13 24 32 21 比较次数1 1 1 2 1 2 1 2 ASLsucc = （ 1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 （2） 13 题图 ASLsucc =11/8 ASLunsucc=19/11 14题（ 2） ASLsucc=13/8 ASLunsucc=19/11 值得指出， 对用拉链法求查找失败时的平均查找长度有两种观点。其一， 认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9 和 10 均为比较 1 次失败，而哈希地址1 和 3 比较 2 次失败，其余哈希地址均为比较3 次失败，因此，查找失败时的平均查找长度为 19/11 ， 我们持这种观点。 还有另一种理解， 他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11 14由 hashf(x)=x mod 11 可知，散列地址空间是0 到 10，由于有 8 个数据，装载因子取0.7 。（1）散列地址0 1 2 3 4 5 6 7 8 9 10 关键字33 1 13 12 34 38 27 22 比较次数1 1 1 3 4 1 2 8 ASLsucc=21/8 ASLunsucc=47/11 15（1）ASL=42/12 （2）a：ASLsucc=31/12 （2）b：ASLsucc=18/12 ( 注：本题 x 取小于等于x 的最大整数) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 34 页学习必备欢迎下载1617查找时，对关键字49,22,38,32,13各比较一次，对21,18 各比较两次18 ASLsucc = 15/1019 ASLsuss =16/11 20散列地址0 1 2 3 4 5 6 7 8 9 10 11 关键字231 89 79 25 47 16 38 82 51 39 151 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 34 页学习必备欢迎下载比较次数1 1 1 1 2 1 2 3 2 4 3 ASLsucc =21/11 21散列地址0 1 2 3 4 5 6 7 8 9 10 关键字22 33 46 13 01 67 41 53 30 比较次数1 2 1 2 4 5 1 1 3 22（1）散 列地址0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 关 键字32 17 63 49 24 40 10 30 31 46 47 比 较次数1 1 6 3 1 2 1 1 1 3 3 （2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63 比较。（3）查找关键字60，H（k）=60 MOD 16=12，散列地址12 内为空，查找失败。（4）ASLsucc=23/11 23设用线性探测再散列解决冲突，根据公式Snl （ 1+1/ （1- ） /2 。可求出负载因子为 =0.67 。再根据数据个数和装载因子，可求出表长m=15/0.67 ，取 m=23 。设哈希函数 H（key）=（关键字首尾字母在字母表中序号之和）MOD 23 。从上表求出查找成功时的平均查找长度为ASLsucc=19/152.0 ，满足要求。24（ 1）哈希函数H（key）=（关键字各字符编码之和）MOD 7 （2）散列地址0 1 2 3 4 5 6 7 8 9 关键字be cd aa ab ac ad bd bc ae ce 比较次数1 2 1 1 1 1 1 3 3 9 25 =0.7 ，所以表长取m=7/0.7=10 散列地址0 1 2 3 4 5 6 7 8 9 关键字SAT WED SUN MON TUE THU FRI 比较次数6 1 1 1 2 3 4 ASLsucc=18/7 ASLunsucc=32/10 26（ 1）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字27 53 2 31 19 20 8 18 比较次数3 1 1 1 1 1 1 2 （2）ASLsuss =11/8 27（ 1）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字0 3 29 200 32 45 58 100 10 126 400 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 34 页学习必备欢迎下载比较次数1 1 2 1 1 2 3 1 1 3 3 关键字 29 和 45 各发生 一次碰撞，关键字58,126 和 400 各发生 两次碰撞，其余关键字无碰撞。（2）散列地址0 1 2 3 4 5 6 7 8 9 10 11 12 关键字58 10 100 3 200 32 400 0 45 126 29 比较次数1 1 2 1 3 1 3 8 1 2 1 发生碰撞次数：100，126 一次； 200， 400 两次； 0 七次。其余关键字无碰撞。28由 =0.75 ，得表长m=11/0.75=15 （1）散列函数H（k）=k MOD 13（p 取小于等于表长的最大素数）（2）因为 p=13，散列地址取0 到 12，用链地址法解决冲突，实际长就取13。（2）ASLsucc=18/11 （3）ASLunsucc=24/13 29在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后， 要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。30 m阶的 B+树和 B-树主要区别有三：（1）有 n 棵子树的结点中含有n（B-树中 n-1）个关键字；（ 2）B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接；（3）B+树的非终端结点可以看成是索引部分，结点中只含其子树（根结点）中最大（或最小）关键字。B+树的查找既可以顺序查找，也可以随机查找， B-只能顺序查找。31本题等价于“含有n 个关键字的m阶 B-树的最大高度是多少”？一次检索中最多走一条从根到叶子的路径，由于根结点至少有两棵子树，其余每个（除叶子）结点至少有m/2棵子树，则第三层至少有m/2 *2 个结点，第l+1 层至少有2* m/2l-1个结点。设B-树深度为 l+1 ，即第 l+1 层是叶子结点，叶子结点数是n+1（下面推导），故有n+12* m/2l-1，即 l logm/2（）+1。附：推导 B- 树中叶子结点数s 与关键字数n 的关系式： s=n+1 设 B-树某结点的子树数为 Ci，则该结点的关键字数Ni=Ci-1。对于有k 个结点的B-树，有 Ni=(Ci-1)= Ci-k （1i k） （ 1）因为 B树上的关键字数，即Ni=n （1 i k） （ 2）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 34 页学习必备欢迎下载而 B-树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为 s；则Ci=(k-1)+s （1i k） （ 3）综合（ 1）（ 2）（ 3）式，有s=n+1。证毕。32表长 m=12/0.6=20 （1） H （key）=key MOD 19 （2）两次碰撞。开地址线性探测法解决冲突，即是用拉链法解决冲突。见本章四第2题（ 2）第 32 题用拉链法解决冲突33由于地址空间为10，且从 100 开始，故散列函数选为 H（key）=key%7+100。散列地址100 101 102 103 104 105 106 107 108 109 关键字98 63 79 17 53 19 61 75 46 49 比较次数1 2 1 1 1 1 2 3 5 10 用线性探测再散列解决冲突，ASLsucc=27/10 3435精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 34 页学习必备欢迎下载36 第一层有 1 个结点，第二层至少有2 个结点，第三层有2* m/2 个结点，第四层有2* m/22个结点，第h 层至少有2* m/2h-2个结点（ h 2）。结点总数是1+2+2* m/2 +2* m/22+2* m/2h-2=2* m/2h-1-1 3738. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 34 页学习必备欢迎下载3940（该题答案不唯一。如删 P时，亦可将双亲结点中M下来与 N一起并入左兄弟成为（K L M N）41满二叉检索树可以看作是三阶B-树（ 23 树）。 B- 树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”（查找失败结点）的定义。4243 B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。44 含 9 个叶子结点的3阶 B-树至少有4 个非叶子结点， 当每个非叶子结点均含3 棵子树，第三层是叶子结点时就是这种情况。当4 层 3 阶 B-树有 10 个叶子结点时，非叶子结点达到最大值 8 个，其中第一层一个，第二层两个，第三层五个非叶子结点。45在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn) ，而在中序遍历输出的序列中查找关键字K，时间复杂度是O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1） /2 ，时间复杂度也是O（n）。46按中序遍历序列将值19 依次标上。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 34 页学习必备欢迎下载47ASLsucc=(1*1+2*2+4*3+ 4*4)/11=3 3/11 48. ASLsucc=32/10 49. （2）10,12,15,20,24,28,30,35,46,50,55,68 （3）ASLsucc=41/12 50精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 34 页学习必备欢迎下载5152序列（ 2）不可能是二叉排序树中查到363 的序列。查到501 后，因363llink,flag）； / 中序遍历左子树if （pre=null）pre=t ；/ 中序遍历的第一个结点不必判断elseif （pre-datadata）pre=t ；/ 前驱指针指向当前结点else flag=flase； /不是完全二叉树Judgebst （t-rlink, flag ）； / 中序遍历右子树/JudgeBST算法结束本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：int JudgeBST（BTree t ） /判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回false if （t=null）return true；if （ Judgebst （t-llink）& Judgebst （t-rlink） / 若左右子树均为二叉排序树 m=max（t-llink）； n=min（t-rlink）； / 左子树中最大值和右子树中最小值return （t-datam & t-datarlink！=null ）p=p-rlink；return p-data ； int min （BTree p ）/ 求二叉树 右子树的最小值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 34 页学习必备欢迎下载 if （ p=null ） return maxint； / 返回机器最大整数else while （p-llink！=null ）p=p-llink；return p-data； 2 题目分析 借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按 k 个集合分块 （元素个数不一定相等），索引表中有两个域，一是各集合最后一个元素在数据表中的位置（一维数组中的下标），二是集合的个数（k）。实现数据运算时，根据给定的二元组（ i ，x），首先在索引表中找到集合i 的位置，然后在数据表中查找x。如查到x ，则查找成功，返回x 在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入x，同时修改索引表。typedefstruct datatype data；rectype；typedefstruct int a ； /a 数组容量够大，存储各集合最后一个数据在数据表中的下标int k； /集合个数 index；int SetSearch_Insert（rectype R，index id，datatype x，int i ） /数据表 R，查找第 i 个集合的 元素 x，若查找成功，返回其位置，否则将其插入第i个集合 if （iid.k）printf（“无第 %d个集合 n ”， i ）； exit （0）； if （i=1 ）first=0；else first=id.ai-1+1； /first指向第 i 个集合在数据表的首址last= id.ai；/last是第 i 个集合在数据表中的末址for （ j=first；j last ；j+ ） if （ Rj=x ）return （j ）； / 查找成功for （ j=id.aid.k； jid.ai；j-） /查找失败，将x 插入数据表 Rj+1=Rj；/ 元素后移Rj+1=x ； /将 x 插入到原第i 个集合最后一个元素之后。for （ j=i ；j k；j+ ）id.aj+；/ 修改索引表中各集合最后一个元素的下标结束 SetSearch_Insert 由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入（2,11.2 ）和（ 1,5.3 ），数据表前后状态如下：插入前0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 10.2 1.7 4.8 16.2 1.7 8.4 0.5 4.8 4.2 3.6 2.7 5.1 3.9 插入后10.2 1.7 4.8 16.2 5.3 1.7 8.4 0.5 11.2 4.8 4.2 3.6 2.7 5.1 3.9 插入前 , 索引表中 a 数组的内容是3，6，12，插入后修改为4，8，14。3（ 1）非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。void Creat_BST （BiTree bst，datatype K，int n ） / 以存储在数组K中的 n 个关键字，建立一棵初始为空的二叉排序树。 for （i=1 ；i n；i+ ） p=bst；f=null；/ 在调用 Creat_BST 时， bst=null while （p!=null）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 34 页学习必备欢迎下载if （p-dataRLINK； / f是 p 的双亲elseif （p-dataKi） f=p ； p=p-LLINK； s=（BiTree ）malloc （ sizeof （BiNode）； / 申请结点空间 s-data=Ki；s-LLINK=null；s-RLINK=null ；if （f=null） bst=s ； /根结点elseif （s-datadata）f-LLINK=s ；/ 左子女else f-RLINK=s；/ 右子树根结点的值大于等于根结点的值 /算法结束（2） 题目分析 本题要求 输出 遍历二叉排序树的嵌套 括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。void Print（BiTree t） /以嵌套括号表示结构打印二叉排序树 if （t ！=null ）printf（t-data ）； / 打印根结点值if （t-LLINK | t-LLINK）； / 左子女和右子女中至少有一个不空 printf（“（”）； /输出左括号 Print（t-LLINK ）； /输出左子树的嵌套括号表示if （t-RLINK ）printf（“，”）；/ 若右子树不空，输出逗号 Print（t-RLINK ）； /输出右子树的嵌套括号表示 printf（“）”）； /输出右括号/if/Print 4 void Delete（BSTree t ，p） / 在二叉排序树t 中，删除 f 所指结点的右孩子（由p 所指向）的算法 if （p-lchild=null）f-rchild=p-rchild；free （p）； /p无左子女else /用 p 左子树中的最大值代替p 结点的值 q=p-lchild；s=q；while （q-rchild）s=q ；q=q-rchild ；/ 查 p 左子树中序序列最右结点if （s=p-lchild） /p左子树的根结点无右子女 p-data=s-data；p-lchild=s-lchild；free （s）； else p-data=q-data；s-rchild=q-lchild；free （q）； /Delete 5 题目分析 上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中最小值（中序遍历第一个）结点代替被删结点。void Delete(BSTree bst,p,fp) /在二叉排序树bst 上，删除fp 所指结点的左子女（由p 所指向）的算法。if （ !p-lchild） fp-lchild=p-rchild；free （p）； /p无左子女 else if（ !p-rchild）fp-lchild=p-lchild； free （p）； /p无右子女 else / p有左子女和右子女q=p-rchild；s=q；/ 用 p 右子树中的最小值代替p 结点的值while （q-lchild）s=q ；q=q-lchild ；/查 p 右子树中序序列最左结点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 34 页学习必备欢迎下载if （s=p-rchild） /p右子树的根结点无左子女 p-data=s-data； p-rchild=s-rchild；free （s）； else p-data=q-data；s-lchild=q-rchild；free （q）； /Delete 6 题目分析 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树， 则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。void Delete(BSTree bst, keytype X) /在二叉排序树bst 上，删除其关键字为X的结点。 BSTree f,p=bst; while (p & p-key!=X) /查找值为X的结点if (p-keyX) f=p; p=p-lchild; else f=p; p=p-rchild; if (p=null) printf(“无关键字为X的结点 n ”); exit(0); if p-lchild=null /被删结点无左子树if (f-lchild=p) f-lchild=p-rchild;/将被删结点的右子树接到其双亲上else f-rchild=p-rchild; else q=p; s=p-lchild; /被删结点有左子树while (s-rchild !=null) /查左子树中最右下的结点（中序最后结点） q=s; s=s-rchild; p-key=s-key; /结点值用其左子树最右下的结点的值代替if (q=p) p-lchild=s-lchild;/被删结点左子树的根结点无右子女else q-rchild=s-lchild; /s是被删结点左子树中序序列最后一个结点 free(s); /算法结束7int Search （rectype r ，int n，keytype k）/ 在 n 个关键字从小到大排列的顺序表中，查找关键字为k 的结点。rn+1.key=MAXINT；/ 在高端设置监视哨 i=1 ；while （ri.keyk）i+ ；if (rn+1.key=k) return （i%（ n+1）；else return (0) / 算法 search 结束查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为（n+1）/2 。8FUNC Srch_Mtree （t:mblink； k：keytp ）： result； /在根结点指针为t 的 m阶 B-树上查找关键字k，返回记录（ pt ，i ，tag ）。若查找成功，/ 置 tag=1 ，等于 k 的关键字即pt 所指结点中第i 个关键字；若查找失败，关键字k应插入/pt所指结点的第i 和第 i+1 个关键字之间。 p:=t；q:=null；found:=false；i:=0 ；/p指向待查结点，q 指向 p 的双亲结点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 34 页学习必备欢迎下载WHILE （pNIL）AND NOT found DO n:=p.keynum；i:=search（p,k ）； / 在 p.key1.n中查找IF （i0 ）AND （p .keyi=k）THEN found ：=true ELSE q:=p ；p:=p .ptri； IF found THENreturn （p,i,1）/ 查找成功ELSE return （q，i ，0）/ 查找失败，返回插入位置 算法讨论 插入时，若所在结点关键字keynumk） return （BinSrch （r,k ，mid+1，high ） ; elsereturn （BinSrch （r,k ，low ，mid-1 ） ; elsereturn （0）； / 查找失败。/ 算法结束算法时间复杂度为O（logn ）。11 题目分析 在 Trie树上查找给定值KEY的过程如下： 沿和给定值相应的指针向下，直至叶子结点， 若叶子中的关键字和KEY相等， 则查找成功； 若分枝结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。typedef enumLEAF，BRANCHNodeKind ；/ 结点种类 叶子，分枝 typedefstruct TrieNode NodeKind kind； union structKeyType K ；Record *infoptr lf； /叶子结点structTrieNode *ptr27；int num bh ； /分枝结点 ； TrieNode，*TrieTree；/ 键树类型Record *SearchTrie（ TrieTree T，KeyType KEY） /在 Trie 树 T 中查找关键字等于K 的记录。 for （P=T，i=0 ； /对 KEY的每个字符逐个查找 P & P-kind=BRANCH & ibh.ptrord（KEY.chi） ，+i ）； /ord求字符在字母表中的序号if （P & P-kind=LEAF & P-lf.K=KEY ）return P-lf.infoptr；/ 查找成功elsereturn null； /结束 SearchTrie 12 题目分析 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针， （第 i 个）单链表结点有两个域，一个是哈希地址为i 的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。typedefstruct node keytype key；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 34 页学习必备欢迎下载struct node *next； HSNode ； *HSList typedefstruct node *HLK ；void Delete （HLK HT ，key