资源描述：
《第四阶段测考试试题汇总--答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1、以关键字序列为例(256,301,751,129,256,937,856,076)生成二叉排序树，并说出查找076和900的比较次数。答：生成的二叉排序树如下图：查找076,需比较3次，分别与256、129和076比较，査找成功；查找900,需比较5次，分别与256、301>751>937.856比较，查找失败。2、请画出对长度为10的有序表进行折半查找(二分查找)的一棵判定树，并求其等概率时查找成功的平均查找长度。ASL=(1*1+2*2+3*4+4*3)/10=29/103、已知如下所示长度为12的表(JAN,FEB,MAR,APR,MAY,JUNE,JULY,AUG,S
2、EP,OCT,NOV,DEC)按表中元素顺序依次插入一棵二叉排序树，并求平均查找长度；若对表中元素先进行排序构成有序表，求折半查找时的平均查找长度；按表中元素顺序构造一棵平衡二叉树，并求平均查找长度。答：1)二叉排序树如下图：ASL=(1*1+2*2+3*3+4*3+2*5+6*1)/12=42/12=7/22)排序后的序列为：(APR,AUG,DEC,FEB,JAN,JULY,JUNE,MAR,MAY,NOV,OCT,SEP)折半查找树为：ASL=(l*l+2*2+3*4+4*5)/12=37/124、二叉排序树的生成过程中如果有相同的关键字应如何处理?II5、选取哈希函数H(
3、key)=keymod7,用链地址法解决冲突。试在0-6的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。答：根据给定的哈希函数和冲突处理方法构造哈希表如下图:在等概率情况下成功查找的平均查找长度ASL二(6*1+3*2+1*3)/10=3/26、对于给定关键字序列(502,087,512,061,908,170,897,275,653,462),分别写出直接插入排序、希尔排序(增量为5,2,1)、冒泡排序、快速排序、选择排序、堆排序、归并排序和基数排序运行上述数据的各趟结果。答：直接插入
4、排序：初始序列:(502),087,512,061,908,170,897,275,653,4621=1(087,502),512,061,908,170,897,275,653,4621=2(087,502,512),061,908,170,897,275,653,4621=3(061,087,502,512),908,170,897,275,653,4621=4(061,087,502,512,908),170,897,275,653,4621=5(061,087,170,502,512,908),897,275,653,4621=6(061,087,170,502,512,
5、897,908),275,653,4621=7(061,087,170,275,502,512,897,908),653,4621=8(061,087,170,275,502,512,653,897,908),4621=9(061,087,170,275,462,502,512,653,897,908)希尔排序：初始序列：(502,087,512,061,908,170,897,275,653增量为5：(502,087,512,061,908,170,897,275,653,462)排序后：(170,087,275,061,462,502,897,512,653,908)增量为2
6、：(170,087,275,061,462,502,897,512,653,908)排序后:»»(170,061,275,087,462,502,653,512,897,908)增量为1：(170,061,275,087,462,502,653,512,897,908)排序后:(061,087,170,275,462,502,512,653,897,908)快速排序：初始序列:(502,087,512,061,908,170,897,275,653,462)(462,087,275,061,170),502,(897,908,653,512)(170,087,275,061),4
7、62,(),502,(512,653),897,(908)(061,087),170,(275),462,(),502,(),512,(653),897,(908)(),(061),(087),170,(275),462,(),502,(),512,(653),897,(908)(061,087,170,275,462,502,512,653,897,908)堆排序：初始序列：(502,087,512,061,908,170,897,275,653,462)初始建堆(大顶堆人(9
