查找和排序练习.docx

查找和排序的部分练习1、 对表：（3，4，5，7，24，30，42，54，63，72，87，95），试回答下列问题A进行折半查找（1） 画出描述折半查找过程的判定树；（2） 若查找元素54，需依次与哪些元素比较？（3） 若查找元素90，需依次与哪些元素比较？（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度ASL；（5） 求查找不成功的平均查找长度ASL；B按照关键字顺序构造一个二叉树排序树？并求等概率情况下查找成功的平均查找长度ASL？不成功的平均查找长度ASL？C按照关键字顺序构造一个平衡二叉树，写出每一步失衡后的调整类型和以及调整结果？求等概率查找下查找成功的平均查找长度ASL？不成功的平均查找长度ASL？2、给定一组关键字序列36，75，83，54，12，67，60，40，92，72，11，10，完成以下各题A进行希尔排序，步长依次取5、3、1，写出每一趟排序的结果？B进行快速排序，写出一趟排序的完整过程？C构建小根堆？简述堆排序的思想？进行一趟堆排序结果？D按关键字顺序构造一个平衡二叉树AVL？并求等概率情况下查找成功的平均查找长度ASL？不成功的ASL？E按关键字顺序构造二叉排序树？并求等概率情况下查找成功的平均查找长度ASL？不成功的ASL？F. 按照排序之后的结果进行折半查找，画出查找判定树？并求等概率情况下查找成功的平均查找长度ASL？不成功的ASL？3、给定关键字序列36，75，83，54，12，67，60，40，92，72，11，10，完成以下各题：A. 采用哈希函数：H(key)=key%11，采用链地址法处理冲突，设计出链表结构？并计算查找成功时的平均查找长度？不成功的ASL？B. 采用哈希函数：H(key)=key%11，采用线性探测法处理冲突，设计出哈希结构？并计算查找成功时的平均查找长度？不成功的ASL？C.采用哈希函数：H(key)=key%11，采用二次探测法处理冲突，设计出哈希结构？并计算查找成功时的平均查找长度？不成功的ASL？4、给定关键字序列Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，完成以下各题： A. 按关键字顺序构造二叉排序树？并求等概率情况下查找成功的平均查找长度ASL？不成功的ASL？JanFebAugJulyJuneMaySepMarAprDecASL=(1+2*2+3*3+4*3+5*2+6)/12= 42/12NovOctB.按关键字顺序构造一个平衡二叉树AVL？并求等概率情况下查找成功的平均查找长度ASL？不成功的ASL？JanFebAugJulyJuneMaySepMarAprOctJanAugFebJulyJuneMayMarAprJanAugFebJulyJuneMayMarAprSepMayJanAugFebJulyJuneOctMarAprSepMayJanAugFebJulyJuneOctMarAprNovDecSepMayJanAugFebJulyJuneOctMarAprNovSepMayJanAugFebJulyJuneOctMarAprNovASL=(1+2*2+3*4+4*4+5)/12=38/12C. 按照排序之后的结果进行折半查找，画出查找判定树？并求