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