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

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

1、下列说法中，（ ）是不正确的。

A、数据项可由若干个数据元素构成

B、数据项是数据中不可分割的最小标识单位

C、数据可由若干个数据元素构成

D、数据元素是数据的基本单位

2、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。

A、6

B、4

C、3

D、2

3、一维数组的元素起始地址LOC[2]=1000，元素长度为5，则LOC[8]为（ ）。

A、1025

B、1030

C、1035

D、8

4、链表不具有的特点是（ ）。

A、不必事先估计存储空间

B、可随机访问任一元素

C、插入删除不需要移动元素

D、所需空间与线性表长度成正比

5、栈和队列的共同特点是（ ）。

A、只允许在端点处插入和删除元素

B、都是先进后出

C、都是先进先出

D、没有共同点

6、串的模式匹配是指（ ）。

A、判断两个串是否相等

B、找某字符在主串中第一次出现的位置

C、对两个串比较大小

D、找某子串在主串中第一次出现的第一个字符位置

7、若串S="SOFTWARE"，其子串的数目最多是（ ）。

A、35

B、36

C、37

D、38

8、设一组初始记录关键字序列为（45，80，55，40，42，85），则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。

A、40，42，45，55，80，83

B、42，40，45，80，85，88

C、42，40，45，55，80，85

D、42，40，45，85，55，80

1、试题答案：A

试题解析：

本题考查数据结构基本概念。
一个数据元素可由若干数据项组成，A说法错误。故本题选A。

2、试题答案：C

试题解析：

本题考查栈的出栈入栈操作。
首先e1、e2依次入栈，此时栈中有2个元素，随即e2出栈后依次执行入队、出队操作。接着e3、e4依次入栈，此时栈中有3个元素，随即e4、e3出栈后依次执行入队、出队操作。然后e5、e6依次入栈，此时栈中有3个元素，随即e6、e5、e1出栈后依次执行入队、出队操作。最终元素出队顺序是e2、e4、e3、e6、e5、e1。分析整个过程可知，栈中同时最多会存放3个与元素，所以栈S的容量至少应该是3。故本题选C。

3、试题答案：B

试题解析：

本题考查数组地址计算。
LOC[8]=( 8-2) *5+1000=1030。故本题选B。 

4、试题答案：B

试题解析：

本题考查链表的特点。
由于链表中各元素之间通过指针连接，元素的存储地址不一定连续， 所以不可以随机访问任一元素，一般从表头开始依次访问。故本题选B。

5、试题答案：A

试题解析：

本题考查栈和队列的共同特点。
栈的特点是“先进后出”，只能在栈顶插入和删除元素；队列的特点是“先进先出”，在队头删除元素、队尾插入元素，所以栈和队列的共同点是都只能在端点处进行元素操作。故本题选A。

6、试题答案：D

试题解析：

本题考查串的模式匹配的含义。
串的模式匹配是在主串中找到与模式串相同的子串，并返回其所在位置。

7、试题答案：C

试题解析：

本题考查子串的个数。
设串s的长度为n，则s的子串个数为n(n+1)/2+1。由题干可知串长为8，则其子串最多为8*9/2+1=37。故本题选C。

8、试题答案：C

试题解析：

本题考查快速排序。
在快速排序中，附设两个指针 left 和 right，它们初始分别指向待排序序列的左端和右端，此外还要附设一个基准（由题意知本题的基准为45）。

首先从 right 所指的位置从右向左搜索找到第一个小于基准的元素为42，然后将其记录在基准元素所在的位置。

接着从 left 所指的位置从左向右搜索找到第一个大于基准的元素为80，然后将其记录在 right 所指向的位置。

然后再从 right 所指向的位置继续从右向左搜索找到第一个小于基准的元素为40，然后将其记录在 left 所指向的位置。

重复上述步骤，直至搜索过程中出现了 left == right ，则说明一趟快速排序结束。此时将基准记录在left和right共同指向的位置即可。所以序列（45，80，55，40，42，85）经历一趟快速排序的结果为42，40，45，55，80，85。故本题选C。