一、 单项选择题(每小题 2 分,共 20 分)
1. 每个结点有多个后继结点的数据结构有____ ______。
A) 线性表 B) 队列 C) 图 D) 栈
2. 一个栈的输入序列为 1 2 3 4 5,则下列序列中不可能是栈的输出序列的是___ ______。
A)2 3 4 1 5 B)5 4 1 3 2 C)2 3 1 4 5 D)1 5 4 3 2
3. 以下的 4 棵二叉树中,_________不是完全二叉树。
A) B) C) D)
4. 一棵非空二叉树的前序序列和中序序列正好相同,则该二叉树一定满足_______。
A)其中任意一结点均无左孩子 B)其中任意一结点均无右孩子
C)是一棵完全二叉树 D)是任意一棵二叉树
5. 一棵度为 4 的树,n
1
,n
2
,n
3
,n
4
分别是度为 1 ,2 ,3 ,4 的结点个数,终端结点个数为
n
0
,则有___ _____。
A)n
0
= n
1
+ n
2
+ n
3
+ n
4
B)n
0
= 2n
4
+ n
3
+ 1
C)n
0
= 4n
4
+ 3n
3
+ 2n
2
+ n
1
D)n
0
= 3n
4
+ 2n
3
+ n
2
+ 1
6. 关键码序列 K = { 23, 40, 28, 19, 20, 42 },经过筛选法建堆过程后,得到的最
小堆为___ ______。
A)19,20,28,40,23,42 B)19,28,20,40,23,42
C)42,40,28,23,20,19 D)42,28,40,20,23,19
7. 有向图 G 用邻接矩阵 A 存储,则顶点 i 的入度等于 A 中____ _____。
A)第 i 行元素之和 B)第 i 行的元素之和与第 i 列元素之和的乘积
C)第 i 行与第 i 列元素之和 D)第 i 列元素之和
8. 有拓扑排序的图,一定是____ _____。
A)有环图 B)无向图 C)无环有向图 D)无环任意图
9. 有一个有序表为{ 2,11,16,23,32,45,51,62,73,79,80,94,97 },当二分检
索关键码值为 94 的数据元素时,_____ _______次比较后查找成功。
A)1 B)2 C)3 D)4
10. 在待排序的元素序列基本有序的情况下,下面的____________算法效率最高。
A)插入排序 B)选择排序 C)快速排序 D)归并排序
二、 已知某二叉树的前序序列为 ABECDFGHIJ,中序序列为 EBCDAFHIGJ,请完成:
(1) 画出该二叉树;
(2) 将该二叉树转换为对应的森林。 (10 分)