数据结构自考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的表达式。

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

对具有15个关键字的关键字序列进行顺序查找时,查找成功的平均查找长度为_______。

设关键字序列为28,72,97,63,4,53,84,使用希尔排序法将其排成升序序列,若第一趟采用的间隔是3,则该趟排序的结果是________。

在有向图、无向图中,其邻接矩阵一定对称的是________。

要计算图中从某一顶点出发到其余各顶点的最短路径,可选用________算法。

一棵树的后序遍历序列与其对应的二叉树的________序遍历序列相同

广义表A=(x,(y,z,(u,v,w)))的长度是________。

下面程序段的时间复杂度是________。

i=1;

在单链表的p结点之后插入s结点的操作是________。

只能在线性表的两端进行插入或删除操作的两种逻辑结构分别是________。

对线性表L进行二分查找时,要求L必须满足(　　)

下列排序算法中，初始数据有序时，花费的时间反而更多的算法是(　　)

下列排序算法中，空间复杂度最差的是(　　)

若要求对序列进行稳定的排序，则在下列选项中应选择(　　)

无向图G如题10图所示，从顶点a开始进行深度优先遍历，下列遍历序列中，正确的是(　　)

设图的邻接矩阵A如下所示。各顶点的度依次是(　　)

设带权连通图G中含有n(≥1)个顶点，下列关于g的最小生成树T的叙述中， 正确的是(　　)

一棵非空二叉树T的前序遍历和后序遍历序列正好相反,则T—定满足(　　)

设髙度为h的二叉树中， 只有度为0和2的结点， 则此类二叉树包含的结点数至少 是(　　)

广义表A=(a,(b,c, (e,f)))，函数head(head(tail(A)))的运算结果是(　　)

设顺序表首元素A[0]的存储地址是4000,每个数据元素占5个存储单元,则元素 A[20]的起始存储地址是(　　)

数据元素1,2,3,4,5依次入栈，则不可能得到的出栈序列是(　　)

瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序。这里的数据结构指的是(　　)

线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址 (　　)

下列选项中，属于非线性数据结构的是(　　)