数据结构B卷.doc

2010-2011学年第2学期考试试题（B）卷
课程名称 《数据结构》 任课教师签名
出题教师签名 审题教师签名
考试方式 （ 闭）卷 性表全部n个元素的值 D) 输出值为x的元素的序号
4个元素a、b、c、d依次进栈, 则出栈的序列不可能是_____。
A) abcd B) dcba C) cabd D) acdb
"abcd"有_____个子串。
A) 4 B) 5 C) 9 D) 10
在线索二叉树中, 判断指针p所指结点没有左子树的条件是_____。
A) p->lch == NULL B) p->ltag == 1
C) p->lch == NULL＆＆ p->ltag == 1 D) 以上都不对
图2所示表达式二叉树的后缀表示式为_____。
A) a * b + c - d / e B) + * a b / - c d e C) a b * c d - e / + D) a b * + c d - e /
+
*
a
b
/
c
d
e
-
图2 表达式树
下面关于树和二叉树的说法中, _____是正确的。
A) 度为m的树第i层至多有mi - 1个结点
B) 二叉树只能采用链式存储结构
C) 二叉树就是度为2的树
D) 度为2的树转换为二叉树后, 形态完全一样
n个叶子结点的哈夫曼树, 结点总数为_____。
A) 不确定 B) 2n - 1 C) 2n D) 2n + 1
无向图的邻接矩阵一定是_____。
A) 对角矩阵 B) 上三角矩阵 C) 下三角矩阵 D) 对称矩阵
采用邻接矩阵存储的图的广度优先遍历算法类似于二叉树的_____算法。
A) 先根遍历 B) 中根遍历 C) 后根遍历 D) 按层遍历
画图题(本大题共3小题, 每小题5分, 共15分)
将图3所示的树转换成二叉树, 请画出对应的二叉树。
A
B
C
D
F
G
E
H
A
B
D
E
G
C
F
图3 树的转换
图4 线索二叉树
将图4所示的二叉树按先根遍历的次序线索化, 请画出对应的先根线索二叉树。
按图5所示无向图, 请画出Kruskal算法求最小生成树的过程。
2
5
1
3
6
4
7
8
2
1
2
3
1
6
1
2
6
3
3
1
5
图5 最小生成树
分析题(本大题共4小题, 每小题5分, 共20分)
若线性表L = {2, 9, 3, 0, 5, 1, 7, 6, 8, 4}, 请写出用冒泡排序法按升序排序时, 线性表变化过程的前5步。
按图6所示有向图, 请写出Dijkstra算法求从顶点A出发到其余顶点的最短路径的计算过程。
F
A
B
C
D
E
G
1
1
1
4
4
3
2
1
1
1
1
3
1
2
3
4
5
6
7
8
9
图6 最短路径
图7 拓扑排序
对图7所示的有向无环图进行拓扑排序, 请写出至少5种排序结果。
已知散列表表长为12, 地址计算公式为
H(k) =