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

1、第9章 查找 一、填空题（每空1分，共10分）1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。2【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。3. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。4. 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1k2 ，但 H（k1）=H（k2），这种现象称为冲突.5. 散列（哈希）法存储的基本思想是由 关键字的值 决定数据的存储地址。6. 顺序查找

2、法中设置监视哨，可以起到防止越界的作用。7. 假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为： ASL=(n+1)/2。8. 在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。9. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找10. 设哈希表长m=14, 哈希函数H(key)=key MOD11.表中已有4个结点；addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是9二、单项选

3、择题（每小题1分，共27分）（ C ）1【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。A3 B4 C5 D 6（ A ）2. 链表适用于 查找A顺序 B二分法 C顺序，也能二分法 D随机3【91程P3】从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平

4、均比较次数约为 D ，最大比较次数为 E 。供选择的答案：AC： 必须以顺序方式存储 必须以链表方式存储 必须以散列方式存储 既可以以顺序方式，也可以以链表方式存储 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E： 25000 30000 45000 90000答案： A= B= C= D E 4. （96初程P73）从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有

5、 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案：A：顺序存储线性表 非顺序存储非线性表顺序存储非线性表 非顺序存储线性表B： 不需要移动结点，不需改变结点指针 不需要移动结点，只需改变结点指针 只需移动结点，不需改变结点指针 既需移动结点，又需改变结点指针C： 顺序查找 循环查找 条件查找二分法查找D： 顺序查找 随机查找 二分法查找分块查找E： 效率较低的线性查找 效率较低的非线性查找 效率较高的非线性查找效率较高的线性查找答案：A B C D E 三、简答题（每小题4分，共16分）1.【全国专升本题

6、】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。2.【计研题1999】假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1） 画出描述折半查找过程的判定树；（2） 若查找元素54，需依次与哪些元素比较？（3） 若查

7、找元素90，需依次与哪些元素比较？解：（1） 先画出判定树如下（注：mid=ë(1+12)/2û=6）：305 633 7 42 87 4 24 54 72 95(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；(3) 查找元素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.

8、若查找关键字68，需要依次与哪些关键字进行比较？（2） 若采用二次探测再散列处理冲突，a.则得到的哈希表为：b. 若查找关键字11，需要依次与哪些关键字进行比较？（3）若采用随机探测再散列处理冲突，H2(key) 是另设定的一个哈希函数，设 H2(key)=(3 key) MOD 10+1，则得到的哈希表为：解答：（1）若采用线性探测再散列处理冲突,a.则得到的哈希表为：b.若查找关键字20，需要依次与哪些关键字进行比较？查找20,首先要与H(20)=20%11=9号单元内容比较，但因为9号单元为空（应当有空标记），所以应当只比较这一次即可。C.若查找关键字68，需要依次与哪些关键字进行比较？查找68,首先要与H(68)=68%11=2号单元内容比较，即68 vs 23 ,no;然后顺移，与14,68相比，一共比较了3次！（3） 若采用二次探测再散列处理冲突，a.则得到的哈希表为：b. 若查找关键字11，需要依次与哪些关键字进行比较？查找11