内容发布更新时间 : 2024/11/20 13:40:14星期一 下面是文章的全部内容请认真阅读。

序:

(1)插入一颗初始为空的二叉排序树，试画出插入完成之后的二叉排序树; (2) 插入一颗初始为空的平衡二叉树； (3) 画出一棵最佳二叉排序树。

并计算在等概率查找情况下，以上三种各自查找成功的平均查找长度。 【解答】

24．已知一关键字序列为(13，19，39，24，28，57，76，51，84)，散列函数为H(key)=key % 11，利用链地址法处理冲突，元素插入单链表时总是插在表头做第一个结点。试构造散列表，并计算查找成功的平均查找长度。 【解答】

26

25．已知长度为l2的表{50，45，80，5，90，70，65，20，99，97，95，30} （1） 试按表中元素的次序依次插入一棵初始为空的二叉排序树，并求在等概率情况下查找成功的平均查找长度。 （2） 用表中元素构造一棵最佳二叉排序树，求在等概率的情况下查找成功的平均查找长度。

（3） 按表中元素顺序构造一棵AVL树，指出是什么类型的旋转，并求其在等概率情况下查找成功的平均查找长度。 【解答】

27

26. Fibonacci树是一种特殊的二叉树，下面给出构造该树的一种算法： procedure FibonacciTree (d: integer; Var T: binarytree) { //d 是Fibonacci树的深度 if d=0 then T:=nil else{new (T);

if d=1 then {T^.lefptr:=nil; T^.rightptr:=nil } else { //d>=2

FibonacciTree(d-2,T^.leftptr); FibonacciTree(d-1,T^.rightptr); } } }

(1) 画出深度为4的Fibonacci树（即用d=4调用上述算法的结果）（7分） (2) 从你画的树中分析深度d的Fibonacci 树中结点总数和Fibonacci数的关系。

Fibonacci数定义如下： F0=1， F1=1

Fn=Fn-1+Fn-2 n>1

(3)你所画出的Fibonacci树是否为平衡二叉树？若是，它是否为同样深度的平衡二叉树中结点数目最少的一种？（4分）【中国科学技术大学1998三(15分)】 【解答】

28

27. 已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 【山东大学 2001 七 ( 7分)】 【解答】

28. 使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。

29

（1）使用线性探查再散列法来构造散列表。（5分） （2）使用链地址法构造散列表。（5分）

针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。（5分） 【清华大学 1998 五 （15分）】 【解答】

29. 已知长度为12 的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)

(1) 试按表中元素的顺序依次插入一棵初始为空的分类二叉树，试画出插入完成之后的分类二叉树并计算其在等概率查找情况下，查找成功的平均查找长度。 (2) 试用以下两种方法构造两个Hash表，Hash函数H(K)=[i/2],其中i为关键字K中第一个字母在字母表中的序号，[ ]表示取整数。 a. 用线性探测开放定址法处理冲突(散列地址空间为0～16);

b. 用链地址法处理,然后分别求出这两个Hash表在等概率查找情况下，查找成功的平均查找长度。

【上海海运学院 1996 五 （15分）】 【解答】

30