已知如下所示长度为9的表{16、3、7、11、9、26、18、14、15}[br][/br]1. 按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出等概率情况下查找成功的平均查找长度；[br][/br]2. 若对表中的元素进行排序构成有序表，对此有序表进行折半查找，画出对其进行折半查找时的判定树，并计算出查找成功的平均查找长度；[br][/br]3. 按表中元素的顺序构造一棵二叉平衡树，画出完成后的二叉平衡树，并求出等概率情况下查找成功的平均查找长度。
答1、[img=197x180]17af05baa3017ab.png[/img]查找成功的平均查找长度=(5×2+4×2+3×2+2×2+1)/9=29/9[br][/br]2.[img=356x203]17af05be9191c07.png[/img]查找成功的平均查找长度= (4×2+3×4+2×2+1)/9=25/9[br][/br]3。[img=222x137]17af05c25558c14.png[/img]查找成功的平均查找长度=(4×2+3×4+2×2+1)/9=25/9
举一反三
- 【简答题】关键字序列为 ( 12, 7, 17, 11, 16, 2, 13, 9, 21, 4 ) : (1) 按元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树 ; (2) 求等概率情况下 , 二叉排序树中查找成功和查找 失败 的平均查找长度 ; (3) 将 该 关键字 序列排序构成有序表,求等概率情况下 ,对 该有序表进行折半查找查找成功和查找失败时的平均查找长度
- 画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。
- 依次输入表（30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。要求：1）画出这个二叉排序树。2）写出该二叉排序的中序遍历序列。3）假定每个元素的查找概率相等，试计算查找成功的平均查找长度。
- 长度为11的有序顺序表(4,9,11,16,23,28,37,46,69,71,88),用折半查找对该表进行查找。(1)画出折半查找所对应的判定树;(2)查找元素46,需要依次与哪些元素比较?(3)查找元素72,需要进行的元素比较次数?
- 长度为11的有序表进行折半查找时，在等查找概率情况下查找成功的平均查找长度为 （ ） 。
内容
- 0
对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为______，查找不成功的平均查找长度为______。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为______。 A: 20/9 B: 18/9 C: 25/9 D: 34/9
- 1
在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。��平均查找长度不同。
- 2
2．应用题 （1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： ① 画出描述折半查找过程的判定树； ② 若查找元素54，需依次与哪些元素比较？ ③ 若查找元素90，需依次与哪些元素比较？ ④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 要求手写作业，拍照上传
- 3
对于长度为11的有序表，按折半查找，在等概率情况下查找成功时，其平均查找长度是（ ）。 A: 1 B: 2 C: 3 D: 4
- 4
中国大学MOOC: 对于长度为11的有序表，按折半查找，在等概率情况下查找成功时，其平均查找长度是（ ）。