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

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

1、线性表采用链式存储时，其地址（ ）。

A、必须是连续的

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

C、一定是不连续的

D、连续与否均可以

2、若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。

A、n-i

B、n-i-1

C、n-i+1

D、不确定

3、已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是（ ）。

A、s= p->next; p=p->next; free(s);

B、p=p->next; free(p);

C、s= p->next; p->next=s->next; free(s);

D、p=p->next; free(p->next);

4、若使用邻接矩阵表示某有向图，则矩阵中非零元素的个数等于（ ）。

A、图中顶点的数目

B、图中边的数目

C、图中边的数目的两倍

D、无法确定

5、下列哪种排序需要的附加存储开销最大（ ）。

A、快速排序

B、堆排序

C、归并排序

D、插入排序

6、下面哪一方法可以判断出一个有向图是否有环（即回路）（ ）。

A、拓扑排序

B、求最短路径

C、求最小生成树

D、广度优先遍历

7、具有n个顶点的无向图至少应有（ ）条边才能确保是一个连通图。

A、n-1

B、n

C、n+1

D、2n

8、对线性表进行折半查找时，要求线性表必须（ ） 。

A、以顺序方式存储

B、以顺序方式存储，且结点按关键字有序排序

C、以链接方式存储

D、以链接方式存储，且结点按关键字有序排序

1、试题答案：D

试题解析：

本题考查线性表的存储。
线性表有两种存储结构，一种为顺序存储，另一种是链式存储。线性表采用链式存储的特点是用一组任意的存储单元存储线性表的数据元素，这个存储单元可以是连续的也可以是不连续的。线性表采用顺序存储是地址是连续的存储空间，故本题选D。

2、试题答案：C

试题解析：

本题考查栈的基本操作。
栈具有后进先出的特性，只允许在表的一端进行插入和删除。表尾端称为栈顶，表头端称为栈底。由于栈的输入序列是1，2，3，…，n，输出的第一个元素是n，因此该栈的输出序列应该为输入序列的逆序，即n，n-1，……，3，2，1，则第i个输出元素即n-i+1。故本题选C。

3、试题答案：C

试题解析：

本题考查单链表的基本操作。
单链表删除结点的操作即将p的next指针指向p的next的next指针，之后再释放p->next即可。具体操作如下图所示：

故本题选C。

4、试题答案：B

试题解析：

本题考查图的存储。
有向图构造矩阵时，若从Vi到Vj有弧，则Vi,j为1，否则为0。因此非零元素的个数即为边数。故本题选B。

5、试题答案：C

试题解析：

本题考查排序算法的辅助空间。
归并排序的辅助空间为O（n），快速排序的辅助空间为O（logn），堆排序和插入排序的辅助空间为O（1）。故本题选C。

6、试题答案：A

试题解析：

本题考查有向图回路判断。
判断有向图是否存在环有两种方法，分别为深度遍历和拓扑排序。若深度遍历中有结点被第二次访问到则证明有环。拓扑排序的思想为每次找入度为0的点，添加到输出队列，然后将与此点相连的结点入度减1，重复上述过程直至删除所有结点。若存在结点无法删除，则证明有环。而B、C、D选项涉及的最短路径算法、最小生成树算法、广度优先算法都是既可以适用于有环图也可以适用于无环图，因此无法判断回路。故本题选A。

7、试题答案：A

试题解析：

本题考查无向图的连通性。
图的连通性是指从任一顶点出发即可以访问所有顶点。无向图中，如果任意两个顶点之间能够连通，则称此无向图为连通图。因此将n个顶点连接起来没有孤立的顶点时该图为连通图，则连接n个顶点至少需要n-1条边。故本题选A。

8、试题答案：B

试题解析：

本题考查折半查找的适用性。
折半查找是针对顺序有序表设计的，因此只能适用于顺序存储结构的线性表，且该算法要求线性表有序排序。故本题选B。