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