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

数据结构
应用题













天涯古巷出品
第三章
题型一:表达式求值
按照四则运算加(+)、减(-)、乘(*)、除(/)和幂运算(^)优先关系的惯例,画出对下列算术
表达式求值时操作数栈和运算符栈的变化过程:A-B×C/D+E^F
解:BC=G G/D=H A-H=I E^F=J I+J=K
步骤 OPTR 栈 OPND 栈输入字符主要操作
1 # A-B*C/D+E^F# PUSH(OPND,A)
2 # A -B*C/D+E^F# PUSH(OPTR,-)
3 #- A B*C/D+E^F# PUSH(OPND,B)
4 #- A B *C/D+E^F# PUSH(OPTR,*)
5 #-* A B C/D+E^F# PUSH(OPND,C)
6 #-* A B C /D+E^F# Operate(B,*,C)
7 #- A G /D+E^F# PUSH(OPTR,/)
8 #-/ A G D+E^F# PUSH(OPND,D)
9 #-/ A G D +E^F# Operate(G,/,D)
10 #- A H +E^F# Operate(A,-,H)
11 # I +E^F# PUSH(OPTR,+)
12 #+ I E^F# PUSH(OPND,E)
13 #+ I E ^F# PUSH(OPTR,^)
14 #+^ I E F# PUSH(OPND,F)
15 #+^ I E F # Operate(E,^,F)
16 #+ I J # Operate(I,+,J)
17 # K # RETURN

题型二:汉诺塔时间复杂度的分析及证明
汉诺塔问题的递归算法的时间复杂度是什么?请给出答案并且给予证明。
n
解:时间复杂度 T(n)=O(2 ),证明如下
已知:f(1)=1,f(n)=2f(n-1)+1
所以:f(n)+1=2(f(n-1)+1)
n n
f(n)= 2 -1 (2 -1 为至少执行移动操作的次数)
n
T(n)=O(2 )
故:得证
第四章
题型一:数组地址的计算
设有二维数组 A(6×8),每个元素占 6 字节存储,顺序存放,A 的起地址为 1000,计算:
(1)数组 A 的体积(即存储量);
(2)数组的最后一个元素 A57 的起始地址;
(3)按行优先存放时,元素 A14 的起始地址;
(4)按列优先存放时,元素 A47 的起始地址。






第五章
题型一:由二叉树的中序遍历和前(后)序遍历,画出该二叉树
1、给定二叉树的两种遍历序列,分别是:
前序遍历序列:A B D F C E G H; 中序遍历序列:B F D A G E H C
试画出二叉树 B,并简述由任意二叉树 B 的前序遍历序列和中序遍历序列求二叉树 B 的思想方法。
答案:
A

B C

D E

F G H

2、试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的
结点序列。
题型二:哈夫曼树的构造(画树、计算 WPL、初态和终态表),设计哈夫曼编码
1、假设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为:,,,
,,,,。
①试为这 8 个字母设计赫夫曼编码。
②试设计另一种由二进制表示的等长编码方案。
③对于上述实例,比较两种方案的优缺点。
答案:方案 1;哈夫曼编码
先将概率放大 100 倍,以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10},按哈夫曼规则:【[(2,3), 6], (7,10)】, ……19, 21, 32

(100)
(40) (60)
19 21 32 (28)
(17) (11)
7 10 6 (5)
2 3

方案比较:
字母编号对应编码出现频率字母编号对应编码出现频率
1 1100 1 000
2 00 2 001

3 11110 3 010

4 1110 4 011

5 10 5 100

6 11111 6 101

7 01 7 110

8 1101 8 1