北林数据结构期末考试(四)应用题.doc

北林数据结构期末考试(四)应用题.doc数据结构
应用题
天涯古巷 出品
第三章
题型一：表达式求值
按照四则运算加(+)、减(-)、乘(* )、除(/ )和幂运算(勺优先关系的惯例，画出对下列算术
表达式求值时操作数栈和运算符栈的变化过程： A-BX C/D44++=
方案2
WPIl3*(+++++++)=3
结论：哈夫曼编码优于等长二进制编码
2、已知下列字符 A B C D E、F、G 的权值分别为 3、12、7、4、2、8, 11，试填写出其对应
哈夫曼树HT的存储结构的初态和终态。
答案：
终态:
初态:
weight
parent
lchild
rchild
1
3
0
0
0
2
12
0
0
0
3
7
0
0
0
4
4
0
0
0
5
2
0
0
0
6
8
0
0
0
7
11
0
0
0
8
0
0
0
9
0
0
0
10
0
0
0
11
0
0
0
12
0
0
0
13
0
0
0
weight
parent
Ichild
rchild
1
3
8
0
0
2
12
12
0
0
3
7
10
0
0
4
4
9
0
0
5
2
8
0
0
6
8
10
0
0
7
11
11
0
0
8
5
9
5
1
9
9
11
4
8
10
15
12
3
6
11
20
13
9
7
12
27
13
2
10
13
47
0
11
12
题型三：利用二叉树的性质对某些问题进行证明 对于那些所有非叶子结点均含有左右子数的二叉树：
试问：有 n个叶子结点的树中共有多少个结点？
n
试证明： »2-(li-1) = 1，其中n为叶子结点的个数， |i表示第i个叶子结点所在的层次
(设根节点所在层次为 1) o
解：(1)总结点数为 1+2口，其中ni为非叶子结点数，则叶子结点数为 n = ni +1，所以总
结点数为2n - 1 o
(2)用归纳法证明。
i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点， |1 = 1,
2-(l1-1) =1,结论成立。
设有 n 个叶子结点时也成立，即 2-(l1-1)+2-(l2-1)+... + 2-(lp-1)+...+ 2-(ln+1) =1,现假设
增加一个叶子结点，这意味着在某叶子结点 p上新生两个叶子结点，而结点 p则成为非叶子结点，
可见，总结点数增 2,叶子结点数增 1。此时，所有叶子结点是原结点除去 p,然后加上两个深度
为lp +1的新叶子结点，由此，
-(l1-1) - (l2- 1) -(lp-1-1) -(lp + 1-1) - (ln +1) -(lp + 1-1) -dp"1)
2 + 2 +... + 2 + 2 +... + 2 + 2 +2
-(l1-1) -(l2-1) -山-1) -(ln+1)
=2 +2 +... + 2 +...+ 2 =1
则当i=n+1时，也成立，由此即得到证明。
0） ⑷連牺^
13 4 5(.
2、已知如图 ，请给出:
邻接矩阵；
邻接表；
最小生成树
答案:
①
第六章
题型一：给定图的逻辑结构，画岀邻接矩阵和邻接表（或反过来考）
1已知图所示的有向图，请给出:
每个顶点的入度和出度；
邻接矩阵；
邻接表；
逆邻接表。
?^
4
3
CO
CO
CO
CO
CO?
?,
?
?4
CO
5
5
9
CO
CO
CO ■
?
?3
5
CO
5
CO
CO
CO
5?
?
?
?s
5
5
CO
7
6
5
4?
?s
9
CO
7
CO
3
CO
CO?
?
?
?^
CO
CO
6
3
CO
2
CO?
?
OO
CO
CO
5
CO
2
CO
6?
?
?
?O
CO
5
4
CO
CO
6
CO?
答案：
b
4
a
4
a
3
b
5
b
9
d
6
d
5
T
T
T
T