第四阶段测考试试题汇总--答案.doc

第四阶段测考试试题汇总--答案.DOC:..1、以关键字序列为例(256,301,751,129,256,937,856,076)生成二叉排序树,并说出查找076和900的比较次数。答:生成的二叉排序树如下图:查找076,需比较3次,分别与256、129和076比较,査找成功;查找900,需比较5次,分别与256、301>751>,查找失败。2、请画出对长度为10的有序表进行折半查找(二分查找)的一棵判定树,并求其等概率时查找成功的平均查找长度。ASL=(1*1+2*2+3*4+4*3)/10=29/103、已知如下所示长度为12的表(JAN,FEB,MAR,APR,MAY,JUNE,JULY,AUG,SEP,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(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)、冒泡排序、快速排序、选择排序、堆排序、归并排序和基数排序运行上述数据的各趟结果。答:直接插入排序:初始序列:(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,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