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、以链接方式存储，且结点按关键字有序排序