《数据结构与算法》第九章-查找.docx

数据结构与算法第九章 查找答案第二部分考研真题精选一、选择题.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一 个记录，其平均查找长度ASL为（）oA. （n-l）/2 B. n/2 C. （n+l）/2 D. n.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）A. （N+l） /2B.N/2 C.N D. （1+N） *N /2.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（1）,二分法查 找只适用于查找顺序存储的有序表，平均比较次数为（2）。在此假定N为线性表中结点数，且每次查找都是成功的。D.N/2 E.Nlog2N F.N2A.N+1 B.21og2N C.logN.下面关于二分查找的叙述正确的是（C.表必须有序，而且只A.表必须有序，表可以顺序方式存储，也可以链表方式存储能从小到大排列实型或字符型D.表必须有序，且表只B.表必须有序且表中数据必须是整型,能以顺序方式存储1 .对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方 式存储，且数据元素有序.适用于折半查找的表的存储方式及元素排列要求为（）A.链接方式存储，元素无序 B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序.用二分（对半）查找表的元素的速度比用顺序法（）A. 必然快 B.必然慢 C.相等 D.不能确定.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减.具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B.4C. 2.5D.5.折半查找的时间复杂性为（）A.O （n2） B.O （n） C. O （nlogn） D. O （logn）.当采用分快查找时，数据的组织方式为（）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） 的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同.二叉查找树的查找效率与二叉树的（1）有关，在（2）时其查找效率最低（1）：A.高度B.结点的多少C.树型D.结点的位置（2）:A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。2 .要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为.已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子，试编写算法, 删除p所指结点。4 .二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点 后，此树仍然是一棵二叉排序树，并且高度没有增长(注：可不考虑被删除的结点是根的情 况)。5 .设记录R1,R2,Rn按关键字值从小到大顺序存储在数组rL.n中，在rn+l处设立一个 监督哨，其关键字值为+8；试写一查找给定关键字k的算法;并画出此查找过程的判定树, 求出在等概率情况下查找成功时的平均查找长度。6 .元素集合已存入整型数组ALn中，试写出依次取A中各值Ai(I<=i<=n)构造一棵二叉 排序树T的非递归算法：CSBT(T,A).给出折半查找的递归算法，并给出算法时间复杂度性分析。考研真题精选答案一.选择题1.C2.A3.1D3.2C4.D5.B6.D7.D8.C9.A10.D11.B12.1C12.2C13.1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.D25.C26.1A26.2C27.B28.D29.D30.C31.D32.1D32.2C33.C二.判断题1. V 2. V 3.X 4X 5.X 6. V 7. V 8.X 9.X 10.X 11.X 12. V13. V 14X15X 16X 17 V 18X 19. V 20.X 21.X 22.X 23.X 24.X25. V 26 X 27 X 28 V 29 V 30 X 31. X 32. V 33. V 34. X 35. V 36. V 部分答案解释如下。4.不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。8.哈希表的结点中可以包括指针，指向其元素。11.单链表不能使用折半查找方法。20 .按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于 该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下 面。21 .从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是， 平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡 二叉树。23 .某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后 继。24 .在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。26 .只有被删除结点是叶子结点时命题才正确。三.填空题1. n n+12. 43. 6,9,11,124. 55. 26(第4层是叶子结点，每个结点两个关键字)6. 1,3,6,8,11,13,16,197. 5,968. m-1,9. 2,4,310. (1)哈希函数解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简 单AVL树(高度平衡树，高度平衡的二叉排序树)，或为空二叉树，或二叉树中任意结点 左子树高度与右子树高度差的绝对值小于等于lo11. 小于等于表长的最大素数或不包含小于20的质因子的合数13. 16L log 2nJ +114. (1)45 (2)45 (3)46 (块内顺序查找) 16. k(k+l)/217. 30, 31.5 (块内顺序查找)18. (1)顺序存储或链式存储(2)顺序存储且有序(3)块内顺序存储，块间有序(4)散列存储 19. (n+l)/220. (n+l)/n*log2(n+l)-l21.结点的左子树的高度减去结点的右子树的高度. (1)顺序表树表(3)哈希表开放定址方法(5)链地址方法(6)再哈希建立公共溢出区22 .直接定址法24. O(N)25. n(n+l)/226. 5427. 3128. 37/1229.主关键字 30.左子树 右子树31.插入 删除32. 1433. (1)126 (2)64(3)33(4)65(l)rear=mid-l (2)head=mid-i-l (3)head>rear34. (l)p!=null (2)pf=p (3)p!=*t (4)*t二null四.应用题1 .概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答 略。2 . (1)散列表存储的基本思想是用关键字的值决定数据元素的存储地址(2)散列表存储中解决碰撞的基本方法： 开放定址法形成地址序列的公式是：Hi= (H (key) +&) %m,其中m是表长，&是增量。根据&取法不同，又分为三种：a. di = l, 2,，m-1称为线性探测再散列，其特点是逐个探测表空间，只要散列表中 有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散 列地址。b. di=l2, -I2, 22,-22,，±k2 (km/2)称为二次探测再散列，它减少了聚集，但 不容易探测到全部表空间，只有当表长为形如4j+3 (j为整数)的素数时才有可能。c. 4 =伪随机数序列，称为随机探测再散列。再散列法 Hi=RHi (key) i=l, 2,，k,是不同的散列函数，即在同义词产生 碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加 了计算时间。 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用 表示，分量初始值为空指针。凡散列地址为i (OWiWm-1)的记录均插在以Hi为 头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增 加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是元 素个数受表长限制。 建立公共溢出区 设为基本表，凡关键字为同义词的记录，都填入溢出 区O0.m-lo(3)用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的 每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i (OWiWm-1)的第一个 关键字存储在地址空间向量第i个分量的“关键字”域。前者的指针域是动态指针，指向同 义词的链表，具有上面的优缺点；后者实际是静态链表，同义词存在同一地址向量空间(从 最后向前找空闲单元)，以指针相连。节省了空间，但易产生“堆积”，查找效率低。(4)要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。(5)记录负载因子.评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突 的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突 的方法见上面2题。3 .哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比)，它反映了 哈希表的装满程度，该值一般取0.650.9。解决冲突方法见上面2题。4 .不一定相邻。哈希地址为i (OWiWm-1)的关键字，和为解决冲突形成的探测序列i的同 义词，都争夺哈希地址i。散列地址0123456789关键字140192384275520比较次数11123412平均查找长度：ASLsucc= (1 + 1+1+2+3+4+1+2) /8=15/8以关键字27为例：H (27) =27%7=6 (冲突) H尸(6+1) % 10=7 (冲突)H2= (6+22) %io=o (冲突)H3= (6+33) % 10=5所以比较了 4 次。7.由于装填因子为0.8,关键字有8个，所以表长为8/0.8=10。(1)用除留余数法，哈希函数为H (key) =key%7(2)散列地址0123456789关键字2115303625402637比较次数11131126(3)计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i(0WiWm-1)时的查找次数。本例中m=10。故查找失败时的平均查找长度为：ASLUnsucc= (9+8+7+6+5+4+3+2+1 + 1) /10=4.6ASLSUcc =16/8=2(4) int Delete (int hn, int k)从哈希表hn中删除元素k,若删除成功返回1,否则返回。i=k%7； / 哈希函数用上面(1),即 H (key) =key % 7if (hi= maxint) /maxint 解释成空地址printf ("无关键字dn"，k)； return (0)； )if (hi=k) hi=-maxint ； return (1)； 被删元素换成最大机器数的负数else /采用线性探测再散列解决冲突廿i；for (d=l； dWn-1； d+)11为表长，此处为1011为表长，此处为10i= (j+d) %n；if (hi= maxint) return (0); /maxint 解释成空地址if (hi=k) hi=-maxint ； return (1 )； /forprintf ("无关键字dn", k)； return (0)哈希表 a: ASLsucc=24/8=3；散列地址0123456789关键字1524101917381840比较次数11214555散列地址0123456789关键字1517241019403818比较次数13121244哈希表 b: ASLsucc=18/8(4) ASLunsucc =29/139.常用构造哈希函数的方法有：(1)数字分析法 该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选 数字分布均匀的位。(2)平方取中法 将关键字值的平方取中间几位作哈希地址。(3)除留余数法 H (key) =key%p,通常p取小于等于表长的最大素数。(4)折叠法 将关键字分成长度相等(最后一段可不等)的几部分，进行移位叠加或间界 叠加，其值作哈希地址。(5)基数转换法 两基数要互素，且后一基数要大于前一基数。在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理 地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除 就中断了查找路径。因为查找时碰到空地址就认为是查找失败。散列地址0123456789101112131415关键字140168275519208479231110比较次数12143113911310.散列地址01234567891011关键字231897925471638825139151比较次数11112123243ASLsucc =21/1111.散列地址012345678910关键字223346130167415330比较次数12124511312.设用线性探测再散列解决冲突，根据公式Snl (1 + 1/ (1-a ) /2 。可求出负载因子 为a=0.67。再根据数据个数和装载因子，可求出表长m= 15/0.67,取m=23。设哈希函数H (key)=(关键字首尾字母在字母表中序号之和)MOD 23。从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2。满足要求。13. (1)哈希函数H (key)=(关键字各字符编码之和)MOD 7 (2)散列地址0123456789关键字becdaaabacadbdbeaece比较次数1211111339a =0.7,所以表长取m=7/0.7=10ASLsucc=18/7散列地址0123456789关键字SATWEDSUNMONTUETHUFRI比较次数6111234ASLUnsucc=32/1014.15. (1)(2) ASLsuss=H/8散列地址0123456789101112关键字27532311920818比较次数31111112散列地址012345关键字0329200比较次数1121散列地址012345关键字0329200比较次数1121678910111232455810010126400123113316. (1)关键字29和45各发生一次碰撞，关键字58,126和400各发生两次碰撞，其余关键字无 碰撞。(2)发生碰撞次数：100, 126一次；200, 400两次；0七次。其余关键字无碰撞。散列地址0123456789101112关键字581010032003240004512629比较次数1121313812117 .在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得 出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关 键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从 最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。18 . m阶的B+树和B-树主要区别有三：（1）有n棵子树的结点中含有n （B-树中n-l）个关 键字；（2） B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点 本身依关键字大小自小到大顺序链接；（3） B+树的非终端结点可以看成是索引部分，结点中 只含其子树（根结点）中最大（或最小）关键字。B+树的查找既可以顺序查找，也可以随机 查找，B-只能顺序查找。19 .本题等价于“含有n个关键字的m阶B-树的最大高度是多少”？ 一次检索中最多走一 条从根到叶子的路径，由于根结点至少有两棵子树，其余每个（除叶子）结点至少有m/2 棵子树，则第三层至少有m/2*2个结点，第1+1层至少有2*m/2W个结点。设B-树深度 为1+1,即第1+1层是叶子结点，叶子结点数是n+1 （下面推导），故有n+l>2*m/21口即lW10gm/2（）+1。附：推导B-树中叶子结点数s与关键字数n的关系式：s=n+l设B-树某结点的子树数为Ci，则该结点的关键字数NfG-1。对于有k个结点的B-树, 有ENFS（Ci-l）=ECi-k （IWiWk） （1）因为B树上的关键字数，即XN尸n（liWk） （2）而B-树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为S；则ECi=(k-l)+s (iWiWk) (3) 综合(1) (2) (3)式，有s=n+l。证毕。20 .满二叉检索树可以看作是三阶B-树(23树)。B-树的插入和删除算法不适合满二叉检 索树。满二叉检索树插入和删除结点后均破坏了 “多路平衡查找树”“叶子在同一层上”(查 找失败结点)的定义。21 . B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。22 .含9个叶子结点的3阶B-树至少有4个非叶子结点，当每个非叶子结点均含3棵子树， 第三层是叶子结点时就是这种情况。当4层3阶B-树有10个叶子结点时，非叶子结点达到 最大值8个，其中第一层一个，第二层两个，第三层五个非叶子结点。23 .ASLSucc=32/10. (2) 10,12/5,20,24,28,30,35,46,50,55,68(3) ASLsUcc=41/12.序列(2)不可能是二叉排序树中查到363的序列。查到501后，因363<501,后面应 出现小于501的数，但序列中出现了 623,故不可能。25 .树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始 查找，根结点的平衡系数为零，说明根的左右子树等高(不一定是满二叉树)。沿左(或右) 子树向下查找时，查找路径上所有结点的平衡系数皆为零，说明任一结点的左右子树等高, 查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。26 .按索引顺序查找分块组织数据。N个区间分块有序，区间(块)内无序，将块内最大关 键字置于块内最后一个位置，即向量下标为汰-1,其中仁1, 2,，N-l, k为每区间的长度 (最后一个区间的最大关键字置于向量最后一个位置)。查找时，若N较小，可用顺序查找， 依次将x与市k-l*key进行比较，找到合适块后在块内顺序查找；若N很大，也可用折半 查找，以确定x所在块，在块内顺序查找。27 . 37/12.线性表应顺序存储且数据有序。28 .监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。29 .表长为n,每块大小取则2时，平均查找长度取最小值则2+屋若n=255,则每块长度为 16o.表长2000,分成45块，每块的理想长度为45 (最后一块长20)。若每块长25,则平均 查找长度为ASL=(80+l)/2+(25+l)/2=53.5(顺序查找确定块)，或ASL=19(折半查找确定块)。30 .将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元 素比较，比较中的小者放前半部，大者放后半部，用了n/21次比较。再在前后两部 分中分别简单选择最小和最大元素，各用n/21-l次比较。总共用了 3*n/2-2次比较。31 .在有序表中，比较到A4时,已查找元素依次是A7, A3, A5o.(1) 顺序查找判定树(2) ASL顺序成功=(Ipi +2P2+3p3+4p4+5p5)=0.97ASL折半成功=(lp3+2 (pi+p4)+3 (p2+p5)=l.04ASL 折半失败=(2qo+3qi+3q2+2q3+3q4+3q5)=L3OASL 顺序失败=(lq()+2qi+3q2+4q3+5q4+5q5)=l.07(3)本题中顺序检索好。36.时间复杂度是判断检索方法的一个重要指标，但不是唯一指标。使用什么检索方法要综 合考虑。哈希检索时间0 (1),查找速度最快，但需构建哈希函数，进行计算哈希地址，查 找时要有解决冲突的方法；二分检索时间O (logzn),需要元素有序且顺序存储，排序操作 的时间开销大；顺时检索时间最差为O (n),但对检索表无要求，数据有序无序均可，在数 据量较小时使用方便。五.算法设计题.根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱 结点值比较，即可得出结论，为此设全局指针变量pre (初值为null)和全局变量flag, 初值为true。若非二叉排序树，则置flag为false。#define true 1#define false 0typedef struct nodedatatype data; struct node *llink,*rlink; *BTree;void JudgeBST (BTree t,int flag)判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 if (t!=null && flag) Judgebst (t->llink,flag)； / 中序遍历左子树if (pre=null) pre=t； /中序遍历的第一个结点不必判断else if (pre->data<t->data) pre=t； 前驱指针指向当前结点 elseflag=flase； 不是完全二叉树Judgebst (t->rlink,flag)； / 中序遍历右子树/JudgeBST算法结束本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左 子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小 值。算法如下：int JudgeBST (BTree t)判断二叉树t是否是二叉排序树，若是，返回true,否则，返回falseif (t=null) return true；if (Judgebst (t->llink) && Judgebst (t->rlink) 若左右子树均为二叉排序树m=max (t->llink)； n=min (t->rlink)； 左子树中最大值和右子树中最小值 return (t->data>m && t->data<n) ； else return false； 不是二叉排序树 结束 judgebstint max (BTree p) 求二叉树左子树的最大值if (p=null) return -maxint； 返回机器最小整数elsewhile (p->rlink! =null) p=p->rlink；return p->data； int min (BTree p) 求二叉树右子树的最小值if (p=null) return maxint； 返回机器最大整数 else(while (p->llink! =null) p=p->llink；return p->data； )1 .题目分析借助于分块查找思想，在建立数据顺序表的同时丁建立一索引表。数据表中按 k个集合分块(元素个数不一定相等)，索引表中有两个域，一是各集合最后一个元素在数 据表中的位置(一维数组中的下标)，二是集合的个数(k)o实现数据运算时，根据给定的 二元组(i, X),首先在索引表中找到集合i的位置，然后在数据表中查找X。如查到X ,则 查找成功，返回X在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移， 插入X,同时修改索引表。typedef struct datatype data； rectype；typedef structint a； /a数组容量够大，存储各集合最后一个数据在数据表中的下标 int k；集合个数 index；int SetSearch_Insert (rectype R, index id, datatype x, int i)数据表R,查找第i个集合的元素x,若查找成功，返回其位置，否则将其插入第i个 集合if (i<l | i>id.k) printf ("无第(1 个集合n”, i)； exit (0)； if (i=l) first=0； else first=id.ai-l+l； /first 指向第 i 个集合在数据表的首址 last= id.ai； /last是第i个集合在数据表中的末址for (j=first； jWlast； j+) if (Rj=x) return (j)； 查找成功for (j=id.aid.k； j>id.ai； j-)/查找失败,将 x 插入数据表Rj+l=Rj； 元素后移Rj+l=x； 将x插入到原第i个集合最后一个元素之后。for (j=i； j<k； j+) id.aj+； 修改索引表中各集合最后一个元素的下标结束 SetSearch_Insert由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元 素值是各集合最后一个元素在数据表中的下标。按本算法插入(2,11.2)和(1,5.3),数据表前后状态如下:插入 刖0123456789101112131410.21.74.816.21.78.40.54.84.23.62.75.13.9插入 后10.21.74.816.25.31.78.40.511.24.84.23.62.75.13.9插入前，索引表中a数组的内容是3, 6, 12,插入后修改为4, 8, 14。3. void Delete (BSTreet, 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)； elsep->data=q->data； s->rchild=q->lchild； free (q)； )/Delete4 .题目分析上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中 最小值(中序遍历第一个)结点代替被删结点。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右子树中序序列最左结点if (s=p->rchild) p右子树的根结点无左子女p->data=s->data； p->rchild=s->rchild； free (s)； elsep->data=q->data； s->lchild=q->rchild； free (q)； /Delete.题目分析在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左 子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树 中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。void Delete(BSTree bst, keytype X)在二叉排序树bst上，删除其关键字为X的结点。BSTree f,p=bst;while (p && p->key!=X) 查找值为X的结点if (p->key>X) 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);算法结束. int Search (rectype r , int n, keytype k)在n个关键字从小到大排列的顺序表中，查找关键字为k的结点。rn+l.key=MAXINT； 在高端设置监视哨i=l;while (ri.kcy<k) i+；if (rn+ l.key=k) return (i% (n+l )；else return (0) 算法search结束查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有序，但进行 顺序查找，查找成功的平均查找长度亦为(n+l) /2。5 .请参见上面题3(1)。6 . int BinSrch (rectype r , int k, low, high)/在长为n的有序表中查找关键字k,若查找成功，返回k所在位置，查找失败返回0。if (lowWhigh) /low和high分别是有序表的下界和上界mid=(low+high) /2；if (rmid.key=k) return(mid)；else if (rmid.key>k) return (BinSrch (r,k, mid+1, high);else return (BinSrch (r,k, low, mid-1);)else return (0)； 查找失败。算法结束算法时间复杂度为O (logn)。n,则顺序查找的平均比较次数为(3)；折半查找的平均比较次数为(4)o(1) (2)： A.必须以顺序方式存储；B.必须以链式方式存储；C.既可以以顺序方式存 储，也可以链式方式存储；D.必须以顺序方式存储，且数据已按递增或递减顺序排好；E.必须以链式方式存储，且数据已按递增或递减的次序排好。(3) (4)： A.n B,n/2 Cn*n D.n*n/2E.log2nEnlog2n G.(n+l)/2H.log2(n+1)14 .在等概率情况下,线性表的顺序查找的平均查找长度人51为(1)，有序表的折半查找 的人5匕为(2)，对静态树表，在最坏情况下,人51为(3)，而当它是一棵平衡树时,ASL 为(4)，在平衡树上删除一个结点后可以通过旋转使其平衡，在最坏情况下需(5) 次旋转。供选择的答案：(1) (2) (3) (4) (5): A. 0( 1)B. 0( log2n)C. O(log2n)2) D.O(nlog2n) E.0(n).对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失 败，它们的平均查找长度是()，对于查找成功，他们