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

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

1、一个队列的入列序列是1，2，3，4，则队列的输出序列是（ ）。

A、4，3，2，1

B、1，2，3，4

C、1，4，3，2

D、3，2，4，1

2、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear， 则当前队列中的元素个数是（ ）。

A、（rear-front+m）%m

B、rear-front+1

C、rear-front-1

D、rear-front

3、平衡二叉树的平均查找长度是（ ）。

A、O（n2）

B、O（nlog2n）

C、O（n）

D、O（log2n）

4、设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。

A、N1-1

B、N2-1

C、N2+N3

D、N1+N3

5、计算机内部数据处理的基本单元是（ ）。

A、数据

B、数据元素

C、数据项

D、数据库

6、设按照从上到下、从左到右的顺序从1开始对完全二叉树的结点进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。

A、2i+1

B、2i

C、i/2

D、2i-1

7、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。

A、第i行非0元素的个数之和

B、第i列非0元素的个数之和

C、第i行0元素的个数之和

D、第i列0元素的个数之和

8、设一组初始记录关键字序列为（16，25，12，30，47，11，23，36，9，18，31），则以增量d=5的一趟希尔排序结束后的结果为（ ）。

A、11，23，12，9，18，16，25，36，30，47，31

B、11，23，12，9，16，18，25，36，47，30，31

C、16，23，12，9，11，18，25，36，30，47，31

D、9，11，12，16，18，23，25，30，36，47，31

9、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。

A、n

B、n-1

C、m

D、m-1

1、试题答案：B

试题解析：

本题考查队列的性质。
队列遵从先入先出的思想，其入队序列即为其出队序列1，2，3，4，因此B正确。区分队列和栈的概念，栈具有“先入后出”的特性，因此若此题改为栈，则栈的出栈顺序应该为4，3，2，1。故本题选B。

2、试题答案：A

试题解析：

本题考查循环队列。
由于该队列是循环队列，因此rear不一定比front大，若直接拿rear-front有可能得出负值，因此B、C、D错误。因此将循环队列中返回队列元素的个数的公式改为（rear-front+m）%m可以保证所求结果是非负数。故本题选A。

3、试题答案：D

试题解析：

本题考查平衡二叉树的基本概念。
AVL树本身是一棵二叉搜索树，且其左右子树的高度差不超过1，并且左右子树都是一个平衡二叉树。当二叉搜索树是单支树时，其搜索的效率为0（n），为了改进时间复杂度，对树的结构进行改进，改进后的AVL树，其时间复杂度为0（log2n）。故本题选D。

4、试题答案：A

试题解析：

本题考查森林与二叉树的转换。
森林转为二叉树的步骤为：（1）将每棵树转为二叉树；（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。因此，最后得到的二叉树的根节点即为第一棵二叉树的根节点，其余结点为二叉树的左孩子结点，其余所有树为二叉树的右孩子结点。则B的左孩子结点个数为N1-1，右孩子结点个数为N2+N3。故本题选A。

5、试题答案：B

试题解析：

本题考查数据结构的基本概念。
对于A，数据是对客观信息的一种描述，它由能被计算机识别与处理的数值、字符等符号构成的集合，数据不能作为数据处理基本单元，因此A错误。对于B，数据元素是数据的基本单元，在计算机程序中通常作为一个整体进行考虑和处理，因此B正确。对于C，数据项是数据不可分割的最小单元而非基本单元，因此C错误。对于D，数据库是大量数据的集合，无法作为数据处理的基本单元，因此D错误。故本题选B。

6、试题答案：B

试题解析：

本题考查完全二叉树的层次遍历。
当完全二叉树顺序存储在一维结构中时，按照从上到下、从左到右的顺序进行编号，则结点i的左孩子为2*i，右孩子为2*i+1，双亲结点为i/2。故本题选B。

7、试题答案：B

试题解析：

本题考查图的邻接矩阵存储。
图的邻接矩阵的定义为若Vi至Vi之间有弧，矩阵对应元素不为0，因此有向图中第i行元素之和为顶点Vi的出度，第i列元素之和为顶点Vi的入度。故本题选B。

8、试题答案：A

试题解析：

本题考查希尔排序的应用。
增量为5的希尔排序，16、11、31进行比较，25和23进行比较，12和36进行比较，30和9进行比较，47和18进行比较，因此对上述关键字排序后的序列为A选项。故本题选A。

9、试题答案：C

试题解析：

本题考查图的邻接表存储。
邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。根据邻接表的定义，图中表结点的个数即为边的个数。故本题选C。