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

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

1、算法的计算量的大小称为计算的（ ）。

A、效率

B、复杂度

C、现实性

D、难度

2、从逻辑上可以把数据结构分为（ ）两大类。

A、动态结构、静态结构

B、顺序结构、链式结构

C、线性结构、非线性结构

D、初等结构、构造型结构

3、以下数据结构中，（ ）是非线性数据结构。

A、树

B、字符串

C、队

D、栈

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

A、都是先进先出

B、都是先进后出

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

D、没有共同点

5、设栈的输入序列是1，2，3，4，则（ ）不可能是其出栈序列。

A、1，2，4，3

B、2，1，3，4

C、1，4，3，2

D、4，3，1，2

6、假设以行序为主序存储二维数组A=array[1.. 100，1.. 100]，设每个数据元素占2个存储单元，基地址为10，则L0C[5，5]=（ ）。

A、808

B、818

C、1010

D、1020

7、对稀疏矩阵进行压缩存储目的是（ ）。

A、便于进行矩阵运算

B、便于输入和输出

C、节省存储空间

D、降低运算的时间复杂度

8、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（ ）。

A、-A+B*C/DE

B、-A+B*CD/E

C、-+*ABC/DE

D、-+A*BC/DE

1、试题答案：B

试题解析：

【考点】本题考查算法的相关名词概念。 

【解析】对于A，算法效率是算法在计算机上运行时所消耗的时间度量，与题干所述不是同一个概念，因此A错误。算法的复杂度包括算法的时间复杂度和空间复杂度，前者衡量算法的执行所消耗的时间，后者衡量算法执行所消耗的空间，算法的计算量大小称为算法的复杂度（性），因此B选项正确。对于C，算法并没有普及现实性的概念，因此C选项错误。对于D，算法的难度并没有一个明确的定义，一般情况下用算法的复杂度来衡量，B选项比D选项的表述更准确且更常规，故本题选B。

2、试题答案：C

试题解析：

【考点】本题考查数据的逻辑结构的分类。 

【解析】数据的逻辑结构是对数据之间关系的描述。对于A，动态结构和静态结构由实现方式决定的，与逻辑结构无关，因此A错误。对于B，顺序结构和链式结构均属于数据的存储结构，因此B错误。对于C，逻辑结构通常包括四种基本类型，分别为线性结构、树形结构、图状或网状结构、纯集合结构，后三者统称为非线性结构，因此C正确。对于D，初等结构和构造性型结构不属于逻辑结构，因此D错误，故本题选C。

3、试题答案：A

试题解析：

【考点】本题考查数据结构的逻辑结构。 

【解析】数据结构的逻辑结构通常包括四种基本类型，分别为线性结构、树形结构、图状或网状结构、纯集合结构，后三者统称为非线性结构。对于A，树是树形结构，具有“一对多”的特点，而B、C、D选项涉及的字符串、队、栈均为线性结构，具有“一对一”的线性特点，故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查栈和队列的特点。

【解析】栈具有“先进后出”的特性，而队列具有“先进先出”的特性，因此A和B均错误。栈和队列是限定的线性表，栈只能从一端进入从该端删除，而队列从一端进入从另一端删除，这两种数据结构只允许在端点除插入和删除元素，因此C正确D错误。故本题选C。

5、试题答案：D

试题解析：

【考点】本题考查栈的基本操作。 

【解析】对于A，若栈执行这样的操作：push(1)、pop(1)、push(2)、pop(2)、push(3)、push(4)、pop(4)、pop(3)，则其出栈序列正如A所示，因此A正确。对于B，若栈执行这样的操作：push(1)、push(2)、pop(2)、pop(1)、push(3)、pop(3)、push(4)、pop(4)，则其出栈序列正如B所示，因此B正确。对于C，若栈执行这样的操作：push(1)、pop(1)、push(2)、push(3)、push(4)、pop(4)、pop(3)、pop(2)，则其出栈序列正如C所示，因此C正确。对于D，若第一个出栈的关键字为4，则证明栈的基本操作操作为：push(1)、push(2)、push(3)、push(4)、pop(4)、pop(3)、pop(2)、pop(1)，此时的出栈序列应当为4,3,2,1，因此D错误。故本题选D。

6、试题答案：B

试题解析：

【考点】本题考查二维数组的存储。 

【解析】本题中数组的行和列均从1开始，A[5，5]之前的元素个数=4*100+4=404。每个数据元素占2个存储单元，则A[5，5]之前的元素占据的存储单元=404*2=808。基地址为10，则LOC[5,5]=10+808=818。故本题选B。

7、试题答案：C

试题解析：

【考点】本题考查矩阵的压缩存储。 

【解析】稀疏矩阵是指矩阵中非零元素<=50%，且分布无规律的矩阵。若采用二维数组存储，空间浪费较大，因此对稀疏矩阵压缩存储（仅存储非零元素）会节省存储空间，而A、B、D的操作并非采用压缩存储的主要目的，故本题选C。

8、试题答案：D

试题解析：

【考点】本题考查算术表达式的相互转换。

【解析】根据后缀表达式对中缀表达式加括号以区别运算的先后关系：((A+(B*C))-(D/E))。将运算符放在括号前面，-(+(A*(BC))/(DE))，将括号去掉以后的序列为-+A*BC/DE，故本题选D。