数据结构作业：第9章作业答案.docx

第9章查找
一、填空题(每空1分，共10分)在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找)。
1. 【计研题2000］折半查找有序表(4, 6, 12, 20, 28, 38, 50, 70, 88, 100),若查找表中元素20,
它将依次与表中元素28, 6, 12, 20比较大小。
2. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。
3. 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即klUk2 ,但H(kl) =H (k2),这种现象称为冲突.
4. 散列(哈希)法存储的基本思想是由 关键字的值决定数据的存储地址。
5. 顺序查找法中设置监视哨，可以起到防止越界的作用。
6. 假设查找每个数据元素的概率相等，即Pi=l/n,则顺序查找算法的平均查找长度为：_ASL=(n+l )/2。
7. 在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。
8. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找设哈希表长 m= 14,哈希函数 H(key)=key MOD11.表中己有 4 个结点;addr( 15)=4, addr(38)=5, addr(61)=6, addr(84)=7,其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是9二、单项选择题(每小题1分，共27分)
(C ) 1.【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。
A. 3B. 4C. 5D. 6
(A ) 2.链表适用于查找A,顺序 B.二分法 C.顺序，也能二分法 D.随机【91程P3】从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在答 卷的对应栏内。
要进行线性查找，则线性表A ；要进行二分查找，则线性表B ；要进行散列查找，则线性表C 。 某顺序存储的表格，其中有9()000个元素，己按关键项的值的上升顺序排列。现假定对各个元素进行查找 的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D_,最大比较次数为E 。
供选择的答案：
A〜C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储
④ 既可以以顺序方式，也可以以链表方式存储
⑤ 必须以顺序方式存储且数据元素己按值递增或递减的次序排好
⑥ 必须以链表方式存储且数据元素己按值递增或递减的次序排好D, E： ① 25000② 30000③ 45000④ 90000答案：A= ④ B= (5) C= ③ D= ③E= ®(96初程P73)从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写 在答卷的对应栏内。
,它对于数据元素的插入和删除
C_是一种只适合于顺序
数据结构反映了数据元素之间的结构关系。链表是一种B o通常查找线性表数据元素的方法有和两种方法，其中 存储结构但的方法；而_D_是一种对顺序和链式存储结构均适用的方法。 供选择的答案：
④非顺序存储线性表
②不需要移动结点，只需改变结点指针
④既需移动结点，又需改变结点指针
③条件查找④二分法查找
A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表 B：①不需要移动结点，不需改变结点指针
③只需移动结点，不需改变结点指针C：①顺序查找②循环查找③二分法查找④分块查找
②效率较低的非线性查找
④效率较高的线性查找
C= ④D=_①

③二分法查找④分块查找
②效率较低的非线性查找
④效率较高的线性查找
C= ④D=_①
D：①顺序查找②随机查找E：①效率较低的线性查找
③效率较高的非线性查找答案：A =④ B =②三、简答题(每小题4分，共16分)【全国专升本题】对分(折半)查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比 线性查找的速度快，这种说法对吗？
答：不适合！虽然有序的单链表的结点是按从小到大(或从大到小)顺序排列，但因其存储结构为单链表, 查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快; 而二分查找则慢得多。
1. 【计研题1999］假定对有序表：(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95)进行折半查找，试 回答下列问题：
(1) 画出描述折半查找过程的判定树；
(2) 若查找元素54,需依次与哪些元素比较？
(3) 若查找元素90,需依次与哪些元素比较？
解：
(1) 先画出判定树如下(注：mid=L(l+12)/2j=6):
查找元素54,需依次与30,63,42,54等元素比较；查找元素90,需依次与30,63,87,95等元素比较；4.关键字集合｛ 19, 01, 23, 14, 55, 68, 11, 82, 36 ｝，设定哈希函数 H(key) = key MOD 11 (表长
=11 ),
(1)若采用线性探测再散列处理冲突，a.则得到的哈希表为： b.若查找关键字20,需要依次与哪些关键字进行比较?
C.若查找关键字68,需要依次与哪些关键字进行比较?
(2) 若采用二次探测再散列处理冲突，则得到的哈希表为：
a. 若查找关键字11,需要依次与哪些关键字进行比较?
(3)若采用随机探测再散列处理冲突，H2(key)是另设定的一个哈希函数，设H2(key)=(3 key) MOD 10+1 ,则得到的哈希表为：
解答：(1)若采用线性探测再散列处理冲突，a.则得到的哈希表为：
55
01
23
14
68
11
82
36
19

查找20,首先要与H(2O)=2O%11=9号单元内容比较，但因为9号单元为空(应当有空标记)， 所以应当只比较这一次即可。
C.若查找关键字68,需要依次与哪些关键字进行比较？
查找68,首先要与H(68)=68%11=2号单元内容比较，即68 vs 23 ,no;
然后顺移，与14, 68相比，一共比较了 3次！
(3) 若采用二次探测再散列处理冲突，a.则得到的哈希表为：
55
01
23
14
36
82
68

19

11
查找11,首先要与H(ll)二11%11=0号单元内容比较，即11 vs 55 ,no;
然后与01,11相比，一共比较了 3次！
(3)若采用随机探测再散列处理冲突,H2(kcy)是另设定的一个哈希函数,设H2(kcy)=(3 key) MOD 10+1 ，则得到的哈希表为：
23 |01
68
14 11 82
55

19

36