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

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

1、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。

A、O(1)

B、O(n)

C、O(n²)

D、O(nlogn)

2、下列排序算法中，（ ）是稳定的。

A、插入、希尔

B、冒泡、快速

C、选择、堆排序

D、基数、归并

3、循环队列是空队列的条件是（ ）。

A、(Q->rear+1)%maxsize==Q->front

B、Q->rear==Q->front

C、Q->rear==0

D、Q->front==0

4、有一个有序表{1，3，9，32，41，45，62，75，77，82，95，100}， 当折半查找值为82的元素时，（ ）次比较后查找成功。

A、1

B、2

C、4

D、8

5、表达式aX(b+c)-d的前缀表达式是（ ）。

A、abcdX+-

B、abc+X d-

C、abcX +d-

D、-X a+bcd

6、深度为5的二叉树至多有（ ）个结点。

A、16

B、32

C、31

D、10

7、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。 与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。

A、M1

B、M1+M2

C、M3

D、M2+M3

8、具有n个节点的完全二叉树的深度为（ ）。

A、⎾log₂(n+1)⏋-1

B、log₂n+1

C、log₂n

D、⎿log₂n⏌

1、试题答案：B

试题解析：

【考点】本题考查单链表的插入操作。 

【解析】本题的存储结构是链表，因此寻找插入的新结点的位置时需要遍历链表寻找结点的位置，该操作的时间复杂度为O(n)。在当前位置插入结点的操作的时间复杂度为O(1)。综合时间复杂度为O(n)，故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查排序算法的稳定性。 

【解析】排序算法的稳定性是指若排序后的序列不改变原序列中相同关键字的相对位置，则称为稳定性排序，否则为不稳定性排序。对于A，希尔排序是不稳定排序，因此A错误；对于B，快速排序是不稳定排序，因此B错误；对于C，选择排序和堆排序均为不稳定排序，因此C错误；对于D，基数排序和归并排序均为稳定性排序，因此D正确，故本题选D。

3、试题答案：B

试题解析：

【考点】本题考查循环队列的判断条件。 

【解析】将顺序队列首尾相接成环状空间，在循环队列中，队头指针指向头元素，队尾指针指向尾元素的下一个位置。若循环队列中存放n个元素，则rear==front，此时无法判断是队空的条件还是队满的条件。为了区分这两者，规定循环队列中当元素个数为n-1个时，判定队列已满。队列已满的条件为队头指针front在队尾指针rear的下一个位置上，因此最大容量为s的循环队列，队满条件为（rear+1）%s==front；队空条件为rear==front。故本题选B。

4、试题答案：C

试题解析：

【考点】本题考查折半查找的应用。 

【解析】mid=(low+high)/2=(0+11)/2=5。和关键字45比较，比45大。mid=(6+11)/2=8，和关键字77做比较，比77大。mid=(9+11)/2=10，和95做比较，比95大。mid=(9+9)/2=9，和82做比较，相等，查找成功。一共比较了4次，故本题选C。

5、试题答案：D

试题解析：

【考点】本题考查算术表达式的相互转换。 

【解析】题干中的表达式为中缀表达式，中缀表达式转为前缀表达式的步骤为三步，① 在中缀表达式的每一步加上括号，表达式为((aX(b+c))-d)；② 将符号移到括号之前，-(X(a+(bc))d)；③ 去掉括号，表达式为-Xa+bcd。因此转换后的前缀表达式即为-Xa+bcd。故本题选D。

6、试题答案：C

试题解析：

【考点】本题考查二叉树的性质。

 【解析】深度为5的二叉树结点个数最多的形态即为满二叉树的形态，满二叉树第i层有2^i-1个结点，总的结点个数=2^k-1=2⁵-1=31，故本题选C。

7、试题答案：D

试题解析：

【考点】本题考查森林转换为二叉树。 

【解析】森林转为二叉树的步骤如下：
① 将每棵树转为二叉树；② 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。因此，最后得到的二叉树的根节点即为第一棵二叉树的根节点，第一棵树其余结点为二叉树的左孩子结点，其余所有树为二叉树的右孩子结点。故本题选D。

8、试题答案：B

试题解析：

【考点】本题考查完全二叉树的深度。 

【解析】具有n个结点的完全二叉树的深度为⎿log₂n⏌+1或⎾log₂(n+1)⏋。其推导过程为：由二叉树的性质可知，在二叉树的第i层上至多有2^i-1个结点。因此深度为k的完全二叉树，其结点个数的范围为2^k-1<=n<2^k。对该式取对数可得 k-1<=log₂n<k，因为k是整数，因此k=⎿log₂n⏌+1。由于选项中没有这个答案，因此选择与该答案最近似的选项，故本题选B。