第9章自测卷答案

第8章查找自测卷答案

一、填空题（每空1分，共10分）

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。

2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8 次。设有100个结点，用二分法查找时，最大比较次数是7。

4折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。

二、单项选择题（每小题1分，共27分）

（B）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;

（ｎ＋１）－１

Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ

２

（A）2．【计研题2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。

A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50

（C）3．【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。

A．3 B．4 C．5 D． 6

7. （96初程P73）从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。

数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。

供选择的答案：

A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表④非顺序存储线性表

B：①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针

③只需移动结点，不需改变结点指针④既需移动结点，又需改变结点指针

C：①顺序查找②循环查找③条件查找④二分法查找

D：①顺序查找②随机查找③二分法查找④分块查找

E：①效率较低的线性查找②效率较低的非线性查找

③效率较高的非线性查找④效率较高的线性查找

答案：A＝④B＝②C＝④D＝①E＝③

三、简答题（每小题4分，共16分）

1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？

答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。

二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。

2.【计研题1999】假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树；

（2）若查找元素54，需依次与哪些元素比较？

（3）若查找元素90，需依次与哪些元素比较？

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

解：

（1）先画出判定树如下（注：mid=?(1+12)/2?=6）：

30

5 63

3 7 42 87

4 24 54 72 95

(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；

(3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；

（4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次，

所以ASL＝1/12（17＋20）＝37/12≈3.08

四、分析题（每小题6分，共24分）

2. 【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。

答：

12

717

2 11 16 21

4 9 13

验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21