中国海洋大学0607数据结构第1学期B卷答案

1、(完满版)中国海洋大学06-07数据构造第1学期B卷+答案(完满版)中国海洋大学06-07数据构造第1学期B卷+答案7/7(完满版)中国海洋大学06-07数据构造第1学期B卷+答案中国海洋大学命题专用纸（首页）2006学年第1学期试题名称：数据构造(B卷)共2页第1页专业年级：学号姓名授课教师名分数一、填空（20分）1，2，n，输出序列为a，a，a。则a=n的输出序列共有1、已知栈的输入序列为种。12n22、算法中基本操作重复执行的次数是问题规模n的某个函数,简称为。3、将上三角矩阵A1.8,1.8的上三角部分逐行地储藏到初步地址为2000的内存单元中，已知每个元素占5个单元，则A5,7的地址

2、为。4、已知完满二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是。5、3个结点可构成棵不同样形态的树。6、对下述广义表进行操作gettail(a,b),(c,d)的结果是。7、在按要点字递加的数组A1.20中，用二分查找方法进行查找时，查找长度为5的元素个数是。8、有n个结点的连通图的生成树有条边。9、在堆排序、快速排序、直接插入排序和希尔排序算法中，牢固的排序算法是算法。10、设有向图G的毗邻矩阵为A，若是图中不存在弧V,V，则Ai,j的值为。ij二、（8分）将以下二叉树改为先序线索二叉树。ABCDEF三、（10分）对下面给出的数据序列4,5,6,7,10,12,15,18,23，

3、构造一棵哈夫曼树，并求出其带权路径长度。四、（8分）已知散列表地址空间为0.8，散列函数为H(k)=kmod7，采用线性探测法办理冲突。将数据序列100,20,21,35,3,78,99,45依次存入该散列表中，并求出在等概率下的平均查找长度。授课教师张海燕命题教师或命题负责人院系负责人签字签字月日年中国海洋大学命题专用纸（附页）2006学年第1学期试题名称：数据构造（B）共2页第2页五、（15分）1）对以下数据表，写出采用冒泡排序算法排序的每一趟的结果。25,10,20,31,5,44,16,61,1002）对以下数据表，请写出采用快速排序算法排序的第一趟的结果。45,50,32,6,42,

4、55,61,30,68,37六、（8分）请画出查找要点字序列24,90，12，85，5，20，15所对应的二叉排序树。七、（15分）对以下有向图，1）写出其毗邻表2）求极点A到其余各极点的最短路经。（写出各步状态）A72534BD13C八、（8分）已知一个递加有序的单链表,编写一个函数向该单链表中插入一个元素为x的节点,使插入后该链表依旧递加有序。九、（8分）试编写一算法，求解二叉树高度。2006学年第一学期数据构造（B）卷试题答案一、填空题1、n-1;2、时间复杂度3、2140；4、73;5、2;6、(c,d);7、5;8、n-1;9、直接插入排序;10、0;二、先序遍历该二叉树的序次为：A

5、BDECF,图中虚线为所加的线索。ABC100DEF5743三、所构造的哈夫曼树为：23341825121315191096745对左子树路径赋为0，右子树赋为1,该数据序列相应的编码分别为4：011105：011116：11107：111110：011012：11015：01018：1023：00带权路径长度w=wili=4*5+5*5+6*4+7*4+10*4+12*3+15*3+18*2+23*2=300四、将100,20,21,35,3,78,99,45依次存入散列表：100mod7=220mod7=621mod7=035mod7=03mod7=378mod7=199mod7=145m

6、od7=30123456782135100378992045各数据的查找长度分别为：100：1，20：1，21:1,35：2，3：1，78：4，99：5，45：5。设查找等概率Pi=1/8;因此平均查找长度为ASL=1/8+1/8+1/8+1/8*2+1/8+1/8*4+1/8*5+1/8*5=2.5五、（1）对于序列25,10,20,31,5,44,16,61,100进行冒泡排序的每一趟的结果以下:251010105510202051010202552016163152516202053116252525441631313131164444444444616161616161100100100100100100（2）采用45为枢轴，第一趟快速排序的结果为：3730326424561556850详尽步骤以下：4550326425561306837初始序列3750326425561306845进行一次交换此后3745326425561306850进行两次交换此后3730326425561456850进行三次交换此后3730326424561556850进行四次交换此后只此一趟排序完成。六、二叉排序树各结点的值为：2412905208515七、（1）该有向图的毗邻表为