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

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

1、二叉排序树中左子树上所有结点的值均（ ）根节点的值。

A、<

B、>

C、=

D、!=

2、设某链表中最常用的操作只是在链表中进行查找，则最好采取下列（ ）存储方式最节省时间。

A、无序静态表

B、有序静态表

C、单向链表

D、双向循环链表

3、设顺序线性表中有 n个数据元素，则删除表中第i个元素需要移动（ ）个元素。

A、n-i

B、n+1-i

C、n-1-i

D、i

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

A、N₁-1

B、N₂-1

C、N₂+N₃

D、N₁+N₃

5、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ ）。

A、O(n)

B、O(nlog₂n)

C、O(n²)

D、O(log₂n)

6、下列各种排序算法中平均时间复杂度为O(n2)的是（ ）。

A、快速排序

B、堆排序

C、归并排序

D、冒泡排序

7、设输入序列1、2、3、...、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。

A、n-i

B、n-1-i

C、n+1-i

D、不能确定

8、设散列表中有m个存储单元，散列函数H(key)= key%p，则p最好选择（ ）。

A、小于等于m的最大奇数

B、小于等于m的最大素数

C、小于等于m的最大偶数

D、小于等于m的最大合数

9、设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）。

A、4

B、5

C、6

D、7

1、试题答案：A

试题解析：

【考点】本题考查二叉排序树的性质。
【解析】二叉排序树的性质：（1）若其左子树不空，则左子树上所有结点的值均小于其根结点的值。（2）若其右子树不空，则右子树上所有结点的值均大于其根结点的值。（3）其左、右子树又分别是一颗二叉排序树。故本题选A。

2、试题答案：B

试题解析：

【考点】本题考查链表的存储。
【解析】链表在查找过程中，一般需要从头往后遍历，比较耗时，所以选项C和D优先排除。有序静态表相较于无序静态表在查找过程中，它更节省时间。故本题选B。

3、试题答案：A

试题解析：

【考点】本题考查顺序表删除元素时移动元素的个数。
【解析】在有n个元素的顺序表中，删除一个元素时，有n个位置可供选择。删除第1个元素时需要移动后面的n-1个元素，删除第2个元素时需要移动后面的n-2个元素，删除第3个元素时需要移动后面的n-3个元素，…，删除第n个元素时需要移动0个元素。由此归纳，得删除第i个元素需要移动n-i个元素。故本题选A。

4、试题答案：A

试题解析：

【考点】本题考查森林转化为二叉树。 

【解析】森林转化为二叉树的过程：首先，T₁、T₂和T₃先分别转化为二叉树，除根结点以外，其它结点都转化为根结点的左孩子。接着，第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子。最终实现森林到二叉树的转化。根据此过程易知，二叉树B的根结点的左子树的结点数为N₁-1。故本题选A。

5、试题答案：C

试题解析：

【考点】本题考查直接插入排序算法的时间复杂度。

【解析】由下表易知，直接插入排序算法的时复杂度为O(n²)。故本题选C。

注：r代表关键字基数，d代表长度，n代表关键字个数。

6、试题答案：D

试题解析：

【考点】本题考查常见排序算法的时间复杂度。
【解析】由下表易知，直接插入排序算法的时复杂度为O(n²)。故本题选D。

注：r代表关键字基数，d代表长度，n代表关键字个数。

7、试题答案：C

试题解析：

【考点】本题考查栈的输出。 

【解析】输出序列中的第一个元素是n，说明1、2、3已经全部入栈，输出时必定是按照n、n-1、...、2、1的顺序出栈的，所以输出序列中的第i个输出元素是n-i+1。故本题选C。

8、试题答案：B

试题解析：

【考点】本题考查散列函数。
【解析】散列函数H(key)=key%p中的p最好选择小于等于散列表表长的最大素数，这样有利于减少散列冲突的发生。故本题选B。

9、试题答案：C

试题解析：

【考点】本题考查求解树中的度数。
【解析】在树中，结点总数=分支数+1。设度为0、1、2、3的结点数分别为n0、n1、n2、n3，则有公式n0+n1+n2+n3 = 0*n0+1*n1+2*n2+3*n3+1。由题意知n1=2，n2=1，n3=2，将其带入公式得n0=6，即度数为0的结点数有6个。故本题选C。