数据结构自考2017年10月真题及答案解析

已知二叉树的存储结构类型定义如下:

typedef struct node{

     int data;

     struct node *lchild, *rchild;

 } BinNode;

 typedef BinNode *BinTree;

编写递归算法,对于给定的一棵二叉树T,将其修改为镜像二叉树。例如,题34图所示的两棵二叉树互为镜像二叉树。

函数的原型为:vod f34( BinTree T);

待排序记录的数据类型定义如下:

#define maXsize 100

typedef int KeyType;

typedef struct {

      KeyType key;

} RecType;

typedef RecType SeqList [MAXSIZE];

下列算法实现自底向上、自顶向下交替进行的双向扫描冒泡排序,请在空白处填上适当内容使算法完整。

void f32( SeqList R, int n)

{      int i=0;

       RecType t;

      int NoSwap=1;

    while(NoSwap) {    

          NoSwap=0;

          for(j=n-i-1; ____(1)____)

            if(R[j].key t=R[j];

             R[i]=R[j-1];

             R[j-1]=t;

               NoSwap=1;

            }

        for(____(2)____; j++)

      if(Ri]. key>R[j+1].key){

             t=R[i];

              R[j]=R[j+1];

             R[j+1]=t;

           NoSwap=1;

     }

        ___(3)____;

        }

}

二叉树的存储结构类型定义如下:

typedef int DataType;

typedef struct node

{ DataType key;      //data是数据域

 Struct node *lchild, *rchild; //分别指向左右孩子

 } BinTNode;

typedef BinTNode *BinTree;

阅读下列算法,并回答问题

void A33(BinTree root, int k1, int k2, int end)

 {     if (root==NULL) return;

        A33(root->lchild, k1, k2, end);

        if (end) return;

       if (root->key>k2){

          end=1;

         return;

        }

     if (root->key >=k1) printf( "%d", root->key);

       A33(root->rchild, k1, k2, end);

}

(1)设二叉排序树T如题33图所示,bt是指向根结点的指针。给出执行A33(bt,6,100,0)的输出结果。

(2)给出该算法的功能。

设有二叉排序树如题29图所示。请回答下列问题。

(1)假定二叉排序树初始为空,写出一个数据输入序列,按序插入时能得到题29图所示的二叉排序树。

(2)能得到题29图所示的二叉排序树的不同的输入数据序列有几个?

顺序表类型定义如下

#define ListSize 100

typedef struct{

     int data[ListSize];

     int length;

}SeqLiist;

阅读下列算法,并回答问题。

void change(SeqList *SL1, SeqList *SL2)

{        int minlength;

        int k=0, temp;

        if(SL1->length< SL2->length) return;

       minlength= SL2->length;

        while( k< minlength)

   {          if (SL1->data[k]< SL2->data[k])

     {         temp=SL1->data[k];

                 SL1->data[k]=SL2->data[k];

              SL2->data[k]=temp;

     }

          k++;

      }

        return;

   }

       void f30( SeqList *SL1, SeqList*SL2)

 {   if( SL1->length>SL2->length) change( SL1, SL2 );else change( SL2, SL1 );return;}(1)若SL1->data中的数据为{25,4,256,9,-38,47,128,256,64},SL2->data中的数据为{22,4,-63,15,29,34,42,3},则执行算法f30(&SL1,&SL2)后SL1->data和SL2->data中的数据各是什么?

(2)该算法的功能是什么?

二叉树的存储结构类型定义如下:

typedef char Data Type;

typedef struct node

{       DataType data;      //data是数据域

       struct node *lchild, * rchild;       //分别指向左右孩子

}BinTNode;

typedefBinTNode *BinTree;

阅读下列算法,并回答问题。

void A31( BinTree T)

{     if(T!= NULL)

 { printf( "%c", T->data );

     A31(T->rchild );

     printf("%c",T->data);

      A31(T->lchild );

    }

    return;

 }

(1)设二叉树T如题31图所示,给出执行A31(T)的输出结果。

(2)给出该算法的时间复杂度。

已知图G采用邻接矩阵存储,邻接矩阵如题27图所示。

(1)写出从顶点A开始图G的3个不同的深度优先搜索遍历序列。

(2)写出从顶点A开始图G的2个不同的广度优先搜索遍历序列。

有以下数据序列(19,14,23,01,68,20,84,27,55,11,10,79,12),使用希尔排序方法将其排成升序序列。请回答下列问题

(1)写出增量为4时对上述数据序列进行一趟希尔排序的结果。

(2)给出一个可行的希尔排序增量序列。

假设顺序存储的有序表R含有12个关键字,进行二分查找时,平均查找长度为_________。

设电文字符集是{e1,e2,e3,e4,e5},它们出现的次数分别为:{50,10,16,8,12}。现要为该字符集设计哈夫曼编码。请回答下列问题。

(1)画出得到的哈夫曼树。

(2)给出各符号的哈夫曼编码。