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

1、数据结构应用题天涯古巷 出品第三章题型一：表达式求值按照四则运算加(+)、减(-)、乘(* )、除(/ )和幂运算(勺优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-BX C/D+EAF解：BC=G G/D=H A-H=l EAF=J l+J=K步骤OPTR 栈OPND 栈输入字符主要操作1#A-B*C/D+EAF#PUSH(OPND,A)2#A-B*C/D+EAF#PUSH(OPTR,-)3#-AB*C/D+EAF#PUSH(OPND,B)4#-A B*C/D+EAF#PUSH(OPTR,*)5#-*A BC/D+EAF#PUSH(OPND,C)6#-*A B C

2、/D+EAF#Operate(B,*,C)7#-A G/D+EAF#PUSH(OPTR,/)8#-/A GD+EAF#PUSH(OPND,D)9#-/A G D+EAF#Operate(G,/,D)10#-A H+EAF#Operate(A,-,H)11#I+EAF#PUSH(OPTR,+)12#+IEAF#PUSH(OPND,E)13#+I EAF#PUSH(OPTR,a)14#+aI EF#PUSH(OPND,F)15#+aI E F#Operate(E,A,F)16#+I J#Operate(I,+,J)17#K#RETURN题型二：汉诺塔时间复杂度的分析及证明汉诺塔问题的递归算法的时间

3、复杂度是什么？请给岀答案并且给予证明 解：时间复杂度T(n)=0(2 )，证明如下已知：f(1)=1 , f(n)=2f(n-1)+1所以：f(n)+1=2(f(n-1)+1)f(n)= 2 n -1(2 n -1为至少执行移动操作的次数)nT(n)=O(2)故：得证第四章题型一：数组地址的计算设有二维数组 A(6 8)，每个元素占6字节存储，顺序存放，A 的起地址为1000,计算:(1) 数组 A的体积(即存储量)(2) 数组的最后一个元素(3) 按行优先存放时，元素(4) 按列优先存放时，元素A57的起始地址；A14的起始地址;A47的起始地址。第五章题型一：由二叉树的中序遍历和前(后)序

4、遍历，画岀该二叉树1、给定二叉树的两种遍历序列，分别是：前序遍历序列：A B D F C E G H ; 中序遍历序列：B F D A G E H CB的前序遍历序列和中序遍历序列求二叉树2、试写岀如图所示的二叉树分别按先序、中序、后序遍历时得到的 结点序列。KB的思想方法。题型二：哈夫曼树的构造（画树、计算WPL初态和终态表），设计哈夫曼编码1、假设用于通信的电文仅由8个字母组成， 字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 试为这 8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方

5、案的优缺点。答案：方案1;哈夫曼编码先将概率放大 100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10 ，按哈夫曼规则:【(2,3)，6, (7,10)】,19, 21,3223字母编号对应编码出现频率j111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案比较:字母编号对应编码出现频率110000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1WPL=2*(0.19+0.32+0.21)+4*(0.07+0.06

6、+0.10)+5*(0.02+0.03)=1.44+0.92+0.25=2.61方案2WPIl3*(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码2、已知下列字符 A B C DE、F、G的权值分别为3、12、7、4、2、8,11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。答案：终态:初态:weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000weightparentIchildrchild1

7、3800212120037100044900528006810007111100859519911481015123611201397122713210134701112题型三：利用二叉树的性质对某些问题进行证明 对于那些所有非叶子结点均含有左右子数的二叉树：(1) 试问：有 n个叶子结点的树中共有多少个结点？n(2) 试证明：2-(li-1) = 1，其中n为叶子结点的个数，|i表示第i个叶子结点所在的层次(设根节点所在层次为1) o解：(1)总结点数为1+2口，其中ni为非叶子结点数，则叶子结点数为n = ni +1，所以总结点数为2n - 1 o(2)用归纳法证明。i=1，说明二叉树只有

8、一个叶子结点，则整棵树只有一个根结点，|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)-dp1)2 + 2 +. + 2 + 2 +. + 2 + 2 +

9、2-(l1-1)-(l2-1)-山-1)-(ln+1)=2 +2 +. + 2 +.+ 2 =1则当i=n+1时，也成立，由此即得到证明。0）連牺13 4 5(.2、已知如图 6.33所示的无向网，请给出: 邻接矩阵； 邻接表； 最小生成树答案:第六章题型一：给定图的逻辑结构，画岀邻接矩阵和邻接表（或反过来考）1已知图所示的有向图，请给出: 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。?43COCOCOCOCO?,?4CO559COCOCO ?35CO5COCOCO5?s55CO7654?s9CO7CO3COCO?COCO63CO2CO?OOCOCO5CO2CO6?OCO54COC

10、O6CO?答案：b4a4a3b5b9d6d5TTTTTTTTTTTTc3c5b5c5d7e3f2TTTTTTd5d5e7f3g2h6TTTZd5丄Tg5h4题型二：根据图的逻辑结构或存储结构，写岀深度、广度优先搜索遍历结果（根据逻辑结构写是唯一的，根据存储结构写不唯一）已知图的邻接矩阵如图所示。试分别画岀自顶点 1岀发进行遍历所得的深度优先生成树和广度优先生成树。lj()tt10 0 0(j(I(III (.110()0 0(1fl00 (t 0答案：深度优先生成树广度优先生成树题型三：根据图的逻辑结构填写最短路径求解过程表，画岀最小生成树（计算权值和），写岀拓扑排序结果有向网如图所示，试用迪

11、杰斯特拉算法求岀从顶点a到其他各顶点间的最短路径，完成下表答案: 终点i=1i=2i=3i=4i=5i=6b1515151515(a,b)(a,b)(a,b)(a,b)b)(a,b)c2(a,c)d12121111(a,d)(a,d)(a,c,f,d)(a,c,f,d)eoo1010.(a,c,e)(a,c,e)foo6gcooo161614(a,c,f,g)(a,c,f,g)(a,c,f,d,g)S终点集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b第七章题型一：折半查找过程，画判定树，计算ASL假定对有序表：(3, 4,5,7,24, 30

12、, 42,54,63,72,87,95)进行折半查找，试回答下列问题: 画出描述折半查找过程的判定树； 若查找元素 54,需依次与哪些元素比较？ 若查找元素 90,需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度答案： 先画出判定树如下(注：mid= ?(1+12)/2?=6):305374242454 72 查找元素 54,需依次与30, 63, 42, 54元素比较； 查找元素 90,需依次与30, 63,87, 95元素比较;3 层共查找 1 + 2X2+4X3=17 求ASL之前，需要统计每个元素的查找次数。判定树的前次；但最后一层未满，不能用8X4,只能

13、用 5X4=20次,所以 ASL=1/12 (17+20)= 37/12 3.08题型二：二叉排序树的创建，查找，计算ASL已知如下所示长度为12 的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov,De 试按表中元素的顺序依次插入一棵初始为空的二叉排序树,树，并求其在等概率的情况下查找成功的平均查找长度。画岀插入完成之后的二叉排序 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度答案:(1)求得的二更排序树如下图所示,在尊槪率情况下查找成功的平均查找长度为ASL = 1(1

14、X1 + 2X2 + 3X3 + 4 X 3 + 5 X 2 + 6 X 1) = 7I丄也12 =题型三：已知哈希表长度和哈希函数，利用线性探测法和链地址法解决冲突，构造哈希表，计算ASL1、(线性探测)设哈希表的地址范围为017，哈希函数为：H(key) =key%16用线性探测法处理冲突，输入关键字序列：(10,24, 32,17,31,30,46, 47,40,63,49)，构造哈希表，试回答下列问题： 画出哈希表的示意图； 若查找关键字63,需要依次与哪些关键字进行比较？ 若查找关键字60,需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。答案：画

15、表如下:012345678910111213141516173217634924401030314647 查找 63,首先要与 H(63)=63%16=15号单元内容比较，即63与31比较，不匹配；然后顺移，与 46,47,32,17,63 相比，一共比较了 6次！ 查找60,首先要与 H(60)=60%16=12号单元内容比较，但因为 12号单元为空(应当有空标记)，所以应当只比较这一次即可。 对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要 6次，“49”需要 3次，“40”需要 2次，“46”需要 3次，“47”需要 3次，所以 ASL=1/11

16、 (6+2+ 3X3+6= 23/112、(链地址法)设哈希函数H(K)=3 K mod 11，哈希地址空间为010，对关键字序列(32,13, 49, 24, 38, 21, 4, 12)，按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查ASLsucc 和 ASLunsuco找成功时和查找失败时的平均查找长度 线性探测法； 链地址法。答案:散列地址012345678910关键字412493813243221比较次数11121212ASLsucc = (1+1+1+2+1+2+1+2 /8=11/8ASLunsucc=( 1+2+1+8+7+6+5+4+3+2+)/11=40/11AS

17、Lsucc =(1*5+2*3)/8=11/8ASLunsucc= ( 1+2+1+2+3+1+3+1+3+1+1/11=19/1110第八章题型一：已知整数序列，写岀直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简 单选择排序、归并排序的排序过程（考两到三种），并会分析时空复杂度、稳定性及适用情况1、设待排序的关键字序列为12，2, 16, 30, 28, 10, 16*，20, 6, 18，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。直接插入排序折半插入排序 希尔排序（增量选取5, 3, 1） 冒泡排序简单选择排序 快速排序二路归并排序2121630281016

18、*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*2028306182610121616*20 :28 3018261012 -16 16*18 :20 28 30折半插入排序排序过程同希尔排序（增量选取5, 3, 1)102166181216*20 3028621210181616*20 30282610121616*18202830冒泡排序21216281016“ 2061830212161016* 206182830212101616* 6182028302101216616*182028302101261616*182028302106121616*182028302610121616*18202830答案：直接插入排序26 1012 16 16*18 20 28 30（增量选取5）（增量选取3）（增量选取1）快速排序12621012283016*20 16186261012283016*20 1618 28261012181616*20 2830 1826101216*161820 283016*26 10 12 16* 1618 20 28 30左子序列递归深度为1右子序列递