数据结构复习题
一． 判断题（10分）
二．填空题（每题1分，共15-20分）
三．选择题（每题1分，共15-20分）
四．应用题（每题5分，共30-35分）
1． 根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
B=（D，R），其中：
D={40，30，20，60，50，80，70，10}， R={<30,20>,<30,60>,<20,40>,<60,50>, <60,70>,<60,80>,<70,10>}
解：
30 20
60 40 50 70 80 图正确4分
10 属于树结构 数据结构正确1分 2．利用栈求：A*(B+C)*D-E的后缀表达式。 解：A B C + * D * E -
3． 画出表达式：（A+B/C-D）*（E*（F+G））的标识符树，并求它们的后缀表达式。解：
* ˉ *
+ DE +
A / F G
B C 图正确3分
后缀表达式：A B C / + D – E F G + * * 表达式正确2分
4． 设稀疏矩阵A5╳5，如图所示。
?6?0??0??0??00?1000300000040?30??0?0??2?0??（1）试给出A的三元组表； （2）写出三元组表的C语言描述。
解：（1） （2）三元组表的C语言描述：
i 0 0 1 2 3 4
5． 某二叉树的结点数据采用顺序存储，其存储结构如图所示。（与P169(7)类似） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F B D J H ^ ^ C （1）画出该二叉树；
（2）写出结点值为D的父结点及左、右子树； （3）写出二叉树按前序遍历的序列。
解：（1） E
K A D C F H ^ ^ ^ G I ^ ^ ^ ^ K j 0 2 1 3 4 3 v 6 3 -1 4 2 -3 #define SMAX 25 struct SPNode {
int i,j,v; };
struct sparmatrix {
int rows,cols,terms;
SPNode data[SMAX]; };
B J G I
（2） D的父结点为A，D的左子树为C，D的右子树为空 （3） 前序遍历的序列：E A B D C K F J H G I
6．把树转换为二叉树（5分）
①
② ③ ④
⑤ ⑥ ⑦ ⑧ ⑨ ⑩
解： ①
②
⑤ ③
⑥ ⑦ ④ ⑧ ⑨ ⑩
7. 把图三-6-3所示的森林转换为二叉树，并指出它的高度。
解：
高度为6
A B C D G F H J M 图三-6-3
I L K E （8）某二叉树的存储如下：
lchild data rchild
1 0 J 0 2 0 H 0 3 2 F 0 4 3 D 9 5 7 B 4 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。
① 画出该二叉树。
② 写出该树的前序遍历的结点序列。 解： ① 根据存储结构画出二叉树： A
H J ② 前序遍历的结点序列：A B C E D F H G I J
（9）给定如图7-41所示二叉树T，请画出
与其对应的中序线索二叉树。
40 28 B C E F I D G 25 33 60 08 54 55 图7-41 二叉树6 解：中序遍历序列：55 40 25 60 28 08 33 54
中序线索二叉树：
NULL 4055600854252833NULL 10. 已知二叉树的后序遍历为：RSBECFKLMDA， 中序遍历为：RBSCEAFDLKM 试画出二叉树。（5分）
解： A 评分标准：每画对一层1分
C D
B E F M
R S L
K 11.
12．给定一个权集W={4，2，6，15，14，20，9，17}，请画出相应的赫哈夫曼树,并计算其带权路径长度WPL。 解：（1） 树画对3分
20 3717 9 6 21 87 50 29 15 12 146
2 4（2）
WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229 WPL公式对1分，答案正确1分，共2分