2018年数据结构考研真题答案及解析（二）

本文提供2018年数据结构考研真题答案及解析，以下为具体内容

1、任何一棵二叉树T， 如果度为1的结点数为2，度为0结点数为11，其分支数为（ ）。

A、 23

B、22

C、24

D、21

2、深度为k的二叉树至多有（ ）个结点（k>=1）。

A、2k

B、2k-1

C、2k+1

D、2k-1

3、已知一棵二叉树结点的中序序列为BDCEAFHG， 后序序列为DECBHGFA， 则结点的先序序列为（ ）。

A、ABCDEFGH

B、DGBFHCA

C、DECBGFAH

D、CAFHGDB

4、在有向图的逆邻接表存储结构中，顶点v在表结点中出现的次数是（ ）。

A、顶点V的度

B、顶点V的出度

C、顶点V的入度

D、依附于顶点V的边数

5、顺序栈s的GetTop（s,e）操作是用e返回s的栈顶元素，则下列（ ）是正确的操作。

A、e=*(s.top)

B、e=*(s.top-1)

C、e=*(--s.top)

D、e=s.top-1

6、若线性表最常用的操作是存取第i个元素及其前趋的值， 则采用（ ）存储方式节省时间。

A、单链表

B、双链表

C、单循环链表

D、顺序表

7、在一棵非空m阶的B-树上，除根之外的所有非终端结点（ ）。

A、至少有⎿m/2⏌棵子树

B、至多有⎿m/2⏌棵子树

C、至少有⎾m/2⏋棵子树

D、至多有⎾m/2⏋棵子树

8、若用单链表来表示队列，最适合队列操作的是（ ）。

A、带尾指针的非循环队列

B、带尾指针的循环链表

C、带头指针的非循环链表

D、带头指针的循环链表

1、试题答案：B

试题解析：

本题考查二叉树的性质。
由于二叉树中每增加1个度为2的结点，必然要增加2个度为0的结点，，同时减少1个度为0的结点，因此每增加1个度为2的结点，增加1个度为0的结点，同时根结点的度为0，因此n2=n0+1，即在本题中n2=10。度为2的结点有两个分支，度为1的结点有1个分支，因此总共有分支10*2+2=22。故本题选B。

2、试题答案：D

试题解析：

本题考查满二叉树的性质。
当这棵二叉树为满二叉树时，其结点数最多。对于一个满二叉树，第i层的结点数为2i-1，因此k层满二叉树总的结点数sn=20+21+……+2k-1=2k-1。故本题选D。

3、试题答案：A

试题解析：

本题考查二叉树的遍历
后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。中序遍历二叉树先遍历左子树，再访问根结点，最后遍历右子树。前序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。根据中序和后序遍历确定该二叉树的结构如下图所示：


对该二叉树进行先序遍历，得到其序列为：ABCDEFGH。故本题选A。

4、试题答案：B

试题解析：

本题考查图的存储。
逆邻接表第i个单链表中结点的个数为顶点Vi的入度；而Vi在整个逆邻接表中出现的次数则表示顶点Vi的出度。因此B正确C错误。而有向图中，顶点的度=入度+出度，因此A错误。对于D，依附于顶点V的边数实际上也是顶点V的度，因此D错误。故本题选B。

5、试题答案：B

试题解析：

本题考查栈的基本操作。
本题中用e返回栈顶元素，因此s.top为栈顶指针，s.top-1为栈顶元素的指针，*（s.top-1）即为指针指向的元素。若删除栈顶元素，指针下移，e=*（--s.top）。故本题选B。

6、试题答案：D

试题解析：

本题考查线性表的基本操作。
链表是非随机存取结构，因此链表访问第i个结点需要遍历整个链表，其时间复杂度为O（n），因此A、B、C这三个链式结构均无法实现常数级元素的访问。对于D，顺序表存取第i个元素的值其时间复杂度为O（1），查找其前驱的值，只需要对下角标i-1，再读取其值即可，时间复杂度为O（1）。故本题选D。

7、试题答案：C

试题解析：

本题考查B-树的定义。
一棵m阶的B-树或者为空树，或者具有这样的特性：（1）树中每个结点至多有m棵子树；（2）除根结点以外的所有非叶子结点至少有⎾m/2⏋棵子树，根结点是非叶子结点则至少有两棵子树；故本题选C。

8、试题答案：B

试题解析：

本题考查队列的基本操作。
队列的特性是只能在一端插入在另一端删除。A选项只能在尾删除，不能插入；B选项可以插入和删除，且时间复杂度为O（1）；C选项插入的时间复杂度为O（1），但删除时需要遍历整个链表，时间复杂度为O（n）；D选项与C同理。故本题选B。