2007级《数据结构》期末考试题答案
一、 单项选择题（每小题2分，共30分）
1.D 2.C 3.B 4.A 5.D 6.C 7.B 8.A 9. D 10.D 11.B 12.A 13.D 14.C 15.B
二、填空题（每空1分，共14分）
1.相同属性、前驱、后继
2.∟㏒22n」+1 、 2n-1
3.数组
4.栈顶 栈底
5.3 2
6.邻接矩阵、邻接表、边集数组
7.0
三、名词解释（每题4分，共16分。）
1．数据结构：数据+结构，指的是数据之间的相互关系，即数据的组织形式
2. 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
3.哈夫曼树：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
4.最小生成树：最小生成树
四、简答题（每题4分，共16分。）
1.正确性、稳健性、可读性、时间复杂度、空间复杂度
2.S－>right=P->right;
P->left->right=S;
S->right=P;
P-left=S.
3.树的性质：1）树中的结点数等于所有结点度数之和；
_ 2）度为K的树中第i层上至多有Ki-1个结点（i>=1）;
_ 3)深度为h的K叉树上至多有(kh-1)/(k-1) 个结点；
4）具有n个结点的k叉树的最小深度为 
。
4.返回N个数的阶乘之和；O（n）。
五、
1.void_ Preorder(BinTree__ T)
____ {
______ if(T) {
__________ Printf(“%c”,T→data);
Preorder(T→lchild);
__________ Preorder(T→rchild);
_______ }
____ }
2.
.
A
B
E
C
F
D
G
H
后序ABCDEFGH
3.构造的哈夫曼树
11
6
8
10
14
218
29
50
15
5
3
2
7
树的带权路径长度WPL=131
4.（1）
1
5
4
2
3
6
10
4
9
12
5
6
0
（2）（V0，V1）6，（V1，V6）4,( V2,V6)9,(V2,V3)5,(V3,V4)10,(V0,V5)12
(3)_ （V1，V6）4，(V2,V3)5，（V0，V1）6，( V2,V6)9，(V3,V4)10，(V0,V5)12