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

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

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.112.213.113.213.313.414.114.214.314.414.515.1C C C D G H E B E B B B 15.216.A 17.C 18.C 19.C 20.D 21.B 22.C 23.B 24.C 25.125.2A 26.A 27.D 28.C 29.129.230.B 31.D 32.D 33.C B F 25.334.D 35.1I 36.C A C D

2、35.2C 二判定题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从平稳因子定义看, 完全二叉树任一

3、结点的平稳因子的肯定值的确是小于等于 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 101 哈希函数 2 解决冲突的方法 3 挑选好的哈希函

4、数 4 处理冲突的方法 5 匀称 6简洁11 AVL树（高度平稳树,高度平稳的二叉排序树）,或为空二叉树,或二叉树中任意结点名师归纳总结 左子树高度与右子树高度差的肯定值小于等于1； 1316 14 第 1 页,共 34 页12小于等于表长的最大素数或不包含小于20 的质因子的合数2n+1 - - - - - - -精选学习资料 - - - - - - - - - 学习必备欢迎下载30, 31.5 （块内次序查15 145 245 346 （块内次序查找） 16kk+1/2 17找）18 1 次序储备或链式储备 2次序储备且有序 3 块内次序储备,块间有序 4 散列储备19 n+1/2 20n

5、+1/n*log2n+1-1 21结点的左子树的高度减去结点的右子树的高度 22 1 次序表 2 树表 3 哈希表 4 开放定址方法 5 链地址方法 6 再哈希 7 建立公共溢 出区23直接定址法 24 logm/2 +1 25ON 26nn+1/2 27 54 2831 2937/12 30主关键字 31左子树右子树32插入删除 33 14 341126 264 333 465 35（ 1）low=high 2 low+hig DIV 2 3 binsrch:=mid 4binsrch:=0 36 1 k 2 Irear 38 1p.=null 2pf=p 3p.=*t 4*t=null 四

6、应用题 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） 称为二次探测再散列

7、,它削减了集合,但不简洁探测到全部表空间,只有当表长为形如4j+3 （j 为整数）的素数时才有可能；cdi = 伪随机数序列,称为随机探测再散列；再散列法 Hi=RHi（key ） i=1 , 2, , k,是不同的散列函数,即在同义词产生碰撞时,用另一散列函数运算散列地址,直到解决碰撞；该方法不易产生“ 集合” ,但增加了运算时间； 链地址法 将关键字为同义词的记录储备在同一链表中,散列表地址区间用H0.m-1 表示, 重量初始值为空指针；凡散列地址为 i （0 i m-1）的记录均插在以 Hi为头指针的链表中；这种解决方法中数据元素个数不受表长限制,插入和删除操作便利,但增加了指针的空间开

8、销；这种散列表常称为开散列表,而中的散列表称闭散列表,含义是元素个数受表长限制；建立公共溢出区设 H0.m-1为基本表,凡关键字为同义词的记录,都填入溢出区O0.m-1；（3）用分别的同义词表和结合的同义词表解决碰撞均属于链地址法；链地址向量空间中的每个元素不是简洁的地址,而是关键字和指针两个域,散列地址为i （0i m-1）的第一名师归纳总结 - - - - - - -第 2 页,共 34 页精选学习资料 - - - - - - - - - 个关键字储备在地址空间向量第学习必备欢迎下载指向i 个重量的“ 关键字” 域；前者的指针域是动态指针,同义词的链表, 具有上面的优缺点；后者实际是静态链

9、表,同义词存在同一地址向量空间（从最终向前找闲暇单元）,以指针相连；节约了空间,但易产生“ 积累” ,查找效率低；（4）要在被删除结点的散列地址处作标记,不能物理的删除；否就,中断了查找通路；（5）记录 负载因子3评判哈希函数优劣的因素有：能否将关键字匀称影射到哈希空间上,有无好的解决冲突的方法,运算哈希函数是否简洁高效；由于哈希函数是压缩映像,的方法见上面 2 题；冲突难以防止； 解决冲突4哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比）,它反映了哈希表的装满程度,该值一般取 0.650.9 ；解决冲突方法见上面 2 题；5不肯定相邻；哈希地址为 i （0i m-1）的关

10、键字,和为解决冲突形成的探测序列 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+2 2）%10=0（冲突） H 3=（6+3 3）%10=5 所以比较了 4 次；7由于装填因子为 0.8 ,关键字有 8 个,所以表长为 8/0.8=10 ；（1）用除留余数法,哈希函数为 H（key）

11、=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；/ 哈希函数用上面（

12、1）,即 H（key） =key % 7 if （hi= maxint）/maxint 说明成空地址printf（“ 无关键字 %dn” , k）； return （0）； if （hi=k）hi=-max int ；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（

13、“ 无关键字 %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 ；3 4 5 6 7 8 9 散列地址0 1 2 关键字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

14、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）折叠法 将关键字分成长度相等（最终一段可不等）的几部

15、分,进行移位叠加或间界叠加,其值作哈希地址；（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

16、7 8 9 10 第 4 页,共 34 页- - - - - - -精选学习资料 - - - - - - - - - 关键字4 学习必备欢迎下载13 24 32 21 12 49 38 比较次数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 ASL unsucc=19/11 14 题（ 2） ASLsucc=13/8 ASL unsucc=19/11 值得指出, 对用拉链法求查找失败时的平均查找长度有两种观

17、点；其一, 认为比较到空指针算失败；以此题为例,哈希地址0、2、5、7、9 和 10 均为比较 1 次失败,而哈希地址1 和 3 比较 2 次失败,其余哈希地址均为比较 3 次失败,因此,查找失败时的平均查找长度为 19/11 ,我们持这种观点； 仍有另一种懂得, 他们认为只有和关键字比较才运算比较次数,而和空指针比较不运算；照这种观点,此题的ASLunsucc=（1+1+2+2+2）/11=8/11 14由 hashfx=x mod 11 可知,散列地址空间是0 到 10,由于有 8 个数据,装载因子取0.7 ；（1）散列地址0 1 2 3 4 5 6 7 8 9 10 关键字33 1 13

18、 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

19、1 2 3 4 5 6 7 8 9 10 11 第 6 页,共 34 页关键字231 89 79 25 47 16 38 82 51 39 151 - - - - - - -精选学习资料 - - - - - - - - - 比较次数1 1 1 1 学习必备2 欢迎下载2 4 3 2 1 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 地址关 键3

20、2 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）=（关键字首尾字母在字母表中序号

21、之和）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

22、（ 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 第 7 页,共 34 页关键字0 3 29 200 32 45 58 100 10 126 400 - - - - - - -精选学习资料 - - - - - - - - - 比较次数1 1 2 1 学习必备2 欢迎下载1 1 3 3 1 3 关键字 29 和 45 各发生 一次碰撞,关键字 碰撞；（2）58

23、,126 和 400 各发生 两次碰撞,其余关键字无散列地址 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）

24、ASLunsucc=24/13 29在 B-树中查找关键字从根结点开头,从根往下查找结点,然后在结点内查找关键字,得出查找胜利与否的结论；B+树的非终端结点是索引部分,其查找从根开头, 从根往下查到关键字后, 要连续查到最下层结点,得到查找胜利与否的结论；另外,B+树仍可以在最下层从最小关键字开头,从左往右进行次序查找,B-树就不能作次序查找；30 m阶的 B+树和 B-树主要区分有三：（1）有 n 棵子树的结点中含有n（B-树中 n-1 ）个关键字；（ 2）B+树叶子结点包含了全部关键字信息,及指向含关键字记录的指针,且叶子结点本身依关键字大小自小到大次序链接；（3）B+树的非终端结点可以看

25、成是索引部分,结点中只含其子树（根结点）中最大（或最小）关键字；B+树的查找既可以次序查找,也可以随机查找, B-只能次序查找；31此题等价于“ 含有 n 个关键字的 m阶 B-树的最大高度是多少” ？一次检索中最多走一条从根到叶子的路径,由于根结点至少有两棵子树,其余每个（除叶子）结点至少有 m/2棵子树,就第三层至少有 m/2 *2 个结点,第 l+1 层至少有 2* m/2 l-1 个结点；设 B-树深度为 l+1 ,即第 l+1 层是叶子结点,叶子结点数是 n+1（下面推导）,故有 n+12* m/2 l-1 ,即 l log m/2 （）+1；附：推导 B- 树中叶子结点数 s 与关

26、键字数 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

27、.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 页,共

28、 34 页精选学习资料 - - - - - - - - - 36第一层有 1 个结点,其次层至少有学习必备欢迎下载22 个结点,第三层有 2* m/2 个结点,第四层有 2* m/2 h-2 个结点（ h 2）；结点总数是个结点, ,第h 层至少有2* m/21+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）4

29、1满二叉检索树可以看作是三阶B-树（ 23 树）； B- 树的插入和删除算法不适合满二叉检索树；满二叉检索树插入和删除结点后均破坏了“ 多路平稳查找树” “ 叶子在同一层上”（查找失败结点）的定义；4243 B+树的查找可从根结点开头随机查找,也可以从最小关键字起次序查找；44含 9 个叶子结点的3 阶 B-树至少有 4 个非叶子结点, 当每个非叶子结点均含3 棵子树,第三层是叶子结点时就是这种情形；当4 层 3 阶 B-树有 10 个叶子结点时,非叶子结点达到最大值 8 个,其中第一层一个,其次层两个,第三层五个非叶子结点；45在二叉排序树上查找关键字K,走了一条从根结点至多到叶子的路径,时

30、间复杂度是Ologn ,而在中序遍历输出的序列中查找关键字 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名

31、师归纳总结 - - - - - - -第 12 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载5152序列（ 2）不行能是二叉排序树中查到363 的序列；查到501 后,因 363501,后面应显现小于 501 的数,但序列中显现了 623,故不行能；53（ 1）此题的本质是给定中序序列1、2、3、4,有几种不同的二叉排序树,也即该中序序列相当多少不同的前序序列,这是树的计数问题；设中序序列中元素数为 n,就二叉数的数目为 1/ （n+1）C2n n,这里 n=4,故有 14 种；图示如下：（2）最优查找树有4 种,上面中 名师归纳总结 - - - - -

32、 - -第 13 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载（3）AVL树有,也是（ 2）中的那 4 种（4）完全二叉树有 1 种,上图中54设以 Nm表示深度为 m的 AVL树中含有的最少结点数；明显,N0=0,N1 =1,N2 =2,且 Nm= Nm-1 + Nm-2 +1 （m 2）；这个关系与斐波那契序列类似,用归纳法可以证明：当 m0 时,Nm = F m+2 -1 ,而 Fm约等于 m/（其中 =（1+）/2 ）,就 Nm约等于 m+2/-1 （即深度为 m的 AVL树具有的最少结点数）当 m层的 AVL树是满二叉树时,结点数为最大值2m-

33、1 ；55树的高度肯定增加；由于“ 查找路径上的任一结点的平稳系数皆为零” ,从根结点开头查找,根结点的平稳系数为零,说明根的左右子树等高（不肯定是满二叉树）；沿左（或右）子树向下查找时,查找路径上全部结点的平稳系数皆为零,说明任一结点的左右子树等高,查找失败是在叶子结点,插入也是在叶子结点,树的高度自然增加；56四种破坏平稳的情形,a,b,c是结点指针, 虚线部分是在失去平稳前的图中未画出部分,该部分如存在,就在调整后应按虚线指出的连接；其它,如LL 型, a 指针所指结点可能有右子树, c 指针所指结点可能有左右子树,这些在调整后均不受影响,故没画出；5758 LR型旋转名师归纳总结 -

34、- - - - - -第 14 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载59（1）ASLsuss = （1*1+2*2+3*3+4*3+5*2+6*1）/12=42/12 （2）ASLsuss = （1*1+2*2+4*3+5*4 ）/12=37/12 （3）ASLsuss = （1*1+2*2+4*3+4*4+5*1）/12=38/12 60名师归纳总结 - - - - - - -第 15 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载61说明：在 （3）后,先删除结点CAN并未破坏平稳, 在删 AQU后破坏了

35、平稳, 根结点 CAP的平稳因子为 -2 ；需作何种调整,要看 CAP右子树 PIS 的平稳因子,如该平稳因子是 1,就作 RL型调整；如为 -1 ,就作 RR型调整；如为 0,就 RR和 RL均可,为简洁计,选 RR型；当然,在 PIS 平稳因子为零后,仍可连续往下分析；6263（ 1）名师归纳总结 - - - - - - -第 16 页,共 34 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载（ 2）最坏情形下, 对该树的插入、 删除和依次输出的时间复杂性分别是 Oh ,Onlog 2h和 On ；64按索引次序查找分块组织数据；N个区间分块有序,区间（块）内无序,

36、将块内最大关键字置于块内最终一个位置,即向量下标为 ik-1 ,其中 i=1 ,2, , N-1,k 为每区间的长度（最终一个区间的最大关键字置于向量最终一个位置）；查找时,如 N较小,可用次序查找,依次将 x 与 rik-1*key 进行比较,找到合适块后在块内次序查找；如 N很大, 也可用折半查找,以确定 x 所在块,在块内次序查找；65 37/12 66线性表应次序储备且数据有序；67监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕,提高了查找效率；68表长为 n,每块大小取 n 1/2 时,平均查找长度取最小值 n 1/2 +1；如 n=255,就每块长度为16；69表长 2

37、000,分成 45 块,每块的抱负长度为 45（最终一块长 20）；如每块长 25,就平均查找长度为 ASL=80+1/2+25+1/2=53.5（次序查找确定块）,或 ASL=19（折半查找确定块）；70将 n 个元素对称比较,即第一个元素与最终一个元素比较,其次个元素与倒数其次个元素比较, ,比较中的小者放前半部,大者放后半部,用了n/2 次比较；再在前后两部分中分别简洁挑选最小和最大元素,各用 n/2-1 次比较；总共用了 3* n/2 -2 次比较；71在有序表 A1.14 中,比较到 A4 时,已查找元素依次是 A7 , A3 ,A5 ；72（ 1）图中结点中的数字为元素在有序表中的下标（2）插入排序中,用折半查找确定待插入元素位置,比直接插入排序削减了比较次数,但数据移动次数没有转变,排序的时间复杂度也未转变；（3）折半查找的平均查找长度是n+1/nlog2n+1-1 logn+1-1；本例 ASL=79/21；