数据结构第九章 查找 习题及答案(4)

数据结构课件

10. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

（1） 按次序构造一棵二叉排序树BS。

（2） 依此二叉排序树，如何得到一个从大到小的有序序列？

（3） 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度 （4） 画出在此二叉排序树中删除“66”后的树结构。

11. 给定关键词输入序列{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO}，假定关键词

比较按英文字典序，试画出从一棵空树开始，依上述顺序（从左到右）输入关键词，用平衡树的查找和插入算法生成一棵平衡树的过程，并说明生成过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数。 12. 假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：

(1).画出描述折半查找过程的判定树；

(2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较?

(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。

第9章 查找

一．选择题

三．填空题

1．n n+1 2．6,9,11,12 3．5

4．26（第4层是叶子结点，每个结点两个关键字） 5．m-1,「m/2 -1 9．2,4,3

6．小于等于表长的最大素数或不包含小于20的质因子的合数

8．(n+1)/2 9．(n+1)/n*log2(n+1)-1 10．结点的左子树的高度减去结点的右子树的高度 11．(1)静态查找表(2)动态查找树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区