一、填空题
1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 9 次。设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式
来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：
全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！
4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。(而任一元素查找次数 ≤n-1)
二、单项选择题
（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为
Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;
Ｃ. ＡＳＬ＝
＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（ A ）2. 折半查找有序表（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
（ B ）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。
A．3 B．4 C．5 D． 6
（ A ）4. 链表适用于 查找
A．顺序 B．二分法 C．顺序，也能二分法 D．随机
（ C ）5. 折半搜索与二叉搜索树的时间性能
A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（log2n）
文章来源地址https://www.toymoban.com/news/detail-487785.html
三、分析求解题
1.对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？
答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。
2. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
- 画出描述折半查找过程的判定树；
- 若查找元素54，需依次与哪些元素比较？
- 若查找元素90，需依次与哪些元素比较？
- 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
解：
- 先画出判定树如下（注：mid=ë(1+12)/2û=6）：
(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；
(3) 查找元素90，需依次与30, 63,87, 95等元素比较；
（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08
3. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
（10，24，32，17，31，30，46，47，40，63，49）
造出Hash表，试回答下列问题：
- 画出哈希表的示意图；
- 若查找关键字63，需要依次与哪些关键字进行比较？
- 若查找关键字60，需要依次与哪些关键字比较？
- 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
解： （1）画表如下：
| 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(63)=63%16=15号单元内容比较，即63 vs 31 ,no;
然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=（1*6+2*1+3*3+6*1）/11＝23/11
4. 已知如下所示长度为12的表：
（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
- 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
解：
文章来源：https://www.toymoban.com/news/detail-487785.html
到了这里，关于数据结构习题9---查找的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
