《北林 数据结构期末考试(四) 应用题》由会员分享，可在线阅读，更多相关《北林 数据结构期末考试(四) 应用题（15页珍藏版）》请在金锄头文库上搜索。
1、 数据结构数据结构 应用题应用题 天涯古巷天涯古巷 出品出品 第三章第三章 题型一：表达式求值题型一：表达式求值 按照四则运算加按照四则运算加（+ +） 、减、减（- -） 、乘、乘（* *） 、除、除（/ /）和幂运算和幂运算( ( ) )优先关系的惯例优先关系的惯例，画出对下列算术，画出对下列算术 表达式求值时操作数栈和运算符栈的变化过程：表达式求值时操作数栈和运算符栈的变化过程：A A- -B BC/D+C/D+EEF F 解：解：BC=G G/D=H ABC=G G/D=H A- -H=I EF=J I+J=KH=I EF=J I+J=K 步骤步骤 OPTROPTR 栈栈 OPNDOP
2、ND 栈栈 输入字符输入字符 主要操作主要操作 1 1 # # A A- -B*C/D+EF#B*C/D+EF# PUSH(PUSH(OPND,A)OPND,A) 2 2 # # A A - -B*C/D+EF#B*C/D+EF# PUSH(OPTR,PUSH(OPTR,- -) ) 3 3 # #- - A A B B*C/D+EF#*C/D+EF# PUSH(OPND,B)PUSH(OPND,B) 4 4 # #- - A BA B * *C/D+EF#C/D+EF# PUSH(OPTR,*)PUSH(OPTR,*) 5 5 # #- -* * A BA B C C/D+EF#/D+EF#
3、 PUSH(OPND,C)PUSH(OPND,C) 6 6 # #- -* * A B CA B C / /D+EF#D+EF# Operate(B,*,C)Operate(B,*,C) 7 7 # #- - A GA G /D+EF#/D+EF# PUSH(OPTR,/)PUSH(OPTR,/) 8 8 # #- -/ / A GA G D D+EF#+EF# PUSH(OPND,D)PUSH(OPND,D) 9 9 # #- -/ / A G DA G D + +EF#EF# Operate(G,/,D)Operate(G,/,D) 1010 # #- - A HA H +EF#+EF#
4、Operate(A,Operate(A,- -,H),H) 1111 # # I I +EF#+EF# PUSH(OPTR,+)PUSH(OPTR,+) 1212 #+#+ I I E EF#F# PUSH(OPND,E)PUSH(OPND,E) 1313 #+#+ I EI E F#F# PUSH(OPTR,)PUSH(OPTR,) 1414 #+#+ I EI E F F# # PUSH(OPND,F)PUSH(OPND,F) 1515 #+#+ I E FI E F # # Operate(E,F)Operate(E,F) 1616 #+#+ I JI J # # Operate(I,+
5、,J)Operate(I,+,J) 1717 # # K K # # RETURNRETURN 题型二：汉诺塔时间复杂度的分析及证明题型二：汉诺塔时间复杂度的分析及证明 汉诺塔问题的递归算法的时间复杂度是什么？请给出答案并且给予证明。汉诺塔问题的递归算法的时间复杂度是什么？请给出答案并且给予证明。 解：解：时间复杂度时间复杂度 T(nT(n) )=O(2=O(2 n n) )，证明如下 ，证明如下 已知：已知：f(1)=1f(1)=1，f(n)=2f(nf(n)=2f(n- -1)+1 1)+1 所以所以：f(n)+1=2(f(nf(n)+1=2(f(n- -1)+1)1)+1) f(n)=f
6、(n)= 2 2 n n - -1 1 （2 2 n n - -1 1 为至少执行移动操作的次数） 为至少执行移动操作的次数） T(n)=O(T(n)=O(2 2 n n) ) 故：故：得证得证 第四第四章章 题型一：数组地址的计算题型一：数组地址的计算 设有二维数组设有二维数组 A(6A(68)8)，每个元素占，每个元素占 6 6 字节存储，顺序存放，字节存储，顺序存放，A A 的起地址为的起地址为 10001000，计算：，计算： （1 1）数组）数组 A A 的体积（即存储量） ；的体积（即存储量） ； （2 2）数组的最后一个元素）数组的最后一个元素 A57A57 的起始地址；的起始地
7、址； （3 3）按行优先存放时，元素）按行优先存放时，元素 A14A14 的起始地址；的起始地址； （4 4）按列优先存放时，元素）按列优先存放时，元素 A47A47 的起始地址。的起始地址。 第五第五章章 题型一：由二叉树的中序遍历和前（后）序遍历，画出该二叉树题型一：由二叉树的中序遍历和前（后）序遍历，画出该二叉树 1 1、给定二叉树的两种遍历序列，分别是：给定二叉树的两种遍历序列，分别是： 前序遍历序列：前序遍历序列：A B D F C E G HA B D F C E G H； 中序遍历序列：中序遍历序列：B F D A G E H CB F D A G E H C 试画出二叉树试画出
8、二叉树 B B，并简述由任意二叉树，并简述由任意二叉树 B B 的前序遍历序列和中序遍历序列求二叉树的前序遍历序列和中序遍历序列求二叉树 B B 的思想方法。的思想方法。 答案：答案： 2 2、试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的 结点序列。结点序列。 A ED CB HGF 题型二：哈夫曼树的构造（画树、计算题型二：哈夫曼树的构造（画树、计算 WPLWPL、初态和终态表） ，设计哈夫曼编码、初态和终态表） ，设计哈夫曼编码 1 1、 假设用于通信的电文仅由假设用于通信的电文仅由 8 8 个字母组成， 字母在电文中出现
9、的频率分别为个字母组成， 字母在电文中出现的频率分别为： 0.070.07， 0.190.19， 0.020.02， 0.060.06，0.320.32，0.030.03，0.210.21，0.100.10。 试为这试为这 8 8 个字母设计赫夫曼编码。个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。对于上述实例，比较两种方案的优缺点。 答案：方案答案：方案 1 1；哈夫曼编码；哈夫曼编码 先将概率放大先将概率放大 100100 倍，以方便构造哈夫曼树。倍，以方便构造哈夫曼树。 w=7,19,2,6,
10、32,3,21,10w=7,19,2,6,32,3,21,10，按哈夫曼规则： 【，按哈夫曼规则： 【 （2,32,3） ，） ，6 6, (, (7,107,10) )】, , 19,19, 21,21, 3232 （100100） （4040） （6060） 19 21 19 21 32 32 （2828） （1717） （1111） 7 7 10 10 6 6 （5 5） 2 2 3 3 方案比较：方案比较： 方案方案 1 1 WPLWPL= =2 2* *(0.19+0.32+0.21)+4(0.19+0.32+0.21)+4* *(0.07+0.06+0.10)+5(0.07+0.0
11、6+0.10)+5* *(0.02+0.03)=1.44+0.92+0.25=2.61(0.02+0.03)=1.44+0.92+0.25=2.61 方案方案 2 2 WPLWPL3 3* *(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码结论：哈夫曼编码优于等长二进制编码 字母编号 对应编码 出现频率 1 000 0.07 2 001 0.19 3 010 0.02 4 011 0.06 5 100 0.32 6 101 0.03 7
12、 110 0.21 8 111 0.10 字母编号 对应编码 出现频率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 11111 0.03 7 01 0.21 8 1101 0.10 2 2、已知下列字符已知下列字符 A A、B B、C C、D D、E E、F F、G G 的权值分别为的权值分别为 3 3、1212、7 7、4 4、2 2、8 8，1111，试填写出其对应，试填写出其对应 哈夫曼树哈夫曼树 HTHT 的存储结构的初态和终态。的存储结构的初态和终态。 答案：答案： 初态初态: : 终态终态: : weight
13、weight parentparent lchlchildild rchrchildild 1 1 3 3 8 8 0 0 0 0 2 2 1212 1212 0 0 0 0 3 3 7 7 1010 0 0 0 0 4 4 4 4 9 9 0 0 0 0 5 5 2 2 8 8 0 0 0 0 6 6 8 8 1010 0 0 0 0 7 7 1111 1111 0 0 0 0 8 8 5 5 9 9 5 5 1 1 9 9 9 9 1111 4 4 8 8 1010 1515 1212 3 3 6 6 1111 2020 1313 9 9 7 7 1212 2727 1313 2 2 10
14、10 1313 4747 0 0 1111 1212 weightweight p parentarent lchlchildild rchrchildild 1 1 3 3 0 0 0 0 0 0 2 2 1212 0 0 0 0 0 0 3 3 7 7 0 0 0 0 0 0 4 4 4 4 0 0 0 0 0 0 5 5 2 2 0 0 0 0 0 0 6 6 8 8 0 0 0 0 0 0 7 7 1111 0 0 0 0 0 0 8 8 0 0 0 0 0 0 9 9 0 0 0 0 0 0 1010 0 0 0 0 0 0 1111 0 0 0 0 0 0 1212 0 0 0 0
15、 0 0 1313 0 0 0 0 0 0 题型三：利用二叉树的性质对某些问题进行证明题型三：利用二叉树的性质对某些问题进行证明 对于那些所有非叶子结点均含有左右子数的二叉树：对于那些所有非叶子结点均含有左右子数的二叉树： (1) (1) 试问：有试问：有 n n 个叶子结点的树中共有多少个结点？个叶子结点的树中共有多少个结点？ (2) (2) 试证明：试证明： () 12 1 1 = = n i li ，其中，其中 n n 为叶子结点的个数，为叶子结点的个数， i l表示第表示第 i i 个叶子结点所在的层次个叶子结点所在的层次 （设根节点所在层次为（设根节点所在层次为 1 1） 。） 。 解：解： （1 1）总结点数为）总结点数为 1 21n+，其中，其中 1 n为非叶子结点数，则叶子结点数为为非叶子结点数，则叶子结点数为1 1+ = nn，所以总，所以总 结点数为结点数为12 n 。 （2 2）用归纳法证明。）用归纳法证明。 i=1i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，1 1 =l, ,
