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-树。

解答：

 

 

 

 

 

 

 

 

 

圆角矩形标注: 插入G后产生分裂 

 

 

 

 

D  I  P
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

圆角矩形标注: 插入L，J后
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


12. 一棵4阶4层（不包括叶子结点）的B-树，至少有多少个关键字？至多有多少关键字？

解答：

é4/2ù =2,每个结点至少2棵子树（即1个关键字，故至少有24－1＝15个关键字。

   至多每个结点3个关键字（4棵子树），故关键字数：

   N＝1*3+41*3+42*3+43*3=255

 

13. 根据图9.3的一棵3阶B-树，(1)分别给出插入关键字2，12，16，17和18之后的结果；

(2)分别给出在原图上删除8和9之后的结果。

           

 

 

 

 

 

 

解答：

(1)           7                                  (7   11)

 

          3        (9   13)                    3      9      13  

 


(1  2) (4  5) 8  (10  11)(14  15) (1  2) (4  5)  8  10  12   (14  15)   

     插入2                                   插入12产生分裂

           (7   11)                                     11

 

          3        9    (13 15)                  7           15

               

(1  2) (4  5)  8  10  12  14  15         3       9       13     17

 


                                (1  2) (4  5)  8  10  12  14  16   18

  插入16后产生分裂                        插入17，再插入18后产生分裂

    （2）              7                                7

 


3                                   （10  13）              3          13

 


          1  （4  5）   9  11  （14  15）     1  （4  5） (10 11)  (14 15)

         删除8后                                    删除9后

 

14. 已知长度为7的表(SUN，MON，TUE，WED ，THU，FRI，SAT)

（1）试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等查找概率情况下，查找的平均查找长度。

（2）试用以下两种方法构造两个散列表，H（Key）=ëi/3û，其中i为关键字中的第一个字母在字母表的序号，

a. 用线性探测法处理冲突（散列地址空间为0—10）；

b. 用链地址法处理冲突；

c.然后分别求出两个哈希表在等查找概率时，查找成功和不成功的平均查找长度。

解答：

（1）                 SUN

 


                  MON        TUE          ASL＝1/7(1*1+2*2+3*3+1*4)=18/7

 


FRI        THU     WED

 


        SAT    

  (2) a： H（SUN）=ë19/3û=6

         H（MON）=ë13/3û=4

         H（TUE）=ë18/3û=6(冲突)，H（TUE）=（H（TUE）＋1）％11＝7

 H（WED）=ë23/3û=7(冲突)，调整到H（WED）=8

         H（THU）=ë18/3û=6(冲突)，经3次调整H（THU）=9

         H（FRI）=ë6/3û=2

         H（SAT）=ë19/3û=6(冲突)，经4次调整H（SAT）=10

哈希地址

0

1

2

3

4

5

6

7

8

9

10

关键字

 

 

FRI

 

MON

 

SUN

TUE

WED

THU

SAT

比较次数

 

 

1

 

1

 

1

2

2

4

5

  ASL（成功）＝1/7(3*1+2*2+1*4+1*5)=16/7

  ASL（失败）=1/11(1+1+2+1+2+1+6+5+4+3+2)=28/11

b： 

 

0

∧

1

∧

2

3

∧

4

 

5

∧

6

7

8

∧

FRI

∧

MON

∧

SUN

 

TUE

 

THU

 

SAT

∧

WED

∧


    ASL（成功）＝1/7(4*1+1*2+1*3+1*4)＝13/7
    ASL（失败）=1/9(1+1+2+1+2+1+5+2+1)=16/9

 

15. 设哈希表的地址范围为0－17，哈希函数为：H(Key)=Key%16,用线性探测法处理冲突，输入关键字序列:(10,24,32,17,31,30,46,48,40,63,49)造出哈希表，试回答下列问题：                            

    (1) 画出哈希表示意图；(2) 若查找关键字63，需要依次与那些关键字比较?

(3) 若查找关键字60，需要依次与那些关键字比较?

（4）假定每个关键字的查找概率相等，求查找成功和不成功时的平均查找长度。

解答：

  （1）

 

散列地址

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

关键字

32

17

63

49

 

 

 

 

24

40

10

 

 

 

30

31

46

47

比较次数

1

1

6

3

 

 

 

 

1

2

1

 

 

 

1

1

3

3

（2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63比较。

（3）查找关键字60，H（k）=60 MOD 16=12，散列地址12内为空，查找失败。

（4）ASLsucc=23/11

 

16.已知二叉树T的结点形式为(lchild,data,count,rchild),在树中查找值为x的结点，若找到，则记数count加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

typedef struct node

    { ElemType data;

      int count;

      struct node  *lchild, *rchild;

     }BSTNode,*BSTree;

void search(BSTree *t,  elemType x)

        //二叉排序树*t中，查找值为x的结点，若查找成功，返回0，否则，将值为x的结点插入二叉排序树中，并返回1。

{BSTree f=NULL,p=*t;

 while(p!=NULL&&p->data!=x)    //查找值为X的结点

      {f=p;

       if(p->data>x)           //沿左分树查找

          p=p->lchild;

       else

          p=p->rchild;         //沿右分树查找

          }//while

 if(p==NULL)                   //无值为X的结点,需生成

    {p=(BSTNode * ) malloc (sizeof(BSTNode));

     p->data=x;                //申请p结点, 并赋值。

     p->lchild=p-rchild=NULL;

     p->count=0;

     if(f==NULL)

        *t=p;                  //根结点

     else if(f->data>x)

         f->lchild=p;

        else

         f->rchild=p;

     return(1);

    }//if

 else                          //二叉排序树上有值为X的结点

     {p->count++;

      return(0);

         }

     }//结束算法

 

17. 二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

  （1）递归算法

      void  DecPrint(BSTree t）

        //递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。

          {if（t）

            {DecPrint(t->rchild)；

             if（!t->lchild && t->rchild）printf(t->data：4）

             DecPrint(t->lchild）；

            }

          }//DecPrint

（2）非递归算法

   void  DecPrint(BSTree t）

// 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值

 {BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大

    int  top=0；

    while（t || top>0）

      {while（t）

        {S[++top]=t；t=t->rchild ；} //沿右分枝向下

       if（top>0）

         {t=S[top--]；

          if（!t->lchild && t->rchild）printf(t->data：4)；

          t=t->lchild；  // 去左分枝

}//if

       }//while

    }//算法结束

 

18．试设计在二叉排序树中删除关键字为k的结点的算法。

[题目分析] 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。

void Delete(BSTree bst, keytype  k)

   //在二叉排序树bst上，删除其关键字为K的结点。

    {BSTree f,p=bst;

while (p && p->key!=k) //查找值为k的结点

    if (p->key>k) {f=p; p=p->lchild;}

    else {f=p; p=p->rchild;}

if (p==null) {printf(“无关键字为k的结点\n”); exit(0);}

if {p->lchild==null} //被删结点无左子树

     if (f->lchild==p) f->lchild=p->rchild;//将被删结点的右子树接到其双亲上

   else f->rchild=p->rchild;

else {q=p; s=p->lchild;        //被删结点有左子树

        while (s->rchild !=null) //查左子树中最右下的结点（中序最后结点）

          {q=s; s=s->rchild;}

        p->key=s->key;           //结点值用其左子树最右下的结点的值代替

        if (q==p) p->lchild=s->lchild;//被删结点左子树的根结点无右子女

        else q->rchild=s->lchild;     //s是被删结点左子树中序序列最后一个结点

        free(s);

       }

  }//算法结束

 

19. 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head,p,key)，检索具有关键字key的结点，并相应地修改p。

 typedef struct Node

    {elemType data;

     struct Node *prior,*next;

          }DLNode , * DLinkedList

     DLinkedList search(DLinkedList head,p,elemType heg)

     //在双向有序链表中,查找值为heg的结点,p指向为前结点

     //查找成功,返回结点指针,否则返回失败的信息NULL

     {if(p->data>heg)         //反向查找

        {while(p->data>heg&&p->data>p->prior->data)

               p=p->prior;    //若没找到值为heg的结点,并且链表仍递减

         if(p->data==heg)

            return(p);        

         else

            return(NULL);

            }//if

       else                    //正向查找

          {while(p->data<heg&&p->data<p->next->data)

                 p=p->next;

            if(p->data==heg)

               return(p);

            else

               return(NULL);

              }

         }

      

      

      [算法讨论] 上述算法按双向循环链表编制,控制循环中的第一个条件,是控制到"尾",如从大往小查时,遇到大的结束.若非循环链表,则控制条件可改为:

          while(p!=NULL&&p->data>heg)(反向查找)

       和

          while(p!=NULL&&p->data<heg)(正向查找)