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

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

1、下面程序段的时间复杂度是（ ）。i=1; while(i<=n) i=i*3;

A、O(n)

B、O(nlog(n))

C、O(log(n))

D、O(log₃n)

2、在n个元素的顺序表中插入或删除一个元素，需要平均移动表中（ ）个元素。

A、(n)

B、(n/2)

C、(n²)

D、(1)

3、设循环队列中数组的下标范围是0，...，m-1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（ ）。

A、(rear-front+1)%(m+1)

B、(rear-front+m+1)%m

C、rear-front

D、rear-front+1

4、设计一个十进制转换为八进制的算法，采用（ ）数据结构最佳。

A、栈

B、队列

C、顺序结构线性表

D、链式结构线性表

5、若某个栈的输入序列为1，2，3，...，n，输出序列的第一个元素为n，则第i个输出元素为（ ）。

A、i

B、n-i

C、n-i+1

D、哪个元素无所谓

6、六个元素按6，5，4，3，2，1的顺序进栈，下列哪个出栈序列是错误的（ ）。

A、5 4 3 6 1 2

B、4 5 3 1 2 6

C、3 4 6 5 2 1

D、2 3 4 1 5 6

7、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）二叉树。

A、空或只有一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子

8、高度为k的完全二叉树至少有（ ）个结点（空树高度为0）。

A、2^k-1

B、2^k

C、2^k-1

D、k

9、设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中至多有（ ）个结点。

A、2^h-1

B、2^h-1

C、2^h+1

D、2^h+1-1

10、数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行优先存放时，元素A[8][5]的起始地址为（ ）。

A、SA+141

B、SA+222

C、SA+144

D、SA+225