(完整版)中国海洋大学06-07数据结构第1学期A卷+答案

1、中国海洋大学命题专用纸（首页）2006学年第1学期试题名称：数据结构（A卷）专业受妇 学号 姓名 授课教师 分数一、简答下列术语：（10分）1、算法的时间复杂度2、栈与队列的异同3、完全二叉树、二叉排序树二、填空（10分）1、在双向循环链表 L中，删除指针P所指结点的语句序列是 , , free（p）。2、将下三角矩阵A1.8,1.8的下三角部分逐行地存储到起始地址为1000的内存单元中.已知每个元素占4个单元，则 A（6,4）的地址为 。3、高度为5的三阶B树至少有个结点。4、分别采用堆排序、 快速排序、1认排序和归并排序算法对初始状态已为递增序列的数据表进行递增排序，最省时间的是 算法。三

2、、（8分）已知一棵二叉机勺中序序列是dcbgeahfijk ,后序序列是 dcegbfhkjia ,请构造出该二叉树。四、（10分）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07 , 0.08 , 0.13 , 0.22 , 0.18 , 0.23,0.04 , 0.05。请设计它们相应的哈夫曼编 码。使用07的二进制表示形式是另一种编码方案，请比较两种方案的优缺点。五、（10分）设散列表地址空间为0.6 ,散列函数为H（x）=i mod 7 ,其中i为键值x中第一个字母在字母表中的序号，若键值的输入序列为 Jen,Feb,Mar,Apr,May,Jun,Jul,Au

3、g,Sep,Oct,Nov,Dec ,用链地址法处理冲突， 1）构造散列表；2）求出在等概率情况下，查找成功时的平均查找长度。六、（15分）（1）对下列数据表，写出采用希尔排序算法排序的每一趟的结果。（100,12,20,31,1,5,44,66,61,200,30,80,150,4,8）（2）对下列数据表，写出采用快速排序算法排序的第一趟的结果。（70,12,20,150 , 44,66,61,200,30,80,28）授课 教师张海燕命题教师或命题负责人签 字院系负责人签 字年 月 日中国海洋大学命题专用纸（附页）2006学年第1学期试题名称：数据结构（A）共2页第2页七、（6分）画出对应

4、于递增有序表 A1.21进行二分查找的判定树。八、（15分）对如下的网，1）写出其邻接矩阵。2）求其最小生成树。（写出各步状态）九、（8分）试编写一算法，实现无头结点的单链表的就地逆置，即利用原表的存储空间将线，性表 a ai,a 2, 11, an-i,an） 逆置为（an,a n-i, ，a2,a i）。十、（8分）设计算法以判断二叉树T是否为二叉排孑树（设T中任意两个结点F值均不相等）。（设二叉树以二叉链表来存储，结点结构为：Lchild dataRchild ）2006学年第一学期数据结构（A）卷试题答案一、简答题 （共10分，每个术语2分）1 算法的时间复杂度：一个算法执行所需的平均

5、时间长度，其描述了算法效率的高低。2 栈与队列的异同：栈是先进后出，只能在栈顶插入元素或删除元素；队列是先进先出，在队 头删除元素，队尾插入元素。3 完全二叉树：若一棵二叉树从上到下，从左到右依次编号与满二叉树对应编号完全相同。则 称此二叉树为完全二叉树。二叉排序树：或者是一棵空树，或者具有这样性质的树：（1）左子树结点的值均小于根结点的值，（2）右子树结点的值均大于根结点的值，（3）左、右子树分别是二叉排序树。二、填空题(共10分，每个填空2分)1. p prior next=p next, p next prior=p prior2. 10723. 154. .插入排序三、（8分，依照所构

6、造的二叉树正确的比例给分）答：由二叉树的中序序列dcbgeahfijk ,后序序列dcegbfhkjia ,构造的二叉树如下:四、（10分）答：（1） （9 分,依照正确的比例给分）所构造的哈夫曼树为 假设 8 个字母分别为 a ,b,c,d,e,f,g,h.出现概率为已知 0.07, 0.08, 0.13, 0.22, 0.18, 0.23, 0.04, 0.05。对左子树路径赋为 0,右子树赋为1,则a,b,c,d,e,f, g,h,i的哈夫曼编码为： a:0110 b:0111 c:110 d:10 e:010 f:00 g:1110 h:1111带权路径长度 WPL= w li =0.

7、07*4+0.08*4+0.13*3+022*2+0.18*3+0.23*2+0.04*4+0.05*4=2.79（2） （1分）07二进制表示如下:0.04: 000,0.05: 001 ,0.07: 010,0.08: 0110.13: 100,0.18: 101 ,0.22: 110,0.23: 111带权路径长度 WPL= w li = (0.04+0.05+0.07+0.08+0.13+0.18+0.22+0.22 ) *3=32.79比较可知：哈夫曼编码为不等长码，信源压缩度高。比例给用链地址法处理冲突，构造散列表如下:六、（15分）（1） （7分，依照正确的比例给分）初始关键字：

8、100 12 20 31 1 5 44 66 61 200 30 80 150 4 8假设各趟希尔排序的间隔分别为第一趟排序结果:第二趟排序结果:第三趟排序结果:8 12 20 304 1 5 8 121 4 5 8 127, 3, 1。1 5 466 61 200 31 80 150 4420 3020 30（2） （8分，依照正确的比例给分） 选取70为枢轴初始关键字:70 12 20 1504第一次交换后:28第二次交换后:28第三次交换后:28第四次交换后:2831314461 150 44 80 200 6644 61 66 80 100 15010010020066 61 200

9、30 80 2812 20 150 44 66 61 200 30 8012121220202044 66 61 200 30 80 150t.ti30 44 66 61 20080 15030 44 66 61200 80 150第一趟排序结果:28 12 20 30 44 66 61 70 200 80 150七、（6分，依照判定树的正确比例给分 ）答：二分查找的判定树如下：（71?）OO之八:（15分）034730 34 025（1） （7分）邻接矩阵为：7320151013)(C20)C2D一1(Vb)2(Vc)3(Vd)4(Ve)UV_UVex adjVa 3Va4Va 7VaVb,Vc,Vd, VeVex adj0Va4Vb 3Va, VbVc,Vd,VeVex adj0Vd 20Vd 1Va,Vb,VdVc,VeVex adj0Vd 200Va,Vb,Vd, VeVcVexStatus Reverse(Linklist *L)int i=1;P=L;for(; i L.length; i+=3 )m=p- next;n=mfnext; mfnext=p;nfnext=m; p=n;L-next=Null;十、(8分，依照解题思路的正确程度给分)判断二叉树是否为二叉排序树的程序如