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

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

1、以下说法正确的是( )。

A、 数据元素是数据的最小单位

B、 数据项是数据的基本单位

C、 数据结构是带有结构的各数据项的集合

D、 数据结构是带有结构的数据元素的集合

2、给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是( )。

A、 O（n²）

B、 （nlog₂ⁿ）

C、 O（n）

D、 O（1）

3、一个栈的输入序列为 1，2，3，4，5，则下列序列中不可能是栈的输出序列的是( )。

A、 5 4 1 3 2

B、 2 3 4 1 5

C、 2 3 1 4 5

D、 1 5 4 3 2

4、以下说法正确的是( )。

A、 队列是先进后出的线性表

B、 队列是线性表的一种特殊存储结构

C、 队列可以通过两个栈来模拟实现

D、 对于插入或删除较为频繁的操作，链队列比循环队列效率更高

5、将含100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为59的结点W的双亲编号为(  )。

A、 28

B、 29

C、 30

D、 无法确定

6、 设有一个二维数组D[m][n]，假设按行为主序把D[0][0]存放位置在600（10），而D[3][3]存放位置在678（10），每个元素占一个空间，请问D[2][4]存放在(  )位置? （脚注（10）表示用10进制表示，m>3）。

A、 653₍₁₀₎

B、 654₍₁₀₎

C、 663₍₁₀₎

D、 664₍₁₀₎

7、下列哪一种图的邻接矩阵一定是对称矩阵? ( )。

A、 AOV网

B、 AOE网

C、 有向图

D、 无向网

8、下面关于哈希（散列）查找的说法正确的是( )。

A、 哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B、 不存在特别好与坏的哈希函数，要视情况而定

C、 除留余数法是所有哈希函数中最好的

D、 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

9、在等概率情况下，对长度为n的线性表进行顺序查找的平均查找长度ASL为(  )。

A、 n

B、 （n-1）/2

C、 n/2

D、 （n+1）/2

10、归并排序中，归并的趟数是(  )。

A、 O（nlog₂n）

B、 O（n）

C、 O（log₂n）

D、 O（n²）

1、试题答案：D

试题解析：

【考点】本题考查数据结构相关的基本概念。
【解析】数据元素是数据的基本单位，一个数据元素可有若干的数据项组成，因此A错误。数据项是数据不可分割的最小单元，因此B错误。数据元素是数据的基本单元，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，因此D正确，而不是数据项的集合，因此C错误。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查创建有序单链表的时间复杂度。
【解析】题干要求创建有序的单链表，因此单链表创建的过程中，每插入一个结点，都需要遍历整个链表寻找当前结点的位置，一个结点插入链表的时间复杂度为O（n）,n个结点插入链表的时间复杂度为O（n²）。故本题选A。

3、试题答案：A

试题解析：

【考点】本题考查栈的基本操作。
【解析】栈具有“后进先出”的基本特性，栈的输入序列为 1，2，3，4，5。对于A，若首先出栈的元素为5，则1、2、3、4必然已经先于5入栈，且1先于2和3入栈，则出栈序列中不应该出现在2和3之前，因此A错误。对于B，若其操作为：push（1） push（2） pop（2） push（3） pop（3） push（4） pop（4） pop（1） push（5） pop（5），则B为有可能的输出序列。对于C，若其操作为：push（1） push（2） pop（2） push（3） pop（3） pop（1） push（4） pop（4） push（5） pop（5），则C为有可能的输出序列。对于D，若其操作为：push（1） pop（1） push（2） push（3） push（4） push（5） pop（5） pop（4） pop（3） pop（2），则D为有可能的输出序列。故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查队列的性质。
【解析】对于A，队列是“先进先出”的线性表，因此A错误。对于B，队列有顺序存储和链式存储两种存储结构，其存储结构不特殊。队列是一种特殊的线性表是指队列的操作受限，因此B错误。对于C，队列可以通过两个栈来模拟实现，其方法为栈s1来模拟入队功能，若要模拟出队功能则将s1序列出栈到s2栈，此时将栈s2出栈序列和队列出队的顺序相同，因此C正确。对于D，循环队列和链队列插入和删除操作的时间复杂度均为O（1），二者效率相同，故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查完全二叉树的性质。
【解析】根据完全二叉树的性质，结点i的左孩子为2*i，右孩子为2*i+1，双亲结点为i/2。本题问59的双亲结点，即59/2=29，故本题选B。

6、试题答案：B

试题解析：

【考点】本题考查二维数组的存储。
【解析】由题干可知，按行序为主且从0开始存放。首先计算D[3][3]之前需存放的元素个数=3*n+3。每个元素占一个空间，因此3*n+3个元素占的空间大小为3*n+3。D[3][3]存放位置=600₍₁₀₎+ （3*n+3）*1=678，解得n=25。D[2][4]的位置=600(₁₀₎+（2*25+4）*1=654₍₁₀₎。由此可得故本题选B。

7、试题答案：D

试题解析：

【考点】本题考查图的存储结构。
【解析】AOV网和AOE网均为有向图，而有向图的邻接矩阵不一定是对称矩阵，因此A、B、C错误，无向图的邻接矩阵一定是对称矩阵，故本题选D。

8、试题答案：B

试题解析：

【考点】本题考查哈希查找。
【解析】对于A，哈希函数并非越复杂越好，复杂的哈希函数会增加计算的时间，降低哈希查找的效率，因此A错误。对于B，哈希函数的构造的好坏需视情况而定，因此B正确。对于C，不同的哈希函数有不同的使用情况。除留余数法计算地址的公式为H（key）=key MOD p（p<=m）。在使用除留余数法时，p的选择很重要，若p选择不好，容易产生同义词，因此C错误。对于D，哈希表由于存在冲突，其删除操作不可以简单删除元素，因此D错误，故本题选B。

9、试题答案：D

试题解析：

【考点】本题考查顺序查找的平均查找长度。
【解析】顺序查找时，查找第一个元素的查找长度为1，查找第二个元素的查找长度为2，…，查找第n个元素的查找长度为n，因此总的查找长度=1+2+3+…+n=n*（n+1）/2。本题要求平均查找长度，因此ASL=（n+1）/2，故本题选D。

10、试题答案：C

试题解析：

【考点】本题考查归并排序的过程。
【解析】归并的含义是将两个或两个以上的有序表合成一个新的有序表。二路归并排序的具体步骤为：假设初始序列含有n个记录，则可以看成n个有序的子记录，每个子记录的长度为1。然后两两归并，得到⎾n/2⏋个长度为2或为1的有序子序列；再两两归并，…，如此重复，直到得到一个长度为n的有序序列为止。第一趟归并划分n/2个子序列，第二趟归并划分n/4个子序列，第三趟归并划分n/8个子序列，…，第log₂n趟归并划分1个子序列，因此归并的趟数为log₂n，故本题选C。