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

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

1、（）是数据的最小单位。

A、数据元素

B、数据项

C、数据对象

D、数据结构

2、在长度为n顺序实现的线性表的第i（1≤i≤n）个位置删除一个元素，需要前移（）个元素。

A、n-i+1

B、i

C、1

D、n-i

3、单链表的存储密度（ ）。

A、大于1

B、等于1

C、小于1

D、不能确定

4、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）。

A、O(1)

B、O(n)

C、O(m)

D、O(m+n)

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

A、栈

B、队列

C、顺序结构线性表

D、链式结构线性表

6、一个栈的输入序列为a，b，c，d，下面哪一个序列不可能是这个栈的输出序列？（）

A、b，c，d，a

B、d，c，a，b

C、a，c，b，d

D、c，d，b，a

7、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列删除两个元素，再加入一个元素后，rear和front的值分别为（）。

A、1和5

B、2和4

C、4和2

D、5和1

8、若串S=“database”，其非空子串数目为（）。

A、8

B、37

C、36

D、9

9、数组a中，每个元素a[i,j]的长度为4个字节，行下标i从0到7，列下标j从0到9，从首地址连续存放在存储器内，该数组按行优先存放时，元素a[7][4]的起始地址为（ ）。

A、a+192

B、a+188

C、a+300

D、a+296

1、试题答案：B

试题解析：

对于A，数据元素是数据的基本单位而非最小单位；对于B，数据项是数据不可分割的最小单位，因此B正确；对于C，数据对象是性质相同的数据元素的集合，是数据的一个子集而非最小单位；对于D，数据结构是相互之间存在一种或多种特定关系的数据元素的集合, 它研究的是数据的逻辑关系和数据的物理关系以及它们之间的相互关系，与题干描述不符。故本题选B。

2、试题答案：D

试题解析：

设长度为n的顺序表存储在下标为1至n的一维数组中，若删除第i个位置的元素，则需要移动第i+1至第n位置的元素，移动的元素总数为n-i，故本题选D。

3、试题答案：C

试题解析：

存储密度在计算机中是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，计算公式：存储密度=(结点数据本身所占的存储量)/(结点结构所占的存储总量)。单链表需要存储指针，因此其存储密度小于1，故本题选C

4、试题答案：C

试题解析：

将长度为n的单链表链接在长度为m的链表之后，需要将长度为m的单链表的尾结点的指针指向长度为n的单链表的头结点。根据单链表的特性，寻找单链表的尾结点需要从头开始遍历链表，因此其时间复杂度为O(m)，故本题选C。

5、试题答案：A

试题解析：

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

6、试题答案：B

试题解析：

对于A，可以经过这样的操作得到该输出序列：push(a)、push(b)、pop(b)、push(c)、pop(c)、push(d)、pop(d)、pop(a)；对于C，可以经过这样的操作得到该输出序列：push(a)、pop(a)、push(b)、push(c)、pop(c)、pop(b)、push(d)、pop(d)；对于D，可以经过这样的操作得到该输出序列：push(a)、push(b)、push(c)、pop(c)、push(d)、pop(d)、push(b)、push(a)。而对于B，若首先出栈的元素是d，则证明在d之前其余元素已入栈，且入栈的顺序为a，b，c，d，则出栈的顺序应为d，c，b，a，故本题选B。

7、试题答案：A

试题解析：

循环队列进行删除操作时，需要更新头指针，即front==(front+1)%maxsize，因此删除两个元素后front由3指向5。循环队列进行插入操作时，需要更新尾指针，即rear==(rear+1)%maxsize，因此加入一个元素后rear由0指向1，故本题选A。

8、试题答案：C

试题解析：

串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。在本题中，串S的长度为1的子串有8个，长度为2的子串有7个，长度为3的子串有6个，…，长度为8的子串有1个，因此子串的个数=8+7+6+5+4+3+2+1=36，故本题选C。

9、试题答案：D

试题解析：

画出上述二维数组a的矩阵如下所示（用绿色标记待存储元素，用红色标记a[7][4]）：

由上述矩阵可知，a[7][4]之前需要存储的元素个数=7*10+4=74。每个元素4个字节，占用的总的存储空间=74*4=296。因此，a[7][4]的起始地址为a+296，故本题选D。