中国海洋大学0607数据结构第1学期A卷

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

2、知一棵二叉树的中序序列是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)=imod7，此中i为键值x中第一个字母在字母表中的序号，若键值的输入序列为Jen,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用链地点法办理矛盾

3、，结构散列表；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分）画出对应于递加有序表A1.21进行二分查找的判断树。八、（15分）对以下的网，1）写

4、出其毗邻矩阵。2）求其最小生成树。（写出各步状态）3BA734D215CE九、（8分）试编写一算法，实现无头结点的单链表的就地逆置，即利用原表的储存空间将线性表（a1,a2,，an-1,an）逆置为（an,an-1,，a2,a1）。十、（8分）设计算法以判断二叉树T能否为二叉排序树(设T中随意两个结点的值均不相等（设二叉树以二叉链表来储存，结点结构为：LchilddataRchild）)。2006学年第一学期数据结构（A）卷试题答案一、简答题（共10分，每个术语2分）算法的时间复杂度：一个算法履行所需的均匀时间长度，其描绘了算法效率的高低。栈与行列的异同：栈是先进后出，只好在栈顶插入元素或删除

5、元素；行列是先进先出，在队头删除元素，队尾插入元素。完整二叉树：若一棵二叉树从上到下，从左到右挨次编号与满二叉树对应编号完整同样。则称此二叉树为完整二叉树。二叉排序树：或许是一棵空树，或许拥有这样性质的树：（1）左子树结点的值均小于根结点的值，（2）右子树结点的值均大于根结点的值，（3）左、右子树分别是二叉排序树。二、填空题（共10分，每个填空2分）1ppriornext=pnext,pnextprior=pprior210723154插入排序三、（8分，依据所结构的二叉树正确的比率给分答：由二叉树的中序序列dcbgeahfijk，后序序列）dcegbfhkjia，结构的二叉树以下：abidg

6、hj四、（10分）cefk答：(1)（9分，依据正确的比率给分）所结构的哈夫曼树为：假定8个字母分别为a,b,c,d,e,f,g,h.出现概率为已知0.07，。对左子树路径赋为0，右子树赋为1，则a,b,c,d,e,f,g,h,i的哈夫曼编码为：a:0110b:0111c:110d:10e:010f:00g:1110h:1111带权路径长度WPL=wili=0.07*4+0.08*4+0.13*3+022*2+0.18*3+0.23*2+0.04*4+0.05*4（1分）07二进制表示以下：000，：001，：010，：011：100，：101，：110，：111带权路径长度WPL=wili=

7、（）比较可知：哈夫曼编码为不等长码，信源压缩度高。1五、（10分）（1）（9分，依据正确的0.070.080.04比率给分）用链地点法办理矛盾，结构散列表以下：0Nov1AprAugOct23JenJunJul4Dec5Sep6FebMarMay(2)（1分）均匀查找长度L=1/12（6*1+3*2+3*3）六、（15分）（1）（7分，依据正确的比率给分）假定各趟希尔排序的间隔分别为7，3，1。第一趟排序结果：81220301546661200318015044100第二趟排序结果：41581220303161150448020066100第三趟排序结果：1458122030314461668

8、01001502002）（8分，依据正确的比率给分）选用70为枢轴初始重点字：701220150446661200308028ij第一次互换后：2812201504466612003080ij第二次互换后：2812204466612003080150ij第三次互换后：2812203044666120080150ij第四次互换后：2812203044666120080150ij第一趟排序结果：281220304466617020080150七、（6分，依据判断树的正确比率给分）答：二分查找的判断树以下：1115162813194710151821八：（15分）034734025（1）（7分）毗邻

9、矩阵为：73201510i1(Vb)2(Vc)3(Vd)4(Ve)UV_UVexVaVaVaVaVb,Vc,Vd,adj347VeVexVaVbVa,VbVc,Vd,Veadj043VexVdVdVa,Vb,VdVc,Veadj0201VexVdVa,Vb,Vd,Vcadj0200VeVexadj000（2）（8分）3最小生成树为：AD2C九：（8分，依据解题思路的正确程度给分）函数编写以下：单链表以以下图：PMNA1A2A3Va,Vb,Vd,0Ve,VcB31EAn-1AnStatusReverse(Linklist*L)inti=1;P=L;for(;iL.length;i+=3m=pnext;n=mnext;mnext=p;nnext=m;p=n;Lnext=Null;十、（8分，依据解题思路的正确程度给分）判断二叉树能否为二叉排序树的程序以下：in