作业9 9.1选择题(从下列各题四个备选答案中选出1个正确答案,将其代号 (A,B,C,D)写在题干前面的括号内。 ()1.顺序查找n个记录的顺序表,当使用监视哨时,若查找失败,比较 关键字的次数最多是 n B n+1 Cn-1 D n/2 ()1.折半查找表(8,12,16,18,20,34,55,80),若查找元素80,则需依次与 表中元素进行比较 A.16,34,80B.20,55,80C.18,20,55D.18,34,55,80 ()2.折半查找顺序表(8,12,16,20,30,34,45),若查找元素25,则需依次 与表中元素进行比较,查找结果是失败。 A.16,34,30B.20,30C.20,34,30D.16,20 )3对22个记录的有序表作折半查找,当查找失败时,至少需要比较 次关键字。 A.3B.4C. D.6 4.对有40个记录的分块表进行分块查找,最理想的块长为_。 20B.10C.7D.8 9.2设对22个记录的有序表折半查找,试画出对应的判定树;假定每个记 录的查找概率相同,求查找成功时的ASL。 9.3依次输入元素:13,06,04,12,20,05,02,26,试生成二叉排序树:(1)画出 二叉排序树;(2)进行中序遍历,写出遍历结果;(3)假定每个结点(元素)的查 找概率相等,求查找成功时的ASL。 94设哈希(Hash)函数为:H(k)=k%14,其中k为关键字,%为取模运算,用线 性探测再散列法处理冲突,在地址范围为0~15的散列区中,用关键字序列 (19,27,26,28,29,40,64,21,15,12,42,41)造一个哈希表:(1)试画出该哈希表 存储结构图;(2)若查找关键字40,试问需依次与哪些关键字比较大小?(3)假定 每个关键字的查找概率相同,试求查找成功时的ASL
作 业 9 9.1 选择题(从下列各题四个备选答案中选出 1 个正确答案, 将其代号 (A,B,C,D)写在题干前面的括号内。 ( )1.顺序查找 n 个记录的顺序表, 当使用监视哨时, 若查找失败, 比较 关键字的次数最多是_____。 A.n B.n+1 C.n-1 D.n/2 ( )1.折半查找表(8,12,16,18,20,34,55,80),若查找元素 80,则需依次与 表中元素_____进行比较。 A.16,34,80 B.20,55,80 C.18,20,55 D.18,34,55,80 ( )2.折半查找顺序表(8,12,16,20,30,34,45),若查找元素 25,则需依次 与表中元素_____进行比较,查找结果是失败。 A.16,34,30 B.20,30 C.20,34,30 D.16,20 ( )3.对 22 个记录的有序表作折半查找, 当查找失败时, 至少需要比较 ____次关键字。 A.3 B.4 C.5 D.6 ( )4.对有 40 个记录的分块表进行分块查找, 最理想的块长为____。 A.20 B.10 C.7 D.8 9.2 设对 22 个记录的有序表折半查找，试画出对应的判定树；假定每个记 录的查找概率相同,求查找成功时的 ASL。 9.3 依次输入元素：13,06,04,12,20,05,02,26,试生成二叉排序树:(1)画出 二叉排序树；(2)进行中序遍历，写出遍历结果；(3)假定每个结点(元素)的查 找概率相等,求查找成功时的 ASL。 9.4 设哈希(Hash)函数为:H(k)=k%14,其中 k 为关键字,%为取模运算，用线 性探测再散列法处理冲突,在地址范围为 0～15 的散列区中,用关键字序列 (19,27,26,28,29,40,64,21,15,12,42,41)造一个哈希表:(1)试画出该哈希表 存储结构图；(2)若查找关键字 40,试问需依次与哪些关键字比较大小?(3)假定 每个关键字的查找概率相同, 试求查找成功时的 ASL