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

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

1、希尔排序的组内排序采用的是（  ）。

A、 直接插入排序

B、 折半插入排序

C、 快速排序

D、 归并排序

2、设顺序队列的容量为MaxSize，其头指针为front，尾指针为rear，空队列的条件为（ ）。

A、front=rear

B、front=MaxSize

C、front+1=rear

D、rear=0

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

A、逻辑

B、逻辑和存储

C、物理

D、线性

4、数据结构中数据元素之间的逻辑关系被称为（ ）。

A、数据的存储结构

B、 数据的基本操作

C、程序的算法

D、数据的逻辑结构

5、下面程序的时间复杂度为（ ）。for(int i=0; i<m; i++) for(int j=0; j<n; j++) A.O(n2) B.O(m*n) C.O(m2) D.O(m+n)a[i][j]=i*j;

A、

B、

C、

D、

6、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式是（ ）。

A、单链表

B、双向链表

C、单循环链表

D、顺序表

7、用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S和X的操作序列为（ ）。

A、SXSXSSXX

B、SSSXXSXX

C、SXSSXXSX

D、SXSSXSXX

8、对于双向循环链表，在p指针所指的结点之后插入s 指针所指结点的操作应为（ ）。

A、p→right=s; s→left=p; p→right→left=s; s→right=p→right;

B、p→right=s; p→right→left=s; s→left=p; s→right=p→right;

C、s→left=p; s→right=p→right; p→right=s; p→right→left=s;

D、s→left=p; s→right=p→right; p→right→left=s; p→right=s;

9、和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A、通常不会出现栈满的情况

B、通常不会出现栈空的情况

C、插入操作更容易

D、删除操作更容易

1、试题答案：A

试题解析：

【考点】本题考查希尔排序。
【解析】希尔排序的基本思想是现将整个待排序列分割成若干子序列，对子序列分别进行插入排序，待整个序列中的记录基本有序之后，再对整个序列进行一次插入排序。希尔排序的组内排序采用的是直接插入排序。故本题选A。

2、试题答案：A

试题解析：

【考点】本题考查队列的判断条件。
【解析】为了方便起见，约定初始化建空队时，令front=rear=0。但是，当队空时，front=rear；当队满时，front=rear亦成立。因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）牺牲一个存储空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志（front指向队首元素，rear指向队尾元素的下一个元素）。即：
① 队空时：front=rear；
② 队满时：(rear+1)%maxsize=front。
综上所述，本题选A。

3、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--线索二叉树--线索二叉树的性质。
【解析】二叉树是一种逻辑结构，但线索二叉树是加上线索后的链表结构，即它是二叉树在计算机内部的一种存储结构，所以是一种物理结构。故本题选C。

4、试题答案：D

试题解析：

【考点】本题考查逻辑结构的含义。
【解析】
（1）数据的存储结构又称为物理结构，是数据的逻辑结构在计算中的表示（又称映像）。
（2）数据的基本操作即数据的运算，是施加在数据上的运算包括运算的定义和实现。
（3）程序算法是对特定问题求解过程的描述，是指令的有限序列，每条指令完成一个或多个操作。
（4）数据的逻辑结构是指数据元素之间的逻辑关系，即逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。
综上所述，本题选D。

5、试题答案：B

试题解析：

【考点】本题考查时间复杂度的计算。
【解析】外层for循环执行m次，内层for循环执行n次，所以循环体a[i][j]=i*j；总共会执行m*n。因此，该程序段的时间复杂度为O(m*n)。故本题选B。

6、试题答案：D

试题解析：

【考点】本题考查线性表的查找。
【解析】顺序表适合频繁进行查找操作的情况，可以随机存取。而单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能够快速查找第i个元素的前趋，但不能实现随机存取。因此，若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式是顺序表。故本题选D。

7、试题答案：D

试题解析：

【考点】本题考查进栈和出栈操作。
【解析】分析如下：

综上所述，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S和X的操作序列为SXSSXSXX。故本题选D。

8、试题答案：D

试题解析：

【考点】本题考查双向循环列表的插入操作。
【解析】双向循环链表中，在p指针所指的结点之后插入s 指针所指结点的操作示意图如下所示，其中：① s->left=p；② s->right=p->right；③ p->right->left=s；④ p->right=s。故本题选D。

9、试题答案：A

试题解析：

【考点】本题考查链栈的优点。
【解析】和顺序栈相比，链栈的优势是通常不会出现栈满的情况。因为顺序栈用数组实现，必须事先确定栈的大小，内存容量无法动态扩充，会出现因数组空间用光而引起溢出的问题。而链栈的空间因为是动态申请内存，一般不会出现栈满情况。故本题选A。