9.2综合练习  

1.     假定对有序表：(3,4,5,7,15,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：(1)画出描述折半查找过程的判定树；(2)若查找元素54，需依次与哪些元素比较?

(3)若查找元素95，需依次与哪些元素比较?

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

解答：.（1）                                 

       

                                   30

 


5                                                                   63

 


                        3       15           62        87

 


                          4    7    24          54    72   95

 

（2）查找元素54，需依次与元素30，63，42比较，之后查到元素54。

（3）查找元素95，需依次与元素30，63，87比较，之后查到元素95。

（4）ASL(成功)=1/13(1*1+2*2+4*3+6*4)=41/13

ASL(失败)=1/14(2*3+12*4)=54/14

 

2.       用不同的输入顺序输入n个关键字，可能构造出的二叉排序树具有多少种不同形态?

解答：1/(n+1)*(2n)!/(n!)* (n!)

 

3.       画出对长度为16的有序表进行二分查找的判定树,并求其等概率时查找成功和不成功的平均查找长度。

解答：

                             8

 

                         4               12

 

2        6        10       14

               

                1    3    5     7    9    11  13    15

 

                                                        16

  ASL(成功)=1/16(1*1+2*2+4*3+8*4+1*5)=54/16

  ASL(失败)=1/17(15*4+2*5)=70/17

 

4.       设有一组关键字(72，35，124，153，84，57)需插入到表长为12的散列表中。设计一个合适的散列函数。用设计出的散列函数将上述关键字插入散列表。请画出建好的散列表结构（假定用线性探测法解决冲突）。指出该散列表的装填因子是多少。

解答：

哈希函数  H(key)=key%11

 

哈希地址

0

1

2

3

4

5

6

7

8

9

10

11

关键字

 

 

35

124

57

 

72

84

 

 

153

 

比较次数

 

 

1

1

3

 

 

1

 

 

1

 

   装填因子    α=6/12=0.5

 

5.       设有一个输入数据的序列是(46, 25, 78, 62, 12, 37, 70, 29)，试画出从空树起，逐个输入各个数据而生成的二叉排序树。

解答：

                                    46

 

25                            78

 

12    37    62

 

29                                       70

 

6.       从一棵二叉排序树中删除两个元素，该二叉排序树的形态是否与元素的删除次序有关？

  解答：有关，除非删除的都是叶子。

 

7.       将关键字(DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN)按字母顺序依次插入到一棵初始为空的AVL树中，画出每插入一个关键字后的AVL树，并标明平衡旋转的类型。在所建立的AVL树中删除关键字MAY，为保持AVL树的特性，应如何进行删除和调整? 若接着删除关键字FEB，又应如何删除与调整?

    解答：

    DEC                  FEB                         NOV

 


        FEB  -(RR)à    DEC    NOV     --(RR)à   FEB     OCT   --LLà

 


         NOV                JUL   OCT         DEC  JUL     SEP

 


SEP      AUG

 


       APR                                                                    

                NOV                                   NOV  

 

FEB     OCT    ---(RR)à             FEB     OCT      --(LR)à

 


AUG   JUL      SEP                 AUG   JUL      SEP

 


APR   DEC   MAR                    APR   DEC   MAR

 


               MAY                              JUL   MAY

 


                                                    JUN

 

                            

MAR

 


FEB            NOV

 


AUG     JUL      MAY    OCT

 


APR   DEC  JAN  JUN           SEP

 

8.       对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少?

解答：高h的AVL树，最少结点为Nh =Fh+2-1, Fh≈Фh/。其中Ф=(1+)/2,

  即 Nh≈Фh+2/{-1}。有n个结点的平衡二叉树的最大高度是logФ( (n+1))-2

最小高度ëlog2nû

 

9.       k1,k2,k3是三个不同的关键字且k1>k2>k3。按不同的输入顺序建立相应的二叉排序树。

解答：共1/(n+1)*(2n)!/(n!)(n!)=5种

                         

 

10.   对于一棵有1999999个关键字的199阶B-树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。

解答： 最大层数

           L=logém/2ù (N+1/2)+1,即L<=4

   最小层数:L=3,因第一层198,第二层199*198,第三层199*199*198个关键字。1,999,999<198+199*198+199*199*198。(大于满两层的B-树而小于满三层的B-树――不包括失败的n个子结点层)

 

11.   给定一组记录，其关键字为字符。记录的插入顺序为(C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J)，给出插入这些记录后的4阶B-树。

解答：