数据结构自考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)算法求最小生成树,请按被选中的次序写出最小生成树上各条边的顶点和权值。

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