中国海洋大学命题专用纸（首页）2006学年第1学期试题名称：数据结构(B卷)共2页第1页专业年级：学号姓名授课教师名分数一、填空（20分）1、已知栈的输入序列为1，2，⋯，n，输出序列为a1，a2，⋯，an。则a2=n的输出序列共有种。2、算法中基本操作重复执行的次数是问题规模n的某个函数,简称为。3、将上三角矩阵A[1..8,1..8]的上三角部分逐行地存储到起始地址为2000的内存单元中，已知每个元素占5个单元，则A[5,7]的地址为。4、已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是。5、3个结点可构成棵不同形态的树。6、对下述广义表进行操作gettail[((a,b),(c,d))]的结果是。7、在按关键字递增的数组A[1..20]中，用二分查找方法进行查找时，查找长度为5的元素个数是。8、有n个结点的连通图的生成树有条边。9、在堆排序、快速排序、直接插入排序和希尔排序算法中，稳定的排序算法是算法。10、设有向图G的邻接矩阵为A，如果图中不存在弧〈Vi,Vj〉，则A[i,j]的值为。二、（8分）将下列二叉树改为先序线索二叉树。三、（10分）对下面给出的数据序列{4,5,6,7,10,12,15,18,23}，构造一棵哈夫曼树，并求出其带权路径长度。四、（8分）已知散列表地址空间为0..8，散列函数为H(k)=kmod7，采用线性探测法处理冲突。将数据序列{100,20,21,35,3,78,99,45}依次存入该散列表中，并求出在等概率下的平均查找长度。授课教师张海燕命题教师或命题负责人签字院系负责人签字年月日ABCEDF中国海洋大学命题专用纸（附页）2006学年第1学期试题名称：数据结构（B）共2页第2页五、（15分）（1）对下列数据表，写出采用冒泡排序算法排序的每一趟的结果。{25,10,20,31,5,44,16,61,100}（2）对下列数据表，请写出采用快速排序算法排序的第一趟的结果。{45,50,32,6,42,55,61,30,68,37}六、（8分）请画出查找关键字序列{24,90，12，85，5，20，15}所对应的二叉排序树。七、（15分）对如下有向图，1）写出其邻接表2）求顶点A到其余各顶点的最短路经。（写出各步状态）八、（8分）已知一个递增有序的单链表,编写一个函数向该单链表中插入一个元素为x的节点,使插入后该链表仍然递增有序。九、（8分）试编写一算法，求解二叉树高度。4723ABDC3512006学年第一学期数据结构（B）卷试题答案一、填空题1、n-1;2、时间复杂度3、2140；4、73;5、2;6、((c,d));7、5;8、n-1;9、直接插入排序;10、0;二、先序遍历该二叉树的顺序为：ABDECF,图中虚线为所加的线索。三、所构造的哈夫曼树为：109451915100342357612137251843ABCEDF对左子树路径赋为0，右子树赋为1,该数据序列相应的编码分别为4：011105：011116：11107：111110：011012：11015：01018：1023：00带权路径长度w=iiwl=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=145mod7=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}进行冒泡排序的每一趟的结果如下:（2）选取45为枢轴，第一趟快速排序的结果为：3730326424561556850具体步骤如下：4550326425561306837初始序列3750326425561306845进行一次交换之后3745326425561306850进行两次交换之后3730326425561456850进行三次交换之后2510203154416611001020255311644611001020525163144611001052016253144611005101620253144611005101620253144611003730326424561556850进行四次交换之后只此一趟排序完成。六、二叉排序树各结点的值为：七、（1）该有向图的邻接表为（2）顶点A到其余各顶点的最短路经求解步骤如下：八、在单链表中插入元素为x的节点的算法编写如下：步骤节点i=1i=2i=3B{A,B}7{A,D,B}6C∞∞{A,D,B,C}7D{A,D}2选取关键DBC8590515202412ABCD1234340123
