数据结构自考2016年4月真题及答案解析

实现f34,对含有n个整数的数组A进行选择排序。函数原型如下。

void f34( int A[], int n); //对含有n个整数的数组A进行选择排序

给出二叉链表定义如下。程序f33生成原二叉树的镜像树,即将二叉树中所有结点的左、右子树互换。请在空白处填写适当内容,完成其功能。

typedef char DataType;

typedef struct node{

        DataType data;                            //data是数据域

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

 } BinTNode;;

 typedef BinTNode"BinTree;

 BinTree f33( BinTree T)

          {    Bin Tree NewT;

               if(____(1)_____  return NULL;

                  ____(2)_____=( BinTree)malloc( sizeof( BinTNode));

              NewT->data= T->data;

               NewT->lchild=____(3)_____;

               NewT->rchild=____(4)_____;

               return ____(5)_____;

}

设带头结点的单链表初始为空。将从键盘读入的每个字符作为一个结点加入该链表表尾,当读入回车符时结束并返回链表表头指针。请在空白处填写适当内容,完成其功能。

typedef struct node

{   char data;

      struct node *next;

}ListNode;

typedef ListNode *LinkList;

LinkList f32()

{      LinkList head= NULL’

      ListNode *p, *rear;\

     char ch;

      head=( ListNode *)malloc( sizeof( ListNode ));

     rear= head;

      while(( ch=getchar())!="\n')

            { ____(1)_____;

                 p->data=ch;

              ____(2)_____;

             rear= p;

               }

          rear->next=NULL;

         ____(3)_____;

}

已知栈的基本操作定义如下,请在空白处填写适当内容,完成相应的功能。

 typedef struct { //栈定义

      char data[ Stack Size];

       int top;

} SeqStack;

SeqStack s;

void InitStack( SeqStack *s)   //栈初始化

 {        s->top=-1;

}

int StackEmpty( SeqStack *s)   //判栈是否为空

{     retum ____(1)_____;

}

   int StackFull( SeqStack *s)  //栈是否为满

{       retum s->top== StackSize-1;

 }

 char push( SeqStack*s, char c)     //入栈操作

{      if( Stack Full( s ))

         return ‘\0’;          //操作失败

       else ____(2)_____=c;

        return c;        //操作成功

 }

   char pop( Seq Stack *s)     //出栈操作

{        if( Stack Empty(s))

      return 0; //操作失败

    else return ____(3)_____; //操作成功

}

阅读程序f0。

int f30( int A[], int n)

{   int m;

   if (n<=0) return=-1;

     if(n==0 )retum=0

     m=f30(A,n-1);"

   if(A[m]>A[n-1]) return m;

else return n-1;

}

已知线性表A={25,34,256,9,38,47,128,256,64}。

(1)若主函数调用语句为f30(A,5),f30的返回值是多少?

(2)若主函数调用语句为f30(A,9),f30的返回值是多少?

(3)给出算法f30的功能。

已知有向图G=(V,E)，其中={v1,v2,v3,v4,v5,v6,v7}，E={,,,,,,,,}。

(1)画出有向图G:

(2)判断图G是否存在拓扑排序序列,若不存在请说明理由;若存在请给出一个拓扑排序序列。

给定一组权值数据{3,8,9,11,4},回答下列问题。

(1)画出基于所给数据的一棵哈夫曼树;

(2)计算所得哈夫曼树的带权路径长度WPL。

已知4×5稀疏矩阵M按行优先顺序存储的三元组表如下：

(1)写出矩阵M;

(2)给出矩阵M的转置矩阵T按行优先顺序存储的三元组表。

设Q是有N个存储空间的循环队列,初始状态font=rear=0,约定指针rear指向的单元始终为空。定义如下：

#define N 100

typedef struct{

       char data[N];

        int front, rear;

}CQ:

CQ*Q:

(1)写出清空队列的语句序列;

(2)写出判断队列为满的表达式;

(3)给出计算队列长度L的表达式。

在二又排序树的查找过程中,若当前结点的关键字值大于待查找关键字,则应在该________结点的子树上继续查找。