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

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

1、进行连续存储分配时，存储单元地址（ ）。

A、一定连续

B、一定不连续

C、不一定连续

D、部分连续部分不连续

2、运算实现是针对（ ）的指出运算的具体操作步骤。

A、逻辑结构

B、存储结构

C、顺序存储

D、链接存储

3、设线性表2n个元素，（ ）在单链表上实现比在顺序表上实现效率高。

A、删除所有值为x的元素

B、在最后一个元素后插入一个新元素

C、顺序输出前k个元素

D、交换第i个元素和第2n-i-1个的值（i=0，1，2，n-1）

4、假设一链表最常用的操作是在末尾插入结点和删除结点，选用（ ）最节省时间。

A、带表头结点双循环链表

B、单链环链表

C、带尾指针单循环链表

D、单链表

5、栈和队列主要区别为（ ）。

A、逻辑结构不同

B、存储结构不同

C、包含元素不同

D、插入删除操作限定不同

6、用链式存储方式的队列操作删除元素需要（ ）。

A、仅修改头指针

B、仅修改尾指针

C、头尾指针都必定修改

D、头尾指针可能修改

7、线索二叉树是一种（ ）结构。

A、逻辑

B、物理

C、线性

D、逻辑和存储

8、先序遍历为A，B，C，后序遍历为C，B，A二叉树共（ ）。

A、5

B、4

C、3

D、2

9、含有20个结点二叉平衡树的最大深度为（ ）。

A、4

B、5

C、6

D、7

1、试题答案：A

试题解析：

顺序存储，即连续存储是指用一段地址连续地存储单元，存储相邻数据元素，或把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现（逻辑与物理统一），要求内存中可用的存储单元的地址必须是连续的。故本题选A。

2、试题答案：B

试题解析：

数据的运算是施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。故本题选B。

3、试题答案：A

试题解析：

无论是顺序表还是单链表，查找所有值为x的元素一般是从头遍历，两个效率差不多。但是删除值为x的元素时，对于单链表而言，只需要修改指针指向即可；对于顺序表而言，可能需要移动大量元素。因此，删除所有值为x的元素在单链表上实现比在顺序表上实现效率高。故本题选A。

4、试题答案：A

试题解析：

在链表末尾插入结点和删除结点时，需要修改其相邻结点的指针域。对于带表头结点双循环链表而言，查找末尾元素以及其前驱结点都很方便，效率更高。因此，若一链表最常用的操作是在末尾插入结点和删除结点，选用带表头结点双循环链表最节省时间。故本题选A。

5、试题答案：D

试题解析：

A：栈和队列的逻辑结构相同，都属于线性结构。
B：栈和队列都可以顺序存储和链式存储。
C：栈和队列包含的元素可以相同，也可以不同。
D：栈和队列都属于操作受限的数据结构，其主要区别是栈的插入删除操作仅限于栈顶这一端，队列的插入删除操作限于队头和队尾这两端。
综上所述，本题选D。

6、试题答案：D

试题解析：

在链队中删除一个元素时，需要将队头指针向后移动一个位置，即指向要删除元素的下一个邻接元素。删除最后一个元素时，不仅需要修改队头指针，还要修改队尾指针让其指向队头指针，这样使得队尾指针也指向空位置。因此，用链式存储方式的队列操作删除元素时，头尾指针都可能需要修改。故本题选D。

7、试题答案：B

试题解析：

存储结构是数据的逻辑结构在计算机中的实现，而线索二叉树属于存储结构。故本题选B。

8、试题答案：B

试题解析：

一棵非空的二叉树的先序遍历序列和后序遍历序列正好相反，则叶子结点除外，该子树每个结点有且仅有一个孩子（不论左孩子还是右孩子），既然每个结点有且仅有一个孩子。先序遍历为A，B，C，后序遍历为C，B，A二叉树共4种情况，如下所示。综上所述，本题选B。

9、试题答案：C

试题解析：

构成深度为h的平衡二叉树所需的最小结点数如下，由此知构造一棵深度为6的平衡二叉树至少需要20个结点，所以含有20个结点二叉平衡树的最大深度为6。故本题选C。