中国海洋大学007数据结构第1学期A卷+答案

中国海洋大学命题专用纸（首页）2006学年第1学期试题名称：数据结构（A卷）专业整：学号姓名授课教师分数一、简答下列术语：（10分）1、算法的时间复杂度2、栈与队列的异同3、完全二叉树、二叉排序树二、填空（10分）1、在双向循环链表L中，删除指针P所指结点的语句序列是,,free（p）。2、将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中.已知每个元素占4个单元，则A（6,4）的地址为。3、高度为5的三阶B—树至少有个结点。4、分别采用堆排序、快速排序、1认排序和归并排序算法对初始状态已为递增序列的数据表进行递增排序，最省时间的是算法。三、（8分）已知一棵二叉机勺中序序列是dcbgeahfijk,后序序列是dcegbfhkjia,请构造出该二叉树。四、（10分）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07,0.08,0.13,0.22,0.18,0.23,0.04,0.05。请设计它们相应的哈夫曼编码。使用0〜7的二进制表示形式是另一种编码方案，请比较两种方案的优缺点。五、（10分）设散列表地址空间为0..6,散列函数为H（x）=imod7,其中i为键值x中第一个字母在字母表中的序号，若键值的输入序列为Jen,Feb,Mar,Apr,May,Jun,Jul,Aug,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分）画出对应于递增有序表A[1..21]进行二分查找的判定树。八、（15分）对如下的网，1）写出其邻接矩阵。2）求其最小生成树。（写出各步状态）九、（8分）试编写一算法，实现无头结点的单链表的就地逆置，即利用原表的存储空间将线，性表（a1,a2,…，an-1,a“逆置为（an,an-1,,…，a2,a。。十、（8分）设计算法以判断二叉树T是否为二叉排孑树（设T中任意两个结点F^值均不相等）。（设二叉树以二叉链表来存储，结点结构为：LchilddataRchild—）答:由二叉树的中序序列dcbgeahfijk,后序序列dcegbfhkjia,构造的二叉树如下:四、答:分）a:0110b:0111答:由二叉树的中序序列dcbgeahfijk,后序序列dcegbfhkjia,构造的二叉树如下:四、答:分）a:0110b:0111带权路径长度(2)(1分)0.04:000,0.13:100,带权路径长度0.08:0110.23:1112006学年第一学期数据结构（A）卷试题答案一、简答题（共10分，每个术语2分）算法的时间复杂度：一个算法执行所需的平均时间长度，其描述了算法效率的高低。栈与队列的异同：栈是先进后出，只能在栈顶插入元素或删除元素；队列是先进先出，在队头删除元素，队尾插入元素。完全二叉树：若一棵二叉树从上到下，从左到右依次编号与满二叉树对应编号完全相同。则称此二叉树为完全二叉树。二叉排序树：或者是一棵空树，或者具有这样性质的树：（1）左子树结点的值均小于根结点的值，（2）右子树结点的值均大于根结点的值，（3）左、右子树分别是二叉排序树。二、填空题（共10分，每个填空2分）p—prior—.next=p—.next,p—.next—.prior=p—.prior107215.插入排序（8分，依照所构造的二叉树正确的比例给分）（10分）（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的哈夫曼编码为：c:110d:10e:010f:00g:1110h:1111WPL=£w叫=0.07*4+0.08*4+0.13*3+022*2+0.18*3+0.23*2+0.04*4+0.05*4=2.790~7二进制表示如下：0.05:001,0.07:010,0.18:101,0.22:110,WPL=工w叫=(0.04+0.05+0.07+0.08+0.13+0.18+0.22+0.22)*3=3>2.79

比较可知：哈夫曼编码为不等长码，信源压缩度高。比例给比较可知：哈夫曼编码为不等长码，信源压缩度高。比例给用链地址法处理冲突，构造散列表如下:六、（15分）（1）（7分，依照正确的比例给分）初始关键字：10012假设各趟希尔排序的间隔分别为第一趟排序结果:

第二趟排序结果:

第三趟排序结果:81220304158121458127,3,1。154666120031801504420302030（2）（8分，依照正确的比例给分）选取70为枢轴初始关键字:701220150・4第一次交换后:28第二次交换后:28第三次交换后:28第四次交换后:28第一趟排序结果:31314461150448020066446166801001501001002006661200308028122015044666120030801212122020204466612003080150t.ti30446661200304466618015020080150281220304466617020080150七、（6分，依照判定树的正确比例给分）答：二分查找的判定树如下：(77^/J_J1DCZ)O()GDCD1C42)(7^)003ct)<CD(八：（15分）■0347-11130/3"（1）（7分）邻接矩阵为：心02511|73201卜85101(Vb)2(Vc)3(Vd)4(Ve)UV_UVexadjVa3Va4Va7[Va][Vb,Vc,Vd,Ve]Vexadj0Va4Vb3[Va,Vb][Vc,Vd,Ve]Vexadj0Vd20Vd1[Va,Vb,Vd][Vc,Ve]Vexadj0Vd200[Va,Vb,Vd,Ve][Vc]

Vexadj0000[Va,Vb,Vd,Ve,Vc]（2）（8分）（2）（8分）最小生成树为:九：（8分，依照解题思路的正确程度给分函数编写如下：单链表如下图：A1*A2*A3An-1aAnA1*A2*A3An-1aAnStatusReverse(Linklist*L){inti=1;P=L;for(;i<L.length;i+=3){m=p-next;n=mfnext;mfnext=p;nfnext=m;p=n;L-next=Null;十、(8分，依照解题思路的正确程度给分)判断二叉树是否为二叉排序树的程序如下：intPaixu(Bi