南京工业大学数据结构作业答案作业6.docx

第六次作业1•假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:画出描述折半查找过程的判定树;若查找元素54,需依次与哪些元素比较?若查找元素90,需依次与哪些元素比较?假定每个元素的查找概率相等,求查找成功时的平均查找长度。设哈希(Hash)表的地址范围为0〜17,哈希函数为:H(K)=KMOD16。K为关键字,用线性探测法再散列法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49)造出Hash表,试回答下列问题:画出哈希表的示意图;若查找关键字63,需要依次与哪些关键字进行比较?若查找关键字60,需要依次与哪些关键字比较?假定每个关键字的查找概率相等,求查找成功时的平均查找长度。在一棵空的二叉查找树中依次插入关键字序列为 12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉查找树。设此二叉树以二叉链表作存储结构。试写一个判别给定二叉树是否为二叉排序树的算法,且树中结点的关键字均不同。假定对有序表:(3, 4,5, 7, 24,30, 42, 54, 63,72, 87, 95)进行折半查找,试回答下列问题:画出描述折半查找过程的判定树;若查找元素54,需依次与哪些元素比较?若查找元素90,需依次与哪些元素比较?假定每个元素的查找概率相等,求查找成功时的平均查找长度。解:(1) 先画出判定树如下(注:mid=(1+12)/2=6):⑵查找元素54,需依次与30,63,42,54等元素比较;⑶查找元素90,需依次与30,63,87,95,72等元素比较;(4)求ASL之前,需要统计每个元素的查找次数。判定树的前 3层共查找1+2X2+4X3=17次;但最后一层未满,不能用 8X4,只能用5X4=20次,所以ASL=1/12(17+20)=37/12~(Hash)表的地址范围为0〜17,哈希函数为:H(K)=KMOD 16。K为关键字,用线性探测法再散列法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49)造出Hash表,试回答下列问题:(5) 画出哈希表的示意图;(6) 若查找关键字63,需要依次与哪些关键字进行比较?(7) 若查找关键字60,需要依次与哪些关键字比较?(8) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。解:(1)画表如下:161732176349244(2)查找63,首先要与H(63)=63%16=15号单元内容比较,即 63vs31,no;然后顺移,与46,47,32,17,63 相比,一共比较了6次!(3)查找60,首先要与H(60)=60%16=12号单元内容比较,但因为 12号单元为空(应当有空标记),所以应当只比较这一次即可。(4) 对于黑色数据元素,各比较1次;共6次;对红色元素则各不相同,要统计移位的位数。 “63”需要6次,“49”需要3次,“40”需要2次,“46”需要3次,“47”需要3次,所以ASL=1/11(6+2+3X3)=17/11=〜 12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉查找树。答:12\7\/ /17\2 丿