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

已知带有头结点的单链表定义如下:

typedef struct node

{    char ch;

      struct node *next;

} ListNode;

typedef ListNode *LinkList;

请编写函数int f34( LinkList h, char string[]);根据输入的字符串,建立不含重复字符的链表

阅读程序,写出执行结果。

void f33(int a[], int n)

{    int i;

      for(i=(n-1)/2; i>=0; i--)

      Sift(a, i, n-1);

}

   void Sift( inta[], int i, int h)

 {    int j, temp *a[i];

      j=2*i+1;

     while(j<=h)

{  if((j

      j++;

      if( temp=>=a[j])

     break;

     a[i]=a[j];

      i=j;

       j=2*i+1;

}

 a[i]=temp;

}

int main()

{          int i, a[10]={10,20,5,23,25,62,21,1,32,39};

          f33(a,10);

          for(i=0; i<10; i++)

            printf(“%d,”,a[i]);

      printf(“\n”);

       return 0;

}

执行结果:

已知二叉树T如题32图所示。

阅读程序f32,写出执行f32(T)的输出结果。

typedef char DataType

typedef struct node

{      DataType data;        //data是数据域

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

} BinTNode;

typedef BinTNode * BinTree;

void f32( BinTree bt)

{      if(bt!=NULL)

   {   f32(bt->rchild);

 printf(“%c”, bt->data);

 f32(bt->lchild);

 }

}

执行结果：

程序f31是将输入的m行n列的二维数组a变换为三元组表形式存储在数组b中。请在空白处填上适当内容将算法补充完整。

#define MAXSIZE 100

typedef int DataType;

typedef struct {

       int i, j;                 //1非零元素行列下标

      Data Type v;      //非零元素值

} TriTupleNode;

typedef struct {

     TriTupleNode data[MAXSIZE];         //存储三元组数组

     int m, n, t;             //m:矩阵的行,n:矩阵的列,t非零元素数量

} TSMatrix;

    void f31(TSMatrix *b, int*a, int m, int n)          

    //将m行n列的矩阵a变换为三元组表形式存储在b中

{     int i, j, k=0;

      for(i=0; i

       for(j=0; j

         {    b->data k].i=i;

                b->data k].j=j;

                b->data[k].v=____(1)____;

              ____(2)____;

          }

         b->m=m;

         b->n=n;

          b->t=____(3)____;

}

设图G如题28图所示题28图回答下列问题。

(1)图G是否是有向无环图?

(2)给出图G所有的拓扑排序序列。

设关键字序列为:53,15,72,52,48,67,63,23。已知散列表地址空间为0~11,散列函数为H(k)=kmod11,采用线性探查再散列法解决冲突。

(1)将所给关键字数据依次填入该散列表中;

(2)计算等概率下查找成功的平均查找长度。

已知队列的基本操作定义如下,请在空白处填写适当的语句,完成指定的功能。#define QueueSize 100

typedef struct {        //队列定义

       char data[QueueSize];

        int front, rear;

 } CirQueue;

 CirQueue Q;

void Init Queue( CirQueue *Q)     //队列初始化

{      Q->front=Q->rear=0;;

}

 int Queue Empty( CirQueue *Q)       //判队列是否空

{ return ____(1)____;

}

int Queue Full( CirQueue * Q)         //判队列是否满

{    return(Q->rear+ 1)% QueueSize==Q->front;

 }

 char EnQueue( CirQueue *Q, char c)      ///入队操作

{     if (QueueFulk(Q))

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

    else

 {     Q->data[ Q->rear]=c;

      Q->rear=____(2)____;

    retum c;       //操作成功

 }

}

 char DeQueue(CirQueue *Q)       //出队列操作

{     char x;

    if( Queue Empty(Q))

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

    else

 {     x=Q->data[[Q->font];

    O->front=____(3)____;

   retum x;      //操作成功

   }

}

两个栈共享数组空间data[m](定义如下),它们的栈底分别设在数组的两端(初始化后topl=-1,top2=m).

typedef struct{

DataType data[m];

int top1, top2;

}SeqStack;回答下列问题。

(1)编写判断栈满的函数 int stackfull( SeqStack *s);

(2)编写进栈函数 void push( SeqStack *s, int si, DataType x);其中,si取值为0、1,分别表示栈底为0或m-1的栈。

已知二叉树T中含有元素A,B,C,D,E,F,G,H,T的前序遍历序列、中序遍历序列和后序遍历序列如下,其中符号____表示未知元素。试写出①到⑩所代表的正确元素值。

前序遍历序列 A B D ① E F G ②

中序遍历序列 ③ B A ④ C G F ⑤

后序遍历序列 ⑥ ⑦ ⑧ ⑨ H F C ⑩

对箱排序的改进和推广的排序算法是_________。

一组记录的关键字为(45,53,18,49,36,76,13,97,36,32),利用快速排序方法对其进行排序，选择45为基准，一次性划分后的结果为_________。

一个连通图的_________是包含图中所有顶点的极小连通子图。

求单源最短路径的迪杰斯特拉( Dijkstra)算法是按照路径_________不减的次序求出各条路径的。

无向图G中含7个顶点,顶点间的边是随机设置的,为保证图G在任何情况下都是连通的,则需要的边数最少是_________。

对长度为1的广义表A,若有 Head(A)=Tail(A),则A=_________。

设高为h的二又树T中只有度为0和2的结点,则T包含的结点数最多为_________。

在二维数组A[10][8]中,每个数组元素占用4个存储单元,则数组A需要的存储单元个数是_________。

为便于实现单链表的插入及删除运算，需要在单链表中增加一个结点，该结点称为_________。

在数据结构中,从逻辑上可以把数据结构分为线性结构和_________。

线性表采用顺序存储或链式存储，对其进行查找的方法应是(　　)

设有序表为(1,3,9,12,32,41,45,62,75,77,82),采用二分查找法查找关键字75,查找过程中关键字之间的比较次数是(　　)

下列排序算法中,在每一趟都能选出一个元素放到其最终位置上的是(　　)

若数据元素序列11,13,15,7,8,9,23,2,5是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法是(　　)

如果无向图G的最小生成树T中含有边(a,b)和(a,c),则下列选项中，一定不在T中的边是(　　)

          题11图

若图G的邻接表中有奇数个表结点,则G是(　　)

若用邻接矩阵存储有向图，矩阵主对角线以下的元素均为零，则关于该图拓扑排序序列的结论是(　　)

根据二叉树的定义,3个结点构成的二叉树的树型有(　　)

一棵有序树可转换为一棵二叉树,树的后序遍历对应二叉树的(　　)

二维数组M,行下标取值范围为0~8,列下标取值范围为1~10,若按行优先存储时,元素M[8][5]的存储地址为ar,则按列优先存储时，地址ar存储的数组元素应(　　)

用不带头结点的单链表存储队列，在进行删除运算时(　　)

某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下列存储结构中，最节省运算时间的是(　　)

下列选项中，属于顺序存储结构优点的是(　　)

下列选项中，属于逻辑结构的是(　　)

数据结构不包含的内容是(　　)