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

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

1、线性表（a1，a2，…，an）采用静态链表存储时，访问第i位置元索的时间复杂度为（ ）。

A、O（n²）

B、O（n）

C、O（i）

D、O（1）

2、设深度为k的二叉树上只有度为0和度为2的结点则这类二叉树上所含结点总数最少（ ）个。

A、k+1

B、2k

C、2k-1

D、2k+1

3、设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（ ）。

A、21

B、23

C、41

D、62

4、如下陈述中正确的是（  ）。

A、串是一种特殊的线性表

B、串的长度必须大于零

C、串中元素只能是字母

D、空串是由空格组成的串

5、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。

A、存储结构

B、存储实现

C、逻辑结构

D、运算实现

6、除了（  ），其它任何指针都不能在算法中作为常量出现。

A、头指针

B、尾指针

C、指针型变量

D、空指针

7、稀疏矩阵的压缩存储方法是只存储（  ）。

A、非零元素

B、三元组（i，j，a_i,j）

C、ai,j

D、i，j

8、设rear是指向非空带头结点的循环单链表的尾指针，delete是释放结点的空间，则删除表中第一个元素结点的操作可表示为（ ）。

A、p=rear; rear=rear- >next; delete p;

B、rear=rear->next; delete rear;

C、p=rear->next->next; rear->next->next=p->next; delete p;

D、rear=rear->next->next; delete rear;

9、对广义表L=（a，（b，c）），进行Tail （L）操作后的结果为（  ）。

A、c

B、b，c

C、（b，c）

D、（（b， c））

10、若元素A、B、C、D、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（  ）。

A、dcebfa

B、cbdaef

C、bcaefd

D、afedcb

1、试题答案：B

试题解析：

【考点】本题考查链表的基本操作的时间复杂度。
【解析】静态链表查找第i位置的元素时需要从链表头开始遍历直至找到第i位置元素，其时间复杂度为O（n），因此B正确A和D错误。同时需要注意，本题问的是时间复杂度而不是所花费的时间，C不是时间复杂度的正确表示。大O表示法表示的是问题复杂度的上界，因此C错误。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查二叉树的性质。
【解析】由题干可知，该二叉树的结点不存在单分支，当所含结点最少时，除第1层以外的其余层的结点数均为2，总的结点数=1+2*（k-1）=2*k+1，故本题选D。

3、试题答案：B

试题解析：

【考点】本题考查索引查找。
【解析】题干中已经说明了按顺序查找块，一共有3块，则查找分块的平均查找长度为2。一共123个元素，分了3块，则每块41个元素。块内采用顺序查找，在块内查找的平均查找长度=（1+2+3+…+41）/41=21。因此该索引表查找成功时的平均查找长度=23。故本题选B。

4、试题答案：A

试题解析：

【考点】本题考查串的性质。
【解析】对于A，串是由一个或多个字符组成的有限序列，串是限定的线性表，因此A正确。对于B，存在空串，其长度为0，因此B错误。对于C，串的元素还可以是空格等字符，并非只能是字母，因此C错误。对于D，空串是不含任何字符的串，而空格是一个字符，因此D错误。故本题选A。

5、试题答案：C

试题解析：

【考点】本题考查数据的逻辑结构。
【解析】数据的存储和运算与数据的形式有关，如double型数据在内存中占8个字节，而int型数据在内存中占2个字节，因此A和B错误。数据运算时，相同的数据类型的元素之间可以运算，否则数据类型需要转换，因此D错误。数据的逻辑结构关注元素之间的逻辑关系，与数据元素本身无关，故本题选C。

6、试题答案：D

试题解析：

【考点】本题考查指针的用法。
【解析】在C语言中，任何类型的两个空指针都保证相等。预处理器宏NULL被定义为实现定义的空指针常量，因此D正确。链表中第一个结点的存储位置叫做头指针，尾指针是相对于头指针而言的，形式与头指针相同，内容指向链表的最后一个结点。两者都对应存储空间且其中的值能被改变，故不能作为常量出现，因此A和B错误。存放地址的变量称为指针变量，具有存储空间且值能被改变，故不能作为常量出现，因此C错误。故本题选D。

7、试题答案：A

试题解析：

【考点】本题考查稀疏矩阵的压缩存储。
【解析】稀疏矩阵中非零元素的个数少于零元素个数，因此采用压缩存储时只存储非零元素。而B选项是稀疏矩阵的一种存储方式，即三元组存储，因此B错误。选项C描述的是矩阵的中任意元素，而实际上稀疏矩阵不需要存储零元素，因此C错误。选项D中的i、j分别指行和列，因此D错误，故本题选A。

8、试题答案：C

试题解析：

【考点】本题考查单链表的删除操作。
【解析】对于A，rear->next指向的是头结点，A删除的是头结点而不是第一个元素结点，因此A错误。对于B，删除的也是头结点。对于C，rear->next头结点，rear->next->next是第一个元素结点，因此C正确。对于D，rear指向的是尾指针，应该再设一个指针指向第一个元素，而不是移动尾指针，因此D错误。故本题选C。

9、试题答案：D

试题解析：

【考点】本题考查广义表的基本操作。
【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。A和C不是一个表的形式，因此A和C错误。而C选项（b，c）整体是广义表的表尾部分，而取表尾操作取出来后是表的形式，应该在表尾部分加一个括号，因此C错误。故本题选D。

10、试题答案：D

试题解析：