​数据结构自考2017年4月真题

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

本试卷为单选题型，填空题，算法阅读，算法设计等题型。

一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

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

A.算法解决的只能是数值计算问题
B.同一问题可以有多种不同算法
C.算法的每一步操作都必须明确无歧义
D.算法必须在执行有限步后结束

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

A.顺序存储时不一定相邻，链式存储时一定相邻
B.顺序存储时不一定相邻，链式存储时也不一定相邻
C.顺序存储时一定相邻，链式存储时也一定相邻
D.顺序存储时一定相邻，链式存储时不一定相邻

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

A.p==NULL
B.head==NULL
C.p==head
D.head !=p

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

A.2,3,5,1,4
B.4,2,1,3,5
C.3,4,1,2,5
D.3,4,2,1,5

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

A.10
B.12
C.14
D.15

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

A.b
B.d
C.( c, d)
D.((c,d))

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

A.38
B.39
C.40
D.41

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

A.a
B.b
C.c
D.e

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

A.n-1
B.n
C.n*(n+1)/2
D.n*(n+1)

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

A.a,b,c,e,f,d
B.a,c,b,e,f,d
C.a,c,e,b,d,f
D.a,e,b,c,f,d

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

A.堆排序
B.直接选择排序
C.冒泡排序
D.希尔排序

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

A.快速排序
B.直接选择排序
C.冒泡排序
D.直接插入排序

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

A.前序遍历
B.中序遍历
C.后序遍历
D.按层遍历

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

A.1
B.2
C.3
D.4

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

A.53 90
B.53
C.90
D.65

二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。

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

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

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

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

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

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

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

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

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

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

三、解答题(本大题共4小题，每小题5分，共20分)

21.对题26图所示的带权无向图G,试回答以下问题。(1)画出G的最小生成树;(2)若用克鲁斯卡尔( Kruskal)算法求最小生成树,请按被选中的次序写出最小生成树上各条边的顶点和权值。

22.已知散列表的长度为11,散列函数为H(key)=key%11,散列表的当前状态如下:现要插入关键字38,回答下列问题(1)若用线性探查法解决冲突,则38所在位置的下标是什么?(2)若用二次探查法解决冲突,则38所在位置的下标是什么?(3)以上两种方法中,各需要多少次擦查次数?

23.试回答下列关于拓扑排序算法的问题。(1)算法中利用一个栈保存入度为0的顶点,其目的是什么?(2)若在算法中将队列改为栈,相应地将入、出栈及判栈空操作改为入、出队列和判队列空操作,其他部分不变,是否依然能够得到拓扑排序的正确结果?

24.考虑用快速排序、堆排序和归并排序3种排序方法对数据序列进行排序,针对下列不同情况,宜分别选择哪种排序方法?(1)使用尽量少的存储空间;(2)要求排序结果是稳定的;(3)快速找出数据序列中关键字值较大的若干项。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

31.设链表中结点类型定义如下,阅读程序,回答下列问题。typedef int DataType;typedef struct node{       DataType data;        struct node *next;} RecType, LinkList;    int f30( LinkList *head)  {       if( head ==NULL ) return 0;       else return max(head-> data,f30(head->next);    //max(ab)返回ab中的较大者}(1)若链表L={2,12,16,88,5,10},写出调用f30(L)的输出结果;(2)函数f30的功能是什么?

32.函数f31的功能是逆序输出链表中所有结点的数据域值。请在空白处填充适当的内容,使其完成指定功能。void f31 LinkList *head){      if( head==NULL ) ___(1)___;      else  {      f31(head->next);          printf("%d",___(2)___);   }}

33.函数f32的功能是统计N个顶点的有向图中边的数量,有向图用邻接矩阵A表示。阅读程序,并在空白处填入适当内容,使其完成指定功能。int f32(intAIN)      {    int i, j;          int sum=0;          for(i=0; i<N;  (3) )          for( ___(2)___ ; j <N;j++)          if( ___(3)___ ) sum++;         return sun;}

34.已知二叉树的二叉链表类型定义如下: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)___;}

五、算法设计题(本大题共1小题，共10分)

41.已知二叉树的结点类型定义如下:typedef struct node{     int data;       struct node *lchild, *rchild;}BinTNode;typedef BinTNode BinTree;请编写函数 SearchXNum,计算任意二叉树T中其数据域的值大于或等于x的结点的个数并返回该值。函数原型如下: int SearchXNum( Bintree *T, int x);//返回二叉树T中数据域的值大于或等于x的结点的个数