【简答题】关键字序列为 ( 12, 7, 17, 11, 16, 2, 13, 9, 21, 4 ) : (1) 按元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树 ; (2) 求等概率情况下 , 二叉排序树中查找成功和查找 失败 的平均查找长度 ; (3) 将 该 关键字 序列排序构成有序表,求等概率情况下 ,对 该有序表进行折半查找查找成功和查找失败时的平均查找长度
(1) 以下是该关键字序列构成的二叉排序树: (2) 该二叉排序树的查找性能: ASL succ = (1 ́ 1 + 2 ́ 2 + 4 ́ 3 + 3 ́ 4) / 10 = 29 / 10 ; ASL unsucc = (5 ́ 3 + 6 ́ 4) / 13 = 39 / 11 。 (3) 以下是该关键字排序后,进行折半查找的判定树: ASL succ = (1 ́ 1 + 2 ́ 2 + 4 ́ 3 + 3 ́ 4) / 10 = 29 / 10 ; ASL unsucc = (5 ́ 3 + 6 ́ 4) / 13 = 39 / 11 ; 两者凑巧一致。
举一反三
- 已知如下所示长度为9的表{16、3、7、11、9、26、18、14、15}[br][/br]1. 按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出等概率情况下查找成功的平均查找长度；[br][/br]2. 若对表中的元素进行排序构成有序表，对此有序表进行折半查找，画出对其进行折半查找时的判定树，并计算出查找成功的平均查找长度；[br][/br]3. 按表中元素的顺序构造一棵二叉平衡树，画出完成后的二叉平衡树，并求出等概率情况下查找成功的平均查找长度。
- 依次输入表（30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。要求：1）画出这个二叉排序树。2）写出该二叉排序的中序遍历序列。3）假定每个元素的查找概率相等，试计算查找成功的平均查找长度。
- 在一棵空的二叉排序树中依次插入关键字序列为49,38,65,97,76,13,27,44,82,35,50,请画出所得到的二叉排序树,求在等概率的情况下进行二叉排序树查找成功的平均查找长度。
- 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。��平均查找长度不同。
- 由关键字序列（57,24,76,63,18,31,15）生成的一棵二叉排序树，其等查找概率情况下查找成功的平均查找长度为
内容
- 0
用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度
- 1
长度为11的有序表进行折半查找时，在等查找概率情况下查找成功的平均查找长度为 （ ） 。
- 2
画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。
- 3
中国大学MOOC: 对关键字序列{13,25,17,10,12,8,22,4,45,30}构造二叉排序树，查找概率相同的情况下，查找成功的平均查找长度为（ ） 。
- 4
对于关键字序列(30,25,40,35,45)，按序列次序创建一颗二叉排序树，在等概率情况下查找成功时，其平均查找长度是（）。