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

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

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

A、数据项

B、数据类型

C、数据元素

D、数据变量

2、栈的插入和删除操作在（ ）进行。

A、栈顶

B、栈底

C、任意位置

D、指定位置

3、对线性表，在下列哪种情况下应当采用链表表示?（ ）

A、经常需要随机地存取元素

B、经常需要进行插入和删除操作

C、表中元素需要占据一片连续的存储空间

D、表中元素的个数不变

4、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）。

A、front=front+1

B、front=（front+1）%（m-1）

C、front=（front-1）%m

D、front=（front+1）%m

5、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。

A、24

B、71

C、48

D、53

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

A、808

B、818

C、1010

D、1020

7、广义表（a，（b，c），d，e）的表头为（ ）。

A、a

B、a，（b，c）

C、（a，（b，c））

D、（a）

8、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树到的序列为（ ）。

A、BADC

B、BCDA

C、CDAB

D、CBDA

9、深度为k的完全二叉树中最少有（ ）个结点。

A、2^k-1-1

B、2^k-1

C、2^k-1+1

D、2^k-1

10、设无向图G中有n个顶点e条边，则邻接表中的表头结点和表结点的个数分别为（ ）。

A、n，e

B、e，n

C、2n，e

D、n，2e

1、试题答案：A

试题解析：

【考点】本题考查数据结构中的基本术语。 

【解析】对于A，数据项是数据不可分割的最小单位。对于B，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。对于C，数据元素是数据的基本单位，一个数据元素可由若干的数据项组成。对于D，数据变量通常包括定类变量，定序变量，定距变量，定比变量等。与题干相符的定义为数据项，故本题选A。

2、试题答案：A

试题解析：

【考点】本题考查栈的定义。 

【解析】栈是限定只能在表的一端进行插入和删除操作的线性表。在表中允许插入和删除的一端称为“栈顶”，不允许插入和删除的一端称为“栈底”。故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查线性表的存储。 

【解析】线性表有两种存储结构，一种为顺序存储，另一种为链式存储。对于A，链表是非随机存取结构，而顺序存储是随机存储结构，因此A错误。对于B，链表插入和删除元素仅需修改指针不需要移动元素，而顺序表的删除和删除均需要移动元素，因此B正确。对于C，顺序存储，用一组连续的存储单元依次存储线性表中的数据元素；链式存储，用一组任意的存储单元存储线性表的数据元素，这个存储单元可以是连续的也可以是不连续的。因此C错误。对于D，链表可以动态变化，而顺序表初始时需要分配一个预定义大小的空间，若表中元素的个数不变更适宜采用顺序表而非链表，因此D错误。故本题选B。

4、试题答案：D

试题解析：

【考点】本题考查循环队列的基本操作。 

【解析】将顺序队列首尾相接成环状空间，在循环队列中，队头指针指向头元素，队尾指针指向尾元素的下一个位置。若循环队列中存放n个元素，则rear==front，此时无法判断是队空的条件还是队满的条件。为了区分这两者，规定循环队列中当元素个数为n-1个时，判定队列已满。循环队列出队时头指针后移一个单位，队首指针更新为：e==front; front==(front+1)%maxsize; 。maxsize表示数组的最大存储空间，在本题中maxsize=m，故本题选D。

5、试题答案：B

试题解析：

【考点】本题考查哈夫曼树带权路径长度的计算。 

【解析】根据题干所给权值构造哈夫曼树如下：

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、试题答案：A

试题解析：

【考点】本题考查广义表的基本操作。 

【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。题干所给的广义表的表头是元素a，故本题选A。

8、试题答案：A

试题解析：

【考点】本题考查二叉树的遍历。 

【解析】根据二叉树的中序序列和前序序列可以唯一的确定一棵二叉树，画出该二叉树如下所示：

9、试题答案：B

试题解析：

【考点】本题考查完全二叉树的性质。

 【解析】深度为k的完全二叉树结点最少时树的第1至k-1层构成满二叉树，第k层仅有1个结点。满二叉树第i层的结点个数=2i-1，因此1至k-1层所含的结点总数=2⁰+2¹+2²+…+2^k-2=2^k-1-1，因此深度为k的完全二叉树最少有2^k-1个结点，故本题选B。

10、试题答案：D

试题解析：

【考点】本题考查无向图的存储。 

【解析】无向图的邻接表中，表头结点存储的是无向图的顶点，因此表头结点的个数为n。每个表头结点都对应一个边表链表，存储与表头结点相连接的结点，其大小为边数。因为是无向图，表结点会重复计算边，因此表结点个数为2*e，故本题选D。