A． q=p->left; r=p->right; q->right=r; r->left=q; 正确的

B． q=p->right; r=p->left; q->right=r; r->left=q; 把A的p和q反过来，结果错了。

C． q=p->left; r=p->right; q->left=r; r->right=q; 错误，与B一样，只是把p和q反过来。 D．q=p->left; r=p->right; q->right=r->left; 什么也没有变化。

7．会引起循环队列队头位置发生变化的操作是 A．出队列

8．如图1所示，若从顶点1出发进行广度优先搜索，则得到的访问序列是 A． 1,8,3,4,5,6,7,2 B． 1,2,3,7,5,6,4,8 C． 1,2,5,4,3,6,7,8 D．1,2,3,4,5,6,7,8

9．下列排序算法中，不受数据初始状态影响，时间复杂度为O(n*logn)的是 A．堆排序

10．用指针实现二叉树，在n个节点的二叉树中含有多少个空指针？ A．n

11．用一棵二叉搜索树进行( )得到的是有序序列。 A．前序遍历

12．合并排序算法的时间复杂度是 A．O(n2)

二、 填空题（共7小题，每空2 分，共16分）

13．在一个长度为n的顺序表的第i（1<=i<=n）个元素之前插入一个元素，需要

B．O(nlogn)

C．O(logn)

D．O(n)

B．中序遍历

C．后序遍历

D．层次遍历

B．n-1

C．n+1

D．2n

B．冒泡排序

C．直接选择排序

D．快速排序

B．入队列

C．取队首元素

D．取队尾元素

后移___n-i+1____个元素。

14．设某哈夫曼树有n个叶子节点，则该哈夫曼树的总结点数为__2n-1__。

15．设有一个序列8,53,37,28，当使用直接插入排序从小到大排序时，比较次数是____5____。

16．设SQ为循环队列，存储在数组queue[0…m-1]中，则SQ入队操作对其队尾指针rear的修改是___ (rear+1)%m___。

17．设待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序是__稳定的____，否则称为___不稳定的___。

18．在一个具有n个顶点的无向图中，要连通所有的顶点至少需要__n-1____条边。

19．在有向图中，以顶点v为起点的弧的数目称为v的___出度__。

三、 应用题（共4小题，每小题10 分，共40分）

20．已知关键字序列(12,77,21,65,38,7,40,53)，采用直接插入排序按递增排序，给出每一趟的结果。 12,77,21,65,38,7,40,53 12,21,77,65,38,7,40,53 12, 21,65, 77,38,7,40,53 12, 21, 38,65, 77, 7,40,53 7,12, 21, 38,65, 77, 40,53 7,12, 21, 38,40,65, 77, 53 7,12, 21, 38,40,53,65, 77

21．已知散列表长度为10（散列空间0..9），使用线性重新散列技术解决冲突，

现有一组单词(SUN, MON, TUE , WED , THU, FRI, SAT)，其对应的散列函数值分别为(3,2,6,3,2,5,6)，请画出这组单词插入后的散列表。 0 1 2 MON 3 SUN 4 WED 5 THU 6 TUE 7 FRI 8 SAT 9 22．假设一个二叉树的先序为EBADCFHGIKJ，中序序列是ABCDEFGHIJK， （1） 画出二叉树；（2）写出后序序列。

先序为EBADCFHGIKJ，中序序列是ABCDEFGHIJK，根是E E

/ \\

ABCD FGHIJK 中 BADC FHGIKJ 先序 根B 根F

/ \\ / \\

A CD GHIJK 中 A DC HGIKJ 先序

根D 根H / / \\ C G IJK 中 IKJ 先 根I \\ JK中 KJ先 根K / J

最后结果： E