数据结构导论2009年1月真题及答案解析（02142）

下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。

Void level(BSTree root，p)

{  int level=0;

   if( !root )

          (1)_________;

   else {

             level++;

             while( root->key!=p->key ) {

                   if( root->keykey )

                     (2)_________ ;

               else

                     (3)_________ ;

               level++;

               }

          (4)_________;

          }

}

完善下列折半插入排序算法。

Void binasort( struct node r[MAXSIZE], int n )

{  for( i=2; i<=n; i++ ) {

        r[0]=r[i]; low=1; high=i-1;       

       while( low<=high ) {

                mid=（1）_________;

                 if( r[0].key

                       high="(2)_________;

                 else low=(3)_________;     

       }

       for( j=i-1; j>=low; j-- )

             (4)_________;

       r[low]=r[0];

   }

}

用快速排序法对数据序列(49，38，65，97，16，53，134，27，39)进行排序，写出其第一趟排序的全过程。

已知某图的邻接表存储结构如题31图所示：

                                                题31图

(1)画出该图。

(2)根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。

假定采用H(k)=k mod 7计算散列地址，引用线性探测的开放定址法解决冲突，试在0~6的散列地址空间中，对关键字序列(38，25，74，63，52，48)构造散列表，并求出等概率情况下查找成功的平均查找长度。

冒泡排序最好的时间复杂度为_________，平均时间复杂度为_________，是一种稳定的排序算法。

已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。

将题30图所示的由三棵树组成的森林转化为一棵二叉树。

                                                   题30图

在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是 _________。

假定对线性表R[0…59]进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为_________。