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

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

2、-AG/D+EF#PUSH(OPTR,/)8#-/AGD+EF#PUSH(OPND,D)9#-/AGD+EF#Operate(G,/,D)10#-AH+EF#Operate(A,-,H)11#I+EF#PUSH(OPTR,+)12#+IEF#PUSH(OPND,E)13#+IEF#PUSH(OPTR,)14#+IEF#PUSH(OPND,F)15#+IEF#Operate(E,F)16#+IJ#Operate(I,+,J)17#K#RETURN题型二：汉诺塔时间复杂度的分析及证明汉诺塔问题的递归算法的时间复杂度是什么？请给出答案并且给予证明解：时间复杂度T(n)=0(2n),证明如下已知：f(

3、l)=l,f(n)=2f(n-1)+1所以：f(n)+1=2(f(n-1)+1)f(n)=2n-1(2n-1为至少执行移动操作的次数)T(n)=O(2n)故：得证第四章题型一：数组地址的计算设有二维数组A(6x8),每个元素占6字节存储，顺序存放，A的起地址为1000,计算:数组A的体积(即存储量)；数组的最后一个元素A57的起始地址；按行优先存放时，元素A14的起始地址；按列优先存放时，元素A47的起始地址。第五章题型一：由二叉树的中序遍历和前(后)序遍历，画出该二叉树1、给定二叉树的两种遍历序列，分别是：前序遍历序列：ABDFCEGH；中序遍历序列：BFDAGEHC试画出二叉树B，并简述由

4、任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。答案：2、试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。题型二：哈夫曼树的构造(画树、计算WPL、初态和终态表)，设计哈夫曼编码1、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32,0.03，0.21，0.10。试为这8个字母设计赫夫曼编码。试设计另一种由二进制表示的等长编码方案。对于上述实例，比较两种方案的优缺点。答案：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10，按哈夫曼规则：【(2,3

5、)，6,(7,10)】，19,21,32字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案比较：字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10(100)(40)(60)192132(28)(17)(11)7106(5)23方案1WPL=2*(0.19+0.32+0.21)+4*(0.07+0.06+0.10)+5*(0.02+0.03)=1.44+0.92+0.25=2.61方

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

7、23611000112013971200012271321013000134701112题型三：利用二叉树的性质对某些问题进行证明对于那些所有非叶子结点均含有左右子数的二叉树：试问：有n个叶子结点的树中共有多少个结点？试证明：2-1)=1,其中n为叶子结点的个数，1表示第i个叶子结点所在的层次ii=1(设根节点所在层次为1)。解：(1)总结点数为1+2件，其中件为非叶子结点数，则叶子结点数为n=nl+1,所以总结点数为2n一1。(2)用归纳法证明。i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，*=1,2-(l1-1)=1，结论成立。设有n个叶子结点时也成立，即2-(/-i.+2-

8、(-L+.+2-(p+.+2-(/”+i.=1，现假设增加一个叶子结点，这意味着在某叶子结点p上新生两个叶子结点，而结点p则成为非叶子结点，可见，总结点数增2，叶子结点数增1。此时，所有叶子结点是原结点除去p，然后加上两个深度为l+1的新叶子结点，由此，p2-(l1-1)+2-(l2-1)+.+2-(lp-1-1)+2-(lp+1-1)+.+2-(ln+1)+2-(lp+1-1)+2-(lp+1-1)=2-(l1-1)+2-(l2-1)+.+2-(lp-1)+.+2-(ln+1)=1则当i=n+1时，也成立，由此即得到证明。AA-第六章2、已知如图6.33所示的无向网，请给出：邻接矩阵；邻接表

9、最小生成树答案：叩43DDDDD4D559DDD35D5DDD5D55D7654D9D7D3DDDDD63D2DDDD5D2D6DD54DD6D题型二：根据图的逻辑结构或存储结构，写出深度、广度优先搜索遍历结果（根据逻辑结构写是唯一的，根据存储结构写不唯一）已知图的邻接矩阵如图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先题型三：根据图的逻辑结构填写最短路径求解过程表，画出最小生成树（计算权值和），写出拓扑排序结果有向网如图所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成下表XyTi23456b1515151515158b8b8b8b8b(ab)2(ac)

10、121211118888f3(a,c,，d)eoo101088e(a,c,e)foo(a,c,)goooo161688f3g88f8g(a,c,d,g)S终点集888188f8e88f8i88f8e88g88f8e88g8b第七章题型一：折半查找过程，画判定树，计算ASL假定对有序表：(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题：画出描述折半查找过程的判定树；若查找元素54，需依次与哪些元素比较？若查找元素90，需依次与哪些元素比较？假定每个元素的查找概率相等，求查找成功时的平均查找长度。答案：先画出判定树如下(注：mid=(1+12)/2=6

11、)：30563374287424547295查找元素54，需依次与30,63,42,54元素比较；查找元素90，需依次与30,63,87,95元素比较；求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1+2X2+4X3=17次；但最后一层未满，不能用8X4，只能用5X4=20次，所以ASL=1/12(17+20)=37/123.08题型二：二叉排序树的创建，查找，计算ASL已知如下所示长度为12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树

12、，并求其在等概率的情况下查找成功的平均查找长度。若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。答案：三(1X1+2XCD求得的二叉排序树如下图所示，在等概率情况下查2+3X3+4X3+!题型三：已知哈希表长度和哈希函数，利用线性探测法和链地址法解决冲突，构造哈希表，计算ASL1、(线性探测)设哈希表的地址范围为017,哈希函数为：H(key)=key%16。用线性探测法处理冲突，输入关键字序列：(10，24，32，17，31，30，46，47，40，63，49)，构造哈希表，试回答下列问题：画出哈希表的示意图；若查找关键字63,需要依次与哪

13、些关键字进行比较？若查找关键字60,需要依次与哪些关键字比较？假定每个关键字的查找概率相等,求查找成功时的平均查找长度。答案：画表如下：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

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

15、+2+1+8+7+6+5+4+3+2+1)/11=40/11ASLsucc=(1*5+2*3)/8=11/8ASLunsucc=(1+2+1+2+3+1+3+1+3+1+1)/11=19/110123456789oTIlAlk|38|A|13|h-k|24|A|13Ihl1Ia|第八章题型一：已知整数序列，写出直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、归并排序的排序过程（考两到三种），并会分析时空复杂度、稳定性及适用情况1、设待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。折

16、半插入排序直接插入排序希尔排序（增量选取5，3，1）冒泡排序快速排序简单选择排序二路归并排序答案：直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830折半插入排序排序过程同希尔排序（增量选取5，3，1）102166181216*203028（增量选取5）621210181616*203028（增量

17、选取3）2610121616*18202830（增量选取1）冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830快速排序12621012283016*2016186261012283016*20161828261012181616*2028301826101216*161820283016*26101216*1618202830左子序列递归深度为1，右