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

已知二叉树的结点类型定义如下:

typedef struct node

{    int data;

       struct node *lchild, *rchild;

}BinTNode;

typedef BinTNode BinTree;

请编写函数 SearchXNum,计算任意二叉树T中其数据域的值大于或等于x的结点的个数并返回该值。函数原型如下:int SearchXNum( Bintree *T, int x);//返回二叉树T中数据域的值大于或等于x的结点的个数

函数f31的功能是逆序输出链表中所有结点的数据域值。请在空白处填充适当的内容,使其完成指定功能。

void f31 LinkList *head)

{     if( head==NULL ) ___(1)___;

     else

 {     f31(head->next);

         printf("%d",___(2)___);

  }

}

函数f32的功能是统计N个顶点的有向图中边的数量,有向图用邻接矩阵A表示。阅读程序,并在空白处填入适当内容,使其完成指定功能。

int f32(intAIN)

     {   int i, j;

         int sum=0;

         for(i=0; i

         for( ___(2)___ ; j

         if( ___(3)___ ) sum++;

        return sun;

}

已知二叉树的二叉链表类型定义如下:

typedef struct node

{  char data;

   struct node * lchild, *rchild;

 } BiTNode;

 typedef BiNode BiTree;

以下程序为求二叉树深度的递归算法,请填空完普之。

int depth( Bitree *bt)       /*bt为指向根结点的指针*/

 { int h1=0, hr =0;

   if(___(1)___) return (0);

     h1=depth( bt->lchild);

      hr= depth (bt->rchild);

     if(___(2)___) return (h1+1);

     else ___(3)___;

}

考虑用快速排序、堆排序和归并排序3种排序方法对数据序列进行排序,针对下列不同情况,宜分别选择哪种排序方法?

(1)使用尽量少的存储空间;

(2)要求排序结果是稳定的;

(3)快速找出数据序列中关键字值较大的若干项。

设链表中结点类型定义如下,阅读程序,回答下列问题。

typedef int DataType;

typedef struct node

{      DataType data;

       struct node *next;

} RecType, LinkList;

   int f30( LinkList *head)

 {      if( head ==NULL ) return 0;

      elsereturn max(head->data,f30(head->next);   //max(ab)返回ab中的较大者

}

(1)若链表L={2,12,16,88,5,10},写出调用f30(L)的输出结果;

(2)函数f30的功能是什么?

已知散列表的长度为11,散列函数为H(key)=key%11,散列表的当前状态如下:

现要插入关键字38,回答下列问题

(1)若用线性探查法解决冲突,则38所在位置的下标是什么?

(2)若用二次探查法解决冲突,则38所在位置的下标是什么?

(3)以上两种方法中,各需要多少次擦查次数?

试回答下列关于拓扑排序算法的问题。

(1)算法中利用一个栈保存入度为0的顶点,其目的是什么?

(2)若在算法中将队列改为栈,相应地将入、出栈及判栈空操作改为入、出队列和判队列空操作,其他部分不变,是否依然能够得到拓扑排序的正确结果?

对题26图所示的带权无向图G,试回答以下问题。

(1)画出G的最小生成树;

(2)若用克鲁斯卡尔( Kruskal)算法求最小生成树,请按被选中的次序写出最小生成树上各条边的顶点和权值。

二分查找的速度快效率高,但是它要求表按关键字有序并且________。

除了问题的规模和分量个数之外,还有________是影响基数排序时间复杂度的主要因素。

连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的________树。

用邻接表存储含n个顶点e条边的有向无环图G，对G进行拓扑排序，算法的时间复杂度为________。

在给定n个叶子结点权值且不含度数为1的结点的所有二叉树中,其________最小的二叉树称为哈夫曼树。

若某二叉树T的前序遍历序列是A,B,C,D,中序遍历序列是B,A,D,C,则T的后序遍历序列是________。

对任何一棵二叉树T,若其叶子结点数为n0, 度数为2的结点数为, 则等于________。

若中缀表达式为9+(6-2)*8,则相应的后缀表达式是________。

一个需要频繁增删的线性表宜选择________存储结构。

在下面3阶B树中插入关键字65后,其根结点内的关键字是(　　)

散列方法的基本思想是根据元素的关键字直接计算出该元素的________。

设一组记录的关键字为{12,22,10,20,88,27,54,11},散列函数为H(key)=key%11,用拉链法解决冲突,则散列地址为0的链中结点数是(　　)

下列排序算法中,比较操作的次数与待排序序列初始排列状态无关的是(　　)

若对二叉排序树进行遍历,则下列遍历方式中,其遍历结果为递增有序的是(　　)

若从顶点a开始对下图进行广度优先遍历,则不可能得到的遍历序列是(　　)

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

若图G是一个含有n个顶点的强连通有向图,则G的边数至少是(　　)

对下面的二叉树进行中序线索化后,结点f的右指针指向的结点是(　　)

若完全二叉树T包含20个终端结点,则T的结点数最多是(　　)

数组A[2][3]按行优先顺序存放,A的首地址为10。若A中每个元素占用一个存储单元,则元素A[1][2]的存储地址是(　　)

广义表((a,b),(c,d))的表尾是(　　)

设栈的入栈序列为1,2,3,4,5,经过入、出栈操作后,可能得到的出栈序列是(　　)

对带头结点的单循环链表从头结点开始遍历(head为头指针,p=head->next)。若指针p指向当前被遍历结点，则判定遍历过程结束的条件是(　　)

下列叙述中，不正确的是(　　)

下列关于栈中逻辑上相邻的两个数据元素的叙述中，正确的是(　　)