数据结构作业：第9章作业题目.docx

第9章查找
一、填空题(每空1分，共10分)在数据的存放无规律而言的线性表中进行检索的最佳方法是。
1. 【计研题2000］折半查找有序表(4, 6, 12, 20, 28, 38, 50, 70, 88, 100),若查找表中元素20,
它将依次与表中元素比较大小。
2. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是o当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即kl尹k2 ,但H(kl)=H (k2),这种现象称为.
3. 散列(哈希)法存储的基本思想是由决定数据的存储地址。
4. 顺序查找法中设置监视哨，可以起到的作用。
5. 假设查找每个数据元素的概率相等，即Pi=l/n,则顺序查找算法的平均查找长度为：_在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为。
6. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是设哈希表长 m=l4,哈希函数 H(key)=key MODI I.表中己有4个结点:addr( 15)=4, addr(38)=5, addr(61)=6, addr(84)=7,其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是—二、单项选择题(每小题1分，共27分)
()1.【计研题2()01】对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。
A. 3B. 4C. 5D. 6
()2.链表适用于查找A.顺序 B.二分法 C.顺序，也能二分法D.随机【91程P3】从供选择的答案中，选出应填入下面叙述二_内的最确切的解答，把相应编号写在答 卷的对应栏内。
要进行线性查找，则线性表要进行二分查找，则线性表B ；要进行散列查找，则线性表C 。 某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找 的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D_,最大比较次数为业_。
供选择的答案：
A〜C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储
④ 既可以以顺序方式，也可以以链表方式存储
⑤ 必须以顺序方式存储且数据元素己按值递增或递减的次序排好
⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好D, E： ① 25000② 30000③ 45000④ 90000答案：A= B= C= D= E=(96初程P73)从供选择的答案中，选出应填入下面叙述二_内的最确切的解答，把相应编号写 在答卷的对应栏内。
数据结构反映了数据元素之间的结构关系。链表是一种 X ,它对于数据元素的插入和删除 B o通常查找线性表数据元素的方法有和口_两种方法，其中是一种只适合于顺序 存储结构但工_的方法；而_y_是一种对顺序和链式存储结构均适用的方法。
供选择的答案：
A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表 B：①不需要移动结点，不需改变结点指针
③只需移动结点，不需改变结点指针
C：①顺序查找②循环查找
D：①顺序查找②随机查找
E：①效率较低的线性查找
③效率较高的非线性查找
答案：A= B=_
④非顺序存储线性表
②不需要移动结点，只需改变结点指针
④既需移动结点，又需改变结点指针
③条件查找④二分法查找
③二分法查找④分块查找
②效率较低的非线性查找
④效率较高的线性查找
C= D=
E=
三、简答题(每小题4分，共16分)【全国专升本题】对分(折半)查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比 线性查找的速度快，这种说法对吗？
1. 【计研题1999］假定对有序表：(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95)进行折半查找，试 回答下列问题：
(1) 画出描述折半查找过程的判定树；
(2) 若查找元素54,需依次与哪些元素比较？
(3) 若查找元素90,需依次与哪些元素比较？
4.关键字集合｛ 19, 01, 23, 14, 55, 68, 11, 82, 36 ｝，设定哈希函数 H(key) = key MOI) 11 (表长=11),
(1)若采用线性探测再散列处理冲突，则得到的哈希表为：
a. 若查找关键字20,需要依次与哪些关键字进行比较？
C.若查找关键字68,需要依次与哪些关键字进行比较?
(1) 若采用二次探测再散列处理冲突，则得到的哈希表为：
a. 若查找关键字11,需要依次与哪些关键字进行比较?
(3)若采用随机探测再散列处理冲突，H2(key)是另设定的一个哈希函数，设H2(key)=(3 key) MOD 10+1 ,则得到的哈希表为：