第9章 查找-作业.pdf

作业 1. 已知如下所示长度为12的表 (Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec) ⑴试按表中元素的顺序依次插入一棵初始为空的二 叉排序树，画出插入完成后的二叉排序树，并求其在等 概率的情况下查找成功的平均查找长度。 ⑵若对表中元素先进行排序构成有序表，求在等概 率情况下对此有序表进行折半查找时查找成功的平均查 找长度。 ⑶按表中元素顺序构造一棵平衡二叉排序树，并求 其在等概率的情况下查找成功的平均查找长度。 ⑴ 求得的二叉排序树如下图所示，在等概率情况 下查找成功的平均查找长度为： ASLsucc=1 ／12(1 ×1+2 ×2+3 ×3+4 ×3+5 ×2+6 ×1)=42 ／12 Jan Feb Mar Apr June May Sept Aug July Oct Dec Nov ⑵ 经排序后的表及在折半查找时找到表中元素所 经比较的次数对照如下： Apr Aug Dec Feb Jan July June Mar May Nov Oct Sept 3 4 2 3 4 1 3 4 2 4 3 4 July Dec May Apr Feb June Oct Aug Jan Mar Nov Sept 等概率情况下查找成功的平均查找长度为： ASLsucc=1 ／12(1 ×1+2 ×2+3 ×4+ 4 ×5 ）=37 ／12 ⑶ 平衡二叉树构造过程为： Jan Jan Jan Feb Feb Mar Jan Jan Feb Mar Feb Mar May Apr Apr Jan Feb Mar Apr May Jan Jan