数据结构作业：第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 。供选择的答案：AC：必须以顺序方式存储必须以链表方式存储必须以散列方式存储 既可以以顺序方式，也可以以链表方式存储 必须以顺序方式存储且数据元素己按值递增或递减的次序排好 必须以链表方式存储且数据元素己按值递增或递减的次序排好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.则得到的哈希表为：550123146811823619查找20,首先要与H(2O)=2O%11=9号单元内容比较，但因为9号单元为空(应当有空标记)， 所以应当只比较这一次即可。C.若查找关键字68,需要依次与哪些关键字进行比较？查找68,首先要与H(68)=68%11=2号单元内容比较，即68 vs 23 ,no;然后顺移，与14, 68相比，一共比较了 3次！(3) 若采用二次探测再散列处理冲突，a.则得到的哈希表为：550123143682681911查找11,首先要与H(ll)二11%11=0号单元内容比较，即11 vs 55 ,no;然后与01,11相比，一共比较了 3次！(3)若采用随机探测再散列处理冲突,H2(kcy)是另设定的一个哈希函数,设H2(kcy)=(3 key) MOD 10+1 ，则得到的哈希表为：23 |016814 11 82551936