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⏌