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

数据结构数据结构 应用题应用题 天涯古巷天涯古巷 出品出品 第三章第三章 题型一：表达式求值题型一：表达式求值 按照四则运算加按照四则运算加（+ +） 、减、减（- -） 、乘、乘（* *） 、除、除（/ /）和幂运算和幂运算( ( ) )优先关系的惯例优先关系的惯例，画出对下列算术，画出对下列算术 表达式求值时操作数栈和运算符栈的变化过程：表达式求值时操作数栈和运算符栈的变化过程：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 栈栈 OPNDOPND 栈栈 输入字符输入字符 主要操作主要操作 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# 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# 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,+,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(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 的起始地址；的起始地址； （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 试画出二叉树试画出二叉树 B B，并简述由任意二叉树，并简述由任意二叉树 B B 的前序遍历序列和中序遍历序列求二叉树的前序遍历序列和中序遍历序列求二叉树 B B 的思想方法。的思想方法。 答案：答案： 2 2、试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的 结点序列。结点序列。 A ED CB HGF 题型二：哈夫曼树的构造（画树、计算题型二：哈夫曼树的构造（画树、计算 WPLWPL、初态和终态表） ，设计哈夫曼编码、初态和终态表） ，设计哈夫曼编码 1 1、 假设用于通信的电文仅由假设用于通信的电文仅由 8 8 个字母组成， 字母在电文中出现的频率分别为个字母组成， 字母在电文中出现的频率分别为： 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,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.06+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 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 的存储结构的初态和终态。的存储结构的初态和终态。 答案：答案： 初态初态: : 终态终态: : weightweight 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 1010 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 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, , 12 ) 1(1 = l ，结论成立。，结论成立。 设有设有 n n 个叶子结点时也成立，即个叶子结点时也成立，即12.2.22 ) 1( ) 1( ) 1() 1( 21 =+ + n p l l ll ，现假设，现假设 增加一个叶子结点，这意味着在某叶子结点增加一个叶子结点，这意味着在某叶子结点 p p 上新生两个叶子结点，而结点上新生两个叶子结点，而结点 p p 则成为非叶子结点，则成为非叶子结点， 可见，总结点数增可见，总结点数增 2 2，叶子结点数增，叶子结点数增 1 1。此时，所有叶子结点是原结点除去。此时，所有叶子结点是原结点除去 p p，然后加上两个深度，然后加上两个深度 为为1+ p l的新叶子结点，由此，的新叶子结点，由此， ) 11() 11( ) 1( ) 1() 1( ) 1() 1( 222.22.22 11 21 + + + +pp n pp ll l ll ll 12.2.22 ) 1( ) 1( ) 1() 1( 21 =+= + n p l l ll 则当则当 i=n+1i=n+1 时，也成立，由此即得到证明。时，也成立，由此即得到证明。 第六第六章章 题型一：给定图的逻辑结题型一：给定图的逻辑结构，画出邻接矩阵和邻接表（或反过来考）构，画出邻接矩阵和邻接表（或反过来考） 1 1、已知图所示的有向图，请给出：已知图所示的有向图，请给出： 每个顶点的入度和出度；每个顶点的入度和出度； 邻接矩阵；邻接矩阵； 邻接表；邻接表； 逆邻接表。逆邻接表。 答案：答案： 2 2、已知如图已知如图 6.336.33 所示的无向网，请给出：所示的无向网，请给出： 邻接矩阵；邻接矩阵； 邻接表；邻接表； 最小生成树最小生成树 答案：答案： 645 625 236 379 456755 5553 9554 34 a a b b 4 4 c c 3 3 b b a a 4 4 c c 5 5 d d 5 5 e e 9 9 c c a a 3 3 b b 5 5 d d 5 5 h h 5 5 d d b b 5 5 c c 5 5 e e 7 7 f f 6 6 g g 5 5 h h 4 4 e e b b 9 9 d d 7 7 f f 3 3 f f d d 6 6 e e 3 3 g g 2 2 g g d d 5 5 f f 2 2 h h 6 6 题型二：根据图的逻辑结构或存储结构，写出深度、广度优先搜索遍历结果题型二：根据图的逻辑结构或存储结构，写出深度、广度优先搜索遍历结果 （根据逻辑结构写是唯一的，根据存储结构写不唯一）（根据逻辑结构写是唯一的，根据存储结构写不唯一） 已知图的邻接矩阵如图所示。 试分别画出自顶点已知图的邻接矩阵如图所示。 试分别画出自顶点 1 1 出发进行遍历所得的深度优先生成树和广度优先出发进行遍历所得的深度优先生成树和广度优先 生成树。生成树。 答案：答案： 题型三：根据图的逻辑结构填写最短路径求解过程表，画出最小生成树（计算权值和） ，写出拓扑题型三：根据图的逻辑结构填写最短路径求解过程表，画出最小生成树（计算权值和） ，写出拓扑 排序结果排序结果 有向网如图所示，试用迪杰斯特拉算法求出从顶点有向网如图所示，试用迪杰斯特拉算法求出从顶点 a a 到其他各顶点间的最短路径，完成到其他各顶点间的最短路径，完成下下表表 答案：答案： D 终点 i=1 i=2 i=3 i=4 i=5 i=6 b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e 10 (a,c,e) 10 (a,c,e) f 6 (a,c,f) g 16 (a,c,f,g) 16 (a,c,f,g) 14 (a,c,f,d,g) S 终点集 a,c a,c,f a,c,f,e a,c,f,e,d a,c,f,e,d,g a,c,f,e,d,g,b 第七第七章章 题型一：折半查找过程，画判定树，计算题型一：折半查找过程，画判定树，计算 ASLASL 假定对有序表： （假定对有序表： （3 3，4 4，5 5，7 7，2424，3030，4242，5454，6363，7272，8787，9595）进行折半查找，试回答下列）进行折半查找，试回答下列 问题：问题： 画出描述折半查找过程的判定树；画出描述折半查找过程的判定树； 若查找元素若查找元素 5454，需依次与哪些元素比较？，需依次与哪些元素比较？ 若查找元素若查找元素 9090，需依次与哪些元素比较？，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。假定每个元素的查找概率相等，求查找成功时的平均查找长度。 答案：答案： 先画出判定树如下（注：先画出判定树如下（注：mid=mid= (1+12)/2(1+12)/2 =6=6） ：） ： 3030 5 5 6363 3 3 7 7 42 42 8787 4 4 24 24 5454 72 72 9595 查找元素查找元素 5454，需依次与，需依次与 30, 63, 42, 54 30, 63, 42, 54 元素比较；元素比较； 查找元素查找元素 9090，需依次与，需依次与 30, 63,87, 9530, 63,87, 95 元素比较；元素比较； 求求 ASLASL 之前，需要统计每个元素的查找次数。判定树的前之前，需要统计每个元素的查找次数。判定树的前 3 3 层共查找层共查找 1 12 22 24 43=173=17 次；次； 但最后一层未满，不能用但最后一层未满，不能用 8 84 4，只能用，只能用 5 54=204=20 次，次， 所以所以 ASLASL1/121/12（17172020）37/1237/123.083.08 题型二：二叉排序树的创建，查找，计算题型二：二叉排序树的创建，查找，计算 ASLASL 已知如下所示长度为已知如下所示长度为 1212 的表： （的表： （Jan, Feb, Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecDec） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树， 画出插入完成之后的二叉排序试按表中元素的顺序依次插入一棵初始为空的二叉排序树， 画出插入完成之后的二叉排序 树，并求其在等概率的情况下查找成功的平均查找长度。树，并求其在等概率的情况下查找成功的平均查找长度。 若对表中元素先进行排序构成有序表， 求在等概率的情况下对此有序表进行折半查找时查若对表中元素先进行排序构成有序表， 求在等概率的情况下对此有序表进行折半查找时查 找成功的平均查找长度。找成功的平均查找长度。 答案：答案： 题型三：已知哈希表长度和哈希函数，利用线性探测法和链地址法解决冲突，构造哈希表，计算题型三：已知哈希表长度和哈希函数，利用线性探测法和链地址法解决冲突，构造哈希表，计算 ASLASL 1 1、 （线性探测）、 （线性探测）设哈希表的地址范围为设哈希表的地址范围为 0 01717，哈希函数为：，哈希函数为：H H（keykey）=key%16=key%16。用线性探测法处。用线性探测法处 理冲突，输入关键字序列： （理冲突，输入关键字序列： （1010，2424，3232，1717，3131，3030，4646，4747，4040，6363，4949） ，构造哈希表，试） ，构造哈希表，试 回答下列问题：回答下列问题： 画出哈希表的示意图；画出哈希表的示意图； 若查找关键字若查找关键字 6363，需要依次与哪些关键字进行比较？，需要依次与哪些关键字进行比较？ 若查找关键字若查找关键字 6060，需要，需要依次与哪些关键字比较依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 答案：答案： 画表如下：画表如下： 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 1313 1414 1515 1616 1717 3232 1717 6363 4949 2424 4040 1010 3030 3131 4646 4747 查找查找 63,63,首先要与首先要与 H(63)=63%16=15H(63)=63%16=15 号单元内容比较，即号单元内容比较，即 6363 与与 3131 比较比较 , ,不匹配不匹配; ; 然后顺移，与然后顺移，与 46,47,32,17,6346,47,32,17,63 相比，一共比较了相比，一共比较了 6 6 次！次！ 查找查找 60,60,首先要与首先要与 H(6H(60 0)=6)=60 0%16=1%16=12 2 号单元内容比较，但因为号单元内容比较，但因为 1212 号单元为空（应当有空标号单元为空（应当有空标 记） ，所以应当只比较这一次即可。记） ，所以应当只比较这一次即可。 对于黑色数据元素，各比较对于黑色数据元素，各比较 1 1 次；共次；共 6 6 次；次； 对红色元素则各不相同，要统计移位的位数。 “对红色元素则各不相同，要统计移位的位数。 “6363”需要”需要 6 6 次， “次， “4949”需要”需要 3 3 次， “次， “4040”需要”需要 2 2 次， “次， “4646”需要”需要 3 3 次， “次， “4747”需要”需要 3 3 次，次， 所以所以 ASL=1/11ASL=1/11（6 62 23 33+63+6）23/1123/11 2 2、 （链地址法）（链地址法）设哈希函数设哈希函数 H H（K K）=3 K mod 11=3 K mod 11，哈希地址空间为，哈希地址空间为 0 01010，对关键字序列（，对关键字序列（3232， 1313，4949，2424，3838，2121，4 4，1212） ，按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查） ，按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查 找成功时和查找失败时的平均查找长度找成功时和查找失败时的平均查找长度 ASLsuccASLsucc 和和 ASLunsuccASLunsucc。 线性探测法；线性探测法； 链地址法。链地址法。 答案：答案： 散列地址散列地址 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 关键字关键字 4 4 1212 4949 3838 1313 2424 3232 2121 比较次数比较次数 1 1 1 1 1 1 2 2 1 1 2 2 1 1 2 2 ASLsucc =ASLsucc =（1+1+1+2+1+2+1+21+1+1+2+1+2+1+2）/8=11/8/8=11/8 ASLunsucc=ASLunsucc=（1+2+1+8+7+6+5+4+3+2+11+2+1+8+7+6+5+4+3+2+1）/11=40/11/11=40/11 ASLsucc =ASLsucc =（1 1*5*5+ +2*32*3）/8=11/8/8=11/8 ASLunsucc=ASLunsucc= （ 1+2+1+1+2+1+2 2+ +3 3+ +1 1+ +3 3+ +1 1+ +3+13+1+ +1 1 ） /11=/11=1919/11/11 第八第八章章 题型一：已知整数序列，写出直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简题型一：已知整数序列，写出直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简 单选择排序、归并排序的排序过程（考两到三种） ，并会分析时空复杂度、稳定性及适用情况单选择排序、归并排序的排序过程（考两到三种） ，并会分析时空复杂度、稳定性及适用情况 1 1、设待排序的关键字序列为设待排序的关键字序列为1212，2 2，1616，3030，2828，1010，16*16*，2020，6 6，1818，试分别写出使用以下，试分别写出使用以下 排序方法，每趟排序结束后关键字序列的状态。排序方法，每趟排序结束后关键字序列的状态。 直接插入排序直接插入排序 折半插入排序折半插入排序 希尔排序（增量选取希尔排序（增量选取 5 5，3 3，1 1） 冒泡排序冒泡排序 快速排序快速排序 简单选择排序简单选择排序 二路归并排序二路归并排序 答案：答案：直接插入排序直接插入排序 2 12 16 30 28 10 162 12 16 30 28 10 16* * 20 6 18 20 6 18 2 12 16 30 28 10 162 12 16 30 28 10 16* * 20 6 18 20 6 18 2 12 16 30 28 10 162 12 16 30 28 10 16* * 2020 6 18 6 18 2 12 16 28 30 10 162 12 16 28 30 10 16* * 20 6 18 20 6 18 2 10 12 16 28 30 162 10 12 16 28 30 16* * 20 6 18 20 6 18 2 10 12 16 162 10 12 16 16* * 28 30 20 6 18 28 30 20 6 18 2 10 12 16 162 10 12 16 16* * 20 28 30 6 18 20 28 30 6 18 2 6 10 12 16 162 6 10 12 16 16* * 20 28 30 18 20 28 30 18 2 6 10 12 16 162 6 10 12 16 16* * 18 20 28 3018 20 28 30 折半插入排序折半插入排序 排序过程同排序过程同 希尔排序（增量选取希尔排序（增量选取 5 5，3 3，1 1） 10 2 16 6 18 12 1610 2 16 6 18 12 16* * 20 30 28 20 30 28 （增量选取（增量选取 5 5） 6 2 12 10 6 2 12 10 18 16 1618 16 16* * 20 30 28 20 30 28 （增量选取（增量选取 3 3） 2 6 10 12 16 162 6 10 12 16 16* * 18 20 28 30 18 20 28 30 （增量选取（增量选取 1 1） 冒泡排序冒泡排序 2 12 16 28 10 162 12 16 28 10 16* * 20 6 18 30 20 6 18 30 2 12 16 10 162 12 16 10 16* * 20 6 18 28 30 20 6 18 28 30 2 12 10 16 162 12 10 16 16* * 6 18 20 28 30 6 18 20 28 30 2 10 12 16 6 162 10 12 16 6 16* * 18 20 28 30 18 20 28 30 2 10 12 6 16 162 10 12 6 16 16