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

1、试题答案：D

试题解析：

该程序段的时间复杂度与while循环内的语句的执行次数同数量级。当循环执行1次时，i=3¹；当循环执行2次时，i=3²；…；当循环执行Tn次时，i=3^Tn。代入循环终止条件可得3^Tn>n，解得Tn>log₃n，时间复杂度应与log₃n同数量级，故本题选D。

2、试题答案：B

试题解析：

顺序表的插入操作是指在第i-1个元素和第i个元素之间插入一个数据元素，使长度为n的线性表长度变为n+1，需要将第n到i的元素向后移动一位，共需移动元素的个数为n-i+1；顺序表的删除操作是指在删除第i个元素，需要将第i+1至第n个元素依次向前移动一位，共需移动元素的个数为n-i。在一个有n个元素的顺序表中，插入一个元素平均要移动的元素个数为n/2，删除一个元素平均要移动的元素个数为（n-1）/2。故本题选B。

3、试题答案：B

试题解析：

将顺序队列首尾相接成环状空间即为循环队列。在该循环队列中，头指针front指向队首元素，rear指向队尾元素，因此元素的个数=rear-front+1，因为front的下标可能会比rear大，因此rear-front+1+m为了保证求出的数是非负数，故本题选B。

4、试题答案：A

试题解析：

栈具有“后进先出”的特点，进行进制的转换时，需要将计算得到的数逆序输出，因此可以利用栈结构。举例说明：将一个非十进制的数转换为八进制，需要将该数进行连续的除以8操作，将每一次的余数结果压入栈中，之后再将栈中的结果依次输出，这个输出的数即为所求的进制转换后的数。故本题选A。

5、试题答案：C

试题解析：

栈具有“后进先出”的特性，因此栈的基本操作为push(1)，push(2)，…，push(n-1)，push(n)，pop(n)，pop(n-1)，…，push(2)，push(1)，因此出栈的序列为n，n-1，…，1，则第i个输出元素为n-i+1，故本题选C。

6、试题答案：C

试题解析：

对于A，可以经过这样的操作得到该出栈序列：push(6)，push(5)，pop(5)，push(4)，pop(4)，push(3)，pop(3)，pop(6)，push(2)，push(1)，pop(1)，pop(2)；对于B，可以经过这样的操作得到该出栈序列：push(6)，push(5)，push(4)，pop(4)，pop(5)，push(3)，pop(3)，push(2)，push(1)，pop(1)，pop(2)，pop(6)；对于C，6在5之前进栈，则5应当在6之前出栈，因此C错误；对于D，可以经过这样的操作得到该出栈序列：push(6)，push(5)，push(4)，push(3)，push(2)，pop(2)，pop(3)，pop(4)，push(1)，pop(1)，pop(5)，pop(6)；故本题选C。

7、试题答案：B

试题解析：

先序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。对于A，若树为空或只有一个结点时，二叉树的先序序列和后序序列相同，不符合题干要求，因此A错误。对于B，若树的结构如图1所示，该树的先序序列为ABC，后序序列为CBA，符合题干要求。对于C，若树的结构如图2所示，该树的先序序列为ABC，后序序列为CBA，符合题干要求。对于D，若树的结构如图3所示，该树的先序序列为ABC，后序序列为CBA，符合题干要求。B的表述包含C和D的情况，故本题选B。

8、试题答案：A

试题解析：

当二叉树的第i至第k-1层为满二叉树且第k层仅含有1个结点时树的结点总数最少。满二叉树第i层的结点个数=2^i-1个，高度为k的二叉树的结点总数=2⁰+2¹+2²+…+2^k-2+1=2^k-1，故本题选A。

9、试题答案：A

试题解析：

当这棵二叉树是一棵满二叉树时，二叉树上的结点数最多，根据二叉树的性质可知，深度为h的满二叉树有2^h-1个结点，故本题选A。

10、试题答案：B

试题解析：

LOC(A[8][5])=SA+((8-1)*10+(5-1))*3=SA+222，故本题选B。