数据结构自考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)给出各符号的哈夫曼编码。

对含n个元素的数据序列采用快速排序算法进行排序,在最坏情况下的时间复杂度是_________。

散列方法中,表示散列表装满程度的指标a称为_________。

如果图G存在拓扑排序序列,则G必为_________。

二叉树的前序遍历序列和后序遍历序列中,叶结点之间的相对次序_________。

将一棵树T转换为一棵二叉树T1,在T1中结点A是结点B的父结点,则在T中,A可能是B的父结点或_________。

一个直接或间接调用自己的函数称为_________。

广义表(a,(b,c,d),e,f,(g,h))的表尾是_________。

指针p和指针q分别指向单链表L中的两个相邻结点,即q>nextp,且p所指结点不是终端结点。若要删除p所指结点,则执行的语句是_________。

数据的逻辑结构是从逻辑关系上描述数据,它与数据元素的存储结构_________。

设散列表长m=14,散列函数H(key)=key%11，表中已保存4个关键字：addr(15)=4，addr(38)=5，adr(61)=6，addr(84)=7，其余地址均为空。保存关键字49时存在冲突，采用线性探查法来处理。则查找关键字49时的探查次数是(　　)

一棵二叉排序树中,关键字n所在结点是关键字m所在结点的祖先,则(　　)

一组记录的关键码为(45,68,57,13,24,89)，利用堆排序算法进行升序排序，建立的初始堆为(　　)

下列排序方法中,稳定的排序方法是(　　)

对数据序列(25,15,7,18,10,0,4)采用直接插入排序进行升序排序，两趟排序后，得到的排序结果为(　　)

无向图G中所有顶点的度数之和是20,则G中的边数是(　　)

设有向图G含有n个顶点、e条边,使用邻接表存储。对G进行广度优先遍历的算法的时间复杂度是(　　)

用邻接矩阵表示有n个顶点和e条边的无向图，采用压缩方式存储，矩阵中零元素的个数是(　　)

在一棵非空二叉树的中序遍历序列中,所有列在根结点前面的是(　　)

已知一棵高度为4的完全二叉树T共有5个叶结点,则T中结点个数最少是(　　)

已知广义表LS=(((ab)),((c,(d)),(e,(f))),(g,h)),LS的深度是(　　)

设指针变量head指向非空单循环链表的头结点,指针变量p指向终端结点,next是结点的指针域,则下列逻辑表达式中,值为真的是(　　)

设栈的初始状态为空，元素1,2,3,4,5,6依次入栈，栈的容量是3，能够得到的出栈序列 是(　　)

下列选项中,与数据存储结构直接相关的是(　　)

将12个数据元素保存在顺序表中,若第一个元素的存储地址是100,第二个元素的存储地址是105,则该顺序表最后一个元素的存储地址是(　　)