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

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

1、以下数据结构中，(  )是非线性数据结构。

A、 二叉树

B、 字符串

C、 队列

D、 栈

2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以(  )为基本操作。

A、 条件判断

B、 结点移动

C、 算术表达式

D、 赋值语句

3、假设 front是指向循环队列队头元素的前一个位置，rear 是指向循环队列的队尾元素的真正位置，maxsize是存储循环队列的数组长度，则循环队列的队满条件为（  ）。

A、 （rear+1） % mazsize = = （ front+1） % maxsize

B、 （ rear+1） % maxsize = = front+1

C、 （rear+1） % maxsize = = front

D、 rear== front

4、设mxn的稀疏矩阵A的非零元素个数为t，对于基于三元组顺序表的稀疏矩阵转置的处理方法以下说法正确的是( )。

A、 按照矩阵A的列序来进行转置，算法的时间复杂度为O（n+t）

B、 按照矩阵A的三元组顺序表a.smarray的次序进行转置，算法的时间复杂度为O（n*t）

C、 按照矩阵A的列序来进行转置的方法称快速转置

D、 按照矩阵A的列序进行转置，对于t<<mxn才有意义

5、广义表A=(a，b，(c，d)，(e，(f，g)))，则式子Head（Tail（Head（Tail（Tail（A)))) 的值为(  )。

A、（g）

B、（d）

C、 c

D、 d

6、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(  )次序的遍历实现编号。

A、 先序

B、 中序

C、 后序

D、 从根开始按层次遍历

7、下列说法不正确的是( )。

A、 图的深度遍历不适用于有向图

B、 图的遍历是从给定的顶点出发每一个顶点仅被访问一次

C、 图的遍历的基本算法有两种: 深度遍历和广度遍历

D、 图的深度遍历是一个递归过程

8、在下述结论中，正确的是(  )。①将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为logn量级（n为线性表中的结点数目）。②对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。

A、只有①正确

B、只有②正确

C、①②都正确

D、①②都不正确

9、 一趟排序结束后不一定能够选出一个元素放在其最终位置上的排序是( )。

A、 堆排序

B、 冒泡排序

C、 快速排序

D、 希尔排序

10、下列排序算法中， 其中( )是稳定的。

A、 直接插入排序和快速排序

B、 折半插入排序和冒泡排序

C、 简单选择排序和二路归并排序

D、 树形选择排序和希尔排序

1、试题答案：A

试题解析：

【考点】本题考查数据结构的逻辑结构.
【解析】线性结构数据元素之间存在“一对一”的对应关系，而二叉树是树型结构数据元素之间存在“一对多”的对应关系。字符串、队列、栈均为“一对一”的对应关系，是线性结构，故本题选A。

2、试题答案：B

试题解析：

【考点】本题考查顺序表的基本操作。
【解析】题干中已点明从时间复杂度的角度考虑，顺序表的插入和删除的时间复杂度均为O（n）。删除第i个结点后，i结点之后的所有元素均需要向前移动一位；在第i个位置上插入结点后，第i之后的所有元素均需要向后移动一位，因此插入和删除算法的基本操作是结点的移动。A、C、D选项涉及的操作其时间复杂度均为O（1）。故本题选B。

3、试题答案：C

试题解析：

【考点】本题考查循环队列的判断条件。
【解析】题干中已经表明front指向队头元素的前一个位置，而rear指向队尾元素。循环队列中，当元素个数为n-1个时，判定队列已满。因此当队列已满，尾元素的后一个位置应当为头元素的前一个位置，即尾指针+1为头指针的位置，故本题选C。

4、试题答案：D

试题解析：

【考点】本题考查三元组顺序表的转置。
【解析】对于A，按照矩阵A的列序进行转置的算法的时间复杂度为O（n*t），因此A错误。对于B，a.summary代表每列中非零元素出现的个数，这种方法是快速转置法，其时间复杂度为O（n+t），因此B错误。对于C，快速转换的方法是统计每列中非零元素出现的个数，从而确定转置后的元素的位置，而按照列序进行转置的方法是一般转置法，因此C错误。对于D，稀疏矩阵的存储空间为3*（t+1），二维数组的存储空间m*n，因此当3*（t+1）< m*n时，矩阵的三元组存储才有意义，即t<<m*n时按照矩阵A的列序进行转置才有意义。故本题选D。

5、试题答案：D

试题解析：

【考点】本题考查广义表基本操作。
【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。对于题干中的式子，从内向外进行分析，Tail（A）=（b，（c，d），（e，（f，g）））；（Tail（Tail（A））=（（c，d），（e，（f，g）））；（Head（Tail（Tail（A））））=（c，d）；（Tail（Head（Tail（Tail（A）））））=（d）；Head（Tail（Head（Tail（Tail（A）））））=d。故本题选D。

6、试题答案：C

试题解析：

【考点】本题考查二叉树的遍历。
【解析】根据题干分析可知，根结点及其左右孩子结点的大小关系为根结点>右孩子结点>左孩子结点，即左孩子结点<右孩子结点<根结点的值。而后序遍历的顺序恰为先遍历左子树、再遍历右子树、最后遍历根结点。对于A，先序结点先遍历根结点、再遍历左孩子结点、最后遍历右孩子结点，因此A错误；对于B，中序遍历先遍历左孩子结点、再遍历根结点、最后遍历右孩子结点，因此B错误；对于D，层次遍历是按照树的层高进行遍历的，显然与题干的要求不符，因此D错误。故本题选C。

7、试题答案：A

试题解析：

【考点】本题考查图的遍历。
【解析】图的遍历算法有两种，一种为深度优先遍历，另一种为广度优先遍历，因此C正确。深度优先遍历可以遍历有向图，不能遍历有环图，因此A错误。不管是深度优先遍历还是广度优先遍历都需要记录被遍历过的顶点，因此每一个顶点均被访问一次，因此C正确。对于D，深度优先是递归的过程，因此D正确。故本题选A。

8、试题答案：C

试题解析：

【考点】本题考查查找的应用。
【解析】对于①，平衡二叉树的左子树与右子树的高度之差的绝对值小于等于１，树的高度与logn同数量级，因此任意检索长度均为logn量级，①正确。对于②，查找成功时，有序表和无序表均需要从头开始按顺序遍历查找，有序的顺序表和无序顺序表的平均查找长度相同，ASL=（1+2+3+…+n）/n=（n+1）/2。查找不成功时，有序表按顺序查找，若查找到的值大于a[i]同时小于a[i+1]，则查找失败，此时失败查找长度ASL大于等于2且小于等于n。或者将顺序表所有元素遍历完仍没有查找到待查找元素，则查找失败，此时失败查找长度=n。因此查找不成功时ASL<=n；无序表将顺序表从头遍历至尾，其查找长度ASL=n。因此②正确。故本题选C。

9、试题答案：D

试题解析：

【考点】本题考查排序算法的比较。
【解析】对于A，堆排序的每一趟结果均能从堆中选择出最大值或者最小值；对于B，以升序的冒泡排序为例，排序过程中将大的值向上漂浮，小的值下沉，因此一趟排序过后会将无序序列中的最大值找出；对于C，快速排序的每一趟结果可以确定基准值的最终位置；对于D，希尔排序是增量间的插入排序，只有最后一趟结果才能最终确认元素的位置，故本题选D。

10、试题答案：B

试题解析：

【考点】本题考查排序算法的稳定性。
【解析】排序算法的稳定性是指若排序后的序列不改变原序列中相同关键字的相对位置，则称为稳定性排序，否则为不稳定性排序。快速排序是不稳定性排序。假定存在这种情况：若基准值为首元素，存在两个相同的元素均比基准值小，右指针首先指向比基准小的元素在较靠后的位置，则通过交换后，靠后位置的元素放在了前面。因此A错误。简单选择排序是不稳定性排序。假定存在这种情况：第一趟排序如果一个元素比当前元素小，而该小的元素在一个和当前元素值相等的元素的后面，则通过交换后，当前元素放在与之相等的元素的后面。因此C错误。希尔排序是不稳定性排序，增量间数据的排序可能会改变相同数据的相对位置。树形选择排序是一种按照锦标赛思想进行的排序，是不稳定排序。因此D错误。故本题选B。