作 业 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。
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。
