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

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

1、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ）。

A、存储结构

B、逻辑结构

C、顺序存储结构

D、链式存储结构

2、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。

A、110

B、108

C、100

D、120

3、设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ ）。

A、n-i+1

B、n-i

C、n-i-1

D、i

4、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（  ）个元素。

A、8

B、63.5

C、63

D、7

5、判定一个队列QU（最多元素为m0）为满队列的条件是（ ）。

A、QU->rear - QU->front = = m0

B、QU->rear - QU->front -1= = m0

C、QU->front = = QU->rear

D、QU->front = = QU->rear+1

6、链表是一种采用（ ）存储结构存储的线性表。

A、顺序

B、链式

C、星式

D、网状

7、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续或不连续都可以

8、线性表Ｌ在（ ）情况下适用于使用链式结构实现。

A、需经常修改Ｌ中的结点值

B、需不断对Ｌ进行删除插入

C、Ｌ中含有大量的结点

D、Ｌ中结点结构复杂

9、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。

A、i

B、n=i

C、n-i+1

D、不确定

10、设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为（ ）。

A、n

B、e

C、2e

D、7

1、试题答案：C

试题解析：

【考点】本题考查顺序存储结构的性质。
【解析】数据结构包括数据的逻辑机构和数据的存储结构两个层次，数据在计算机内存储表示的是数据的存储结构，因此B错误。存储结构有两种，数据的顺序存储结构和链式存储结构。其中顺序存储结构物理地址相同且连续，链式存储结构用附加的指针表示数据元素之间的关系，故本题选C。

2、试题答案：B

试题解析：

【考点】本题考查数据在计算内的存储。
【解析】画出该向量在计算内的存储结构如下所示：

由上图可知，故本题选B。

3、试题答案：A

试题解析：

【考点】本题考查顺序表的基本操作。
【解析】顺序表的插入操作是指在第i-1个元素和第i个元素之间插入一个数据元素，使长度为n的线性表长度变为n+1，需要将第n到i的元素向后移动一位，共需移动元素的个数为n-i+1。故本题选A。

4、试题答案：B

试题解析：

【考点】本题考查顺序表的基本操作。
【解析】该顺序表有127个元素，共有128个位置可以插入元素。当元素插入在第1个位置时，需要移动的元素个数为127；当元素插入第2个位置时，需要移动元素的个数为126；……；当插入第127个位置时，需要移动的元素个数为1；当插入第128个位置时，需要移动的元素个数为0。因此，总的移动元素个数除以插入的次数，即可求出平均移动元素个数。平均移动元素个数=[（0+127）*128/2]/128=127/2=63.5。故本题选B。

5、试题答案：A

试题解析：

【考点】本题考查队列判满条件。
【解析】队列中最多元素为m0，因此当尾指针-头指针=元素个数时，队列已满，因此A正确B错误。头指针和尾指针指向同一个位置时队列为空，因此C和D错误，故本题选A。

6、试题答案：B

试题解析：

【考点】本题考查数据结构的存储结构。
【解析】数据结构的存储结构有两种，分别为顺序存储结构和链式存储结构，而链表采用的是链式存储结构，因此A错误，B正确。C选项不是一种存储结构，因此C错误。D选项是数据结构的逻辑结构，因此D错误。故本题选B。

7、试题答案：D

试题解析：

【考点】本题考查线性表的存储结构。
【解析】线性表有两种存储结构，一种为顺序存储，用一组连续的存储单元依次存储线性表中的数据元素。其特点为
① 是一种随机存取的结构；② 初始时需要为顺序表分配一个预定义大小的空间；③ 插入和删除操作均需要移动元素。
另一种为链式存储，用一组任意的存储单元存储线性表的数据元素，这个存储单元可以是连续的也可以是不连续的。其特点为① 非随机存取结构，线性链表的存取需要从头指针开始；② 插入和删除元素仅需修改指针不需要移动元素。
线性表的链式存储结构采用指针表示数据元素之间的逻辑关系，地址可连续可不连续。故本题选D。

8、试题答案：B

试题解析：

【考点】本题考查线性表的存储结构。
【解析】线性表的有两种存储结构，顺序存储和链式存储。顺序存储支持随机存取而链式不支持，故A选项更适合顺序存储。顺序存储插入和删除均需要移动元素，而链式存储插入和删除仅需修改指针不需移动元素，故B选项采用链式存储更好。C和D选项不影响存储结构。故本题选B。

9、试题答案：C

试题解析：

【考点】本题考查栈的基本操作。
【解析】栈具有后进先出的特性。由于入栈的最后一个元素是出栈的第一个元素，出栈的序列应该为入栈序列的相反序列，即出栈序列为n，n-1，n-2，……，2，1。因此，pi=n-i+1。故本题选C。

10、试题答案：C

试题解析：

【考点】本题考查无向图的度。
【解析】无向图中的每条边连接两个顶点，分别为顶点的一个度，因此无向图的度即为边数的二倍。故本题选C。