《2023年数据结构习题第九章查找超详细解析答案.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构习题第九章查找超详细解析答案.pdf（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习必备 欢迎下载 第 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
2、.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。但是，平衡二叉树本
3、质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。23 某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。24在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。26只有被删除结点是叶子结点时命题才正确。三填空题 1n n+1 24 36,9,11,12 45 526（第 4 层是叶子结点，每个结点两个关键字）6 1,3,6,8,11,13,16,19 75,96 8m-1,m/2-1 92,4,3 10(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单 11AVL树（高
4、度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于 1。12小于等于表长的最大素数或不包含小于 20 的质因子的合数 1316 14 2n+1 学习必备 欢迎下载 15(1)45(2)45(3)46（块内顺序查找）16 k(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)链地址
5、方法(6)再哈希(7)建立公共溢出区 23直接定址法 24logm/2()+1 25O(N)26n(n+1)/2 2754 2831 2937/12 30主关键字 31左子树 右子树 32插入 删除 3314 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
6、）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （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=伪随机数序列，称为随机探测再
7、散列。再散列法 Hi=RHi（key）i=1，2，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H0.m-1 表示，分量初始值为空指针。凡散列地址为 i（0i m-1）的记录均插在以 Hi为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是元素个数受表长限制。建立公共溢出区 设 H0.m-1 为基本表，凡关键字为同义词的记录，都填入溢出区 O0
8、.m-1。（3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为 i（0i m-1）的第一增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 个关键字存储在地址空间向量第 i 个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以指针相连。节省了空间，但易产生
9、“堆积”，查找效率低。（4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。（5）记录 负载因子 3评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面 2 题。4哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取 0.650.9。解决冲突方法见上面 2 题。5不一定相邻。哈希地址为 i（0i m-1）的关键字，和为解决冲突形成的探测序列 i 的同义词，都争夺哈希地址 i。6 散列地址 0 1 2 3
10、 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
11、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”
12、，k）；return （0）；if（hi=k）hi=-max int ；return（1）；/被删元素换成最大机器数的负数 else /采用线性探测再散列解决冲突 j=i;for（d=1；dn-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)增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同
13、只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 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
14、 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）基数转换法 两基数要互素，且后一基数要大于前一基数。在哈希表中删除
15、一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。散列地址 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 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故
16、不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 关键字 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、
17、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
18、 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 的最大整数)增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 16 17查找时，对关键字 49,22,38,32,13各比较一次，对 21,18 各比较两次 18ASLsucc=15/10 19ASLsuss=16/11 20 散列地址
19、 0 1 2 3 4 5 6 7 8 9 10 11 关键字 231 89 79 25 47 16 38 82 51 39 151 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 比较次数 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）
20、散 列地址 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。再根据数据个数和装载因子，可求
21、出表长 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 F
22、RI 比较次数 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 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长
23、度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 比较次数 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
24、 MOD 13（p 取小于等于表长的最大素数）（2）因为 p=13，散列地址取 0 到 12，用链地址法解决冲突，实际长就取 13。（2）ASLsucc=18/11 （3）ASLunsucc=24/13 29在 B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。30m阶的 B+树和 B-树主要区别有三：（1）有 n 棵子树的结点中含有 n（B-树
25、中 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 层是叶子结
26、点，叶子结点数是 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 （1i k）（2）增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 而 B-树上的子树数
27、可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为 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
28、 49 比较次数 1 2 1 1 1 1 2 3 5 10 用线性探测再散列解决冲突，ASLsucc=27/10 34 35 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 36 第一层有 1 个结点，第二层至少有 2 个结点，第三层有 2*m/2 个结点，第四层有 2*m/22个结点，第 h 层至少有 2*m/2h-2个结点（h2）。结点总数是 1+2+2*m/2+2*m/22+2*m/2h-2=2*m/2h-1-1 37 38.增序列
29、的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 39 40（该题答案不唯一。如删 P时，亦可将双亲结点中 M下来与 N一起并入左兄弟成为（K L M N）41满二叉检索树可以看作是三阶 B-树（23 树）。B-树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”（查找失败结点）的定义。42 43B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。44 含 9 个叶子结点的
30、3 阶 B-树至少有 4 个非叶子结点，当每个非叶子结点均含 3 棵子树，第三层是叶子结点时就是这种情况。当 4 层 3 阶 B-树有 10 个叶子结点时，非叶子结点达到最大值 8 个，其中第一层一个，第二层两个，第三层五个非叶子结点。45在二叉排序树上查找关键字 K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字 K，时间复杂度是 O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是 O（n）。46按中序遍历序列将值 19 依次标上。增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉
31、树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 47 ASLsucc=(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 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 51 52序列（2）
32、不可能是二叉排序树中查到 363 的序列。查到 501 后，因 363llink,flag）；/中序遍历左子树 if（pre=null）pre=t；/中序遍历的第一个结点不必判断 else if（pre-datadata）pre=t；/前驱指针指向当前结点 else flag=flase；/不是完全二叉树 Judgebst（t-rlink,flag）；/中序遍历右子树/JudgeBST算法结束 本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：int JudgeBST（BTre
33、e 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）/求二叉树右子树的最小值 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉
34、树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 if（p=null）return maxint；/返回机器最大整数 else while（p-llink！=null）p=p-llink；return p-data；2 题目分析 借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按 k 个集合分块（元素个数不一定相等），索引表中有两个域，一是各集合最后一个元素在数据表中的位置（一维数组中的下标），二是集合的个数（k）。实现数据运算时，根据给定的二元组（i，x），首先在索引表中找到集合 i 的位置，然后在数据表中查找
35、x。如查到x，则查找成功，返回 x 在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入 x，同时修改索引表。typedef struct datatype data；rectype；typedef struct 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”
36、，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
37、由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入（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）非递归建立
38、二叉排序树，在二叉排序树上插入的结点都是叶子结点。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）增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 if（p-dataRLINK；/f是 p 的双亲 el
39、se if（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；/根结点 else if（s-datadata）f-LLINK=s；/左子女 else f-RLINK=s；/右子树根结点的值大于等于根结点的值 /算法结束（2）题目分析 本题要求输出遍历二叉排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要
40、输出右括号，在左右子树均空情况下，则不输出括号。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）
41、/在二叉排序树 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
42、 题目分析 上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中最小值（中序遍历第一个）结点代替被删结点。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=
43、q；q=q-lchild；/查 p 右子树中序序列最左结点 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 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 题目分析 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直
44、接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。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
45、=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，key
46、type 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）。若查找成功，
47、/置 tag=1，等于 k 的关键字即 pt 所指结点中第 i 个关键字；若查找失败，关键字 k应插入/pt所指结点的第 i 和第 i+1 个关键字之间。p:=t；q:=null；found:=false；i:=0；/p 指向待查结点，q 指向 p 的双亲结点 增序列的原则若某结点只有右子树而插入元素的关键字小于该结点的关二叉树本质上是二叉排序树完全二叉树不一定是排序树故不能说完全二时的平均查找长度不相同只有被删除结点是叶子结点时命题才正确三填学习必备 欢迎下载 WHILE（pNIL）AND NOT found DO n:=p.keynum；i:=search（p,k）；/在 p.key1.n
48、中查找 IF（i0）AND（p.keyi=k）THEN found：=true ELSE q:=p；p:=p.ptri；IF found THEN return （p,i,1）/查找成功 ELSE return （q，i，0）/查找失败，返回插入位置 算法讨论 插入时，若所在结点关键字 keynumk）return （BinSrch（r,k，mid+1，high）;else return （BinSrch（r,k，low，mid-1）;else return （0）；/查找失败。/算法结束 算法时间复杂度为 O（logn）。11 题目分析 在 Trie 树上查找给定值 KEY的过程如下：沿和给
49、定值相应的指针向下，直至叶子结点，若叶子中的关键字和 KEY相等，则查找成功；若分枝结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。typedef enumLEAF，BRANCHNodeKind；/结点种类叶子，分枝 typedef struct TrieNode NodeKind kind；union structKeyType K；Record*infoptr lf；/叶子结点 structTrieNode*ptr27；int num bh；/分枝结点 ；TrieNode，*TrieTree；/键树类型 Record *SearchTrie（TrieTree
50、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；/查找成功 else return null；/结束 SearchTrie 12 题目分析 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第 i 个）单链表结点有两个域，一个是哈希地址为 i 的关键字，另一个是指向同义词结点的指