6．【91程P3】从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。
某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。 供选择的答案：
A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储
⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好
D，E： ① 25000 ② 30000 ③ 45000 ④ 90000
答案： A= ④ B= ⑤ C= ③ D＝ ③ E＝ ④ 7. （96初程P73）从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案：
A：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 性表
B： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针
③只需移动结点，不需改变结点指针 C：① 顺序查找 ②循环查找 D：① 顺序查找 ②随机查找 E：① 效率较低的线性查找
④既需移动结点，又需改变结点指针
④二分法查找
④非顺序存储线
③条件查找
③二分法查找 ④分块查找
②效率较低的非线性查找
③ 效率较高的非线性查找 ④效率较高的线性查找
答案：A＝ ④ B＝ ② C＝ ④ D＝ ① E＝ ③ 8. 【97程P18】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是 C 。 供选择的答案
A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大
④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历 C：① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的
③ 每个结点的左右子树的高度之差的绝对值不大于1 ④ 最下层的叶子必须在最左边 答案：A＝ ① B＝ ② C＝ ②
9. 【92程 P6】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。
散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。 供选择的答案
A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值 ⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同
③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法
答案：A＝ ④ B＝ ① C＝ ③ D＝ ④
10.【91程P4】考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。
现把9个数1，2，3，?，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把10放入此树并使该树保持前述性质，增加的一个结点可以放在 D 或 E 。 供选择的答案
A～C： ①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8
⑨ 9
D～E： ① n7下面 ② n8下面 ③ n9下面 ④ n6下面 ⑤ n1与n2之间 ⑥ n2与n4之间 ⑦ n6与n9之间 ⑧ n3与n6之间 答案：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
3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少? 答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。
4. 【计研题1999】设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；
（2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？
（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 32 17 63 49 24 40 10 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55 四、分析题（每小题6分，共24分）
1. 【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：判定树应当描述每次查找的位置：
5 2
8
1 3 6 9 4 7 10
2. 【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 答：
12
7
17
2 11 16 21
ASL＝1/10（1＋2×2＋3×4＋4×3） ＝1/10（1＋4＋12＋12） ＝29/10=2.9