2014年数据结构考研真题答案及解析

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

1、 当输入非法错误时，一个“好"的算法能够进行适当的处理，而不会产生难以理解的输出结果。这称为算法的( )。

A、 正确性

B、 可行性

C、 健壮性

D、 有穷性

2、若线性表最常用的操作是存取第 i个元素及其前驱和后继元素的值，为了节省时间应采用以下哪一种存储方式最合适? (  )

A、 顺序表

B、 单链表

C、 单循环链表

D、 双向循环链表

3、为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，当( )时，才产生上溢。

A、 两个栈的栈顶同时到达栈空间的中心点

B、 其中一个栈的栈顶到达栈空间的中心点

C、 两个栈的栈顶在栈空间的某一位置相遇

D、 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底

4、深度为h的满m叉树的第k层有( )个结点（1<=k<=h）。

A、 m^k-1

B、 m^k-1

C、 m^h-1

D、 m^h-1

5、要连通具有n个顶点的有向图，至少需要( )条边。

A、 n-1

B、 n

C、 n+1

D、 2n

6、折半查找的时间复杂度为( )。

A、 O（n²）

B、 O（n）

C、 O（nlog₂n）

D、 O（log₂n）

7、对序列{25，19，17，18，30，-10，14，28}用希尔排序方法排序，经一趟后序列变为{25，-10， 14，18，30，19，17，28}，则该次采用的增量是(  )。

A、 1

B、 4

C、 3

D、 2

8、删除堆顶元素重建堆的时间复杂度是( )。

A、 O（nlog₂n）

B、 O（n）

C、 O（log₂n）

D、 O（1）

9、下列排序算法中，( )算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

A、 堆排序

B、 冒泡排序

C、 快速排序

D、 插入排序

10、在排序表的数据元素的关键字分布随机情况下，就排序算法所用的辅助空间大小而言，堆排序、快速排序、归并排序的关系是(  )。

A、 堆排序<快速排序<归并排序

B、 堆排序<归并排序<快速排序

C、 堆排序>归并排序>快速排序

D、 堆排序>快速排序>归并排序

1、试题答案：C

试题解析：

【考点】本题考查算法设计的要求。
【解析】算法的五大特性分别为有穷性、确定性、可行性（有效性）、输入、输出。算法设计的要求为正确性、可读性、健壮性、时间效率高和存储量低。对于A，正确性指算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案，与题干描述不符，因此A错误。对于B，可行性是算法的特性不是算法设计的要求，因此B错误。对于C，健壮性指当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果，因此C正确。对于D，有穷性是算法的特性不是算法的设计要求，因此D错误。故本题选C。

2、试题答案：A

试题解析：

【考点】本题考查顺序存储和链式存储的特点。
【解析】对于A，顺序表属于顺序存储，顺序存储属于随机存储结构，其存取第i个元素及其前驱和后继的时间复杂度为O（1）。对于BCD，链表属于链式存取结构，是非随机存储结构。链表访问第i个元素的时间复杂度为O（n）。单链表访问第i个元素的后继的时间复杂度为O（1），单链表不能访问前驱元素；单循环链表访问第i个元素的后继的时间复杂度为O（1），访问第i个元素的前继的时间复杂度为O（n）；双向循环链表访问第i个元素的后继的时间复杂度为O（1），访问第i个元素的前继的时间复杂度为O（1）。故本题选A。

3、试题答案：C

试题解析：

【考点】本题考查栈的存储。
【解析】在一个程序中，需要同时使用具有相同成分类型的两个栈时，为避免造成存储空间的浪费，应采用双进栈操作。存储空间中，一个栈的栈底为该空间的始端，另一个栈的栈底为该空间的末端。当元素进栈时都从存储空间的两端向中间“延伸”，当两个栈的栈顶在该存储空间的某处相遇时，才会发生“上溢”。对于A和D，仅描述了“相遇”情况的一种，因此A和D错误；对于B，这种情况下存储空间未满，不会发生“上溢”，因此B错误。故本题选C。

4、试题答案：A

试题解析：

【考点】本题考查树的性质。
【解析】对于满m叉树，每个结点都有m个子结点。因此，当h=1时，该层结点数n1=1=m⁰；当h=2时，n₂=m=m¹；当h=3时，n₃=m²；…；当h=k时，n_k=m^k-1。故本题选A。

5、试题答案：B

试题解析：

【考点】本题考查图的连通性。
【解析】图的连通性是指图中任意两点之间存在一条路径使得这两点可达。n个顶点的有向图串联成一个环时，此时图具有连通性且需要的边个数最少，需要n条边。若该图为无向图，将顶点串联起来即可，最少需要n-1条边。故本题选B。

6、试题答案：D

试题解析：

【考点】本题考查折半查找。
【解析】具有n个结点的折半查找的判定树的深度为h=⎿log₂n⏌+1，折半查找的关键字比较次数最多为⎿log₂n⏌+1，因此折半查找的时间复杂度为O（log₂n），故本题选D。

7、试题答案：B

试题解析：

【考点】本题考查希尔排序的应用。
【解析】对题干中序列的关键字依次编号0-7。若希尔排序的则增量为1，则相邻的关键字应当有序，因此A错误。若增量为4，则第0个元素与第4个号元素有序，第1个元素与第5个元素有序，依次类推。上述序列符合该规律，因此B正确。若增量为3，则第0个元素与第3个、第6个元素有序，第1个元素与第4个、第7个元素有序，依次类推。上述序列不符合该规律，因此C错误。若增量为2，则第0个元素与第2个、第4个、第6个元素有序，第1个元素与第3个、第5个、第7个元素有序，上述序列不符合该规律，因此D错误。故本题选B。

8、试题答案：C

试题解析：

【考点】本题考查堆的构造的时间复杂度。
【解析】堆排序的时间复杂度为O（nlog₂n），第i次删除堆顶元素并重新建堆的时间复杂度为O（log₂n），有n个结点，因此需要删除n-1次堆顶元素并建堆。故本题选C。

9、试题答案：D

试题解析：

【考点】本题考查排序算法的比较。
【解析】对于A，堆排序通过构造最大值堆或最小值堆进行排序，因此每一趟的排序结果会将最大值或最小值选择出来。对于B，冒泡排序的第i趟结果会将序列中的最大（小）值定位在R[i]的位置上。对于C，快速排序每一趟结果会确定其基准值的位置。对于D，插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。若插入排序的最小值在无序数组的最后一个位置，则插入该值时需要将之间所有元素向后移动，故本题选D。

10、试题答案：A

试题解析：

【考点】本题考查排序算法的辅助空间。
【解析】堆排序需要的辅助空间为O（1），快速排序需要的辅助空间为O（logn），归并排序需要的辅助空间为O（n），故本题选A。