中国海洋大学2012-2013学年期末考试试题及参考答案A

中国海洋大学2012-2013学年期末考试试题及参考答案学年第2学期试题名称:数据结构（A卷）专业年级：计算机学号姓名授课教师名分数一、解答下列各题（40分，每小题8分）1.已知下图为广义表的存储结构图，写出该图表示的广义表，并求该广义表的长度和深度。listlist2・对下图所示有向图，利用Dijkstra算法求出从顶点A到其它各顶点的最短路径及距离。已知一棵3阶B-树如下图所示，分别画出插入关键字20后和删除关键字150后得到的B-树。

已知序列｛503，87，512，61，908，170，897，275，653，462｝将其调整为堆(大堆顶，即K>=K,K>=K)。i2ii2i+1将下列森林转换为相应的二叉树，并加上指向前驱和后继的中序线索。C8J二、判断题：正确的打"，错误的打X(每题1分，共15分)1、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()2．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。()3．顺序存储的线性表可以随机存取。()4．若一个广义表的表头为空表，则此广义表亦为空表。()5．任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。()6．广义表是由零或多个原子或子表所组成的有限序列，所以广义表可能为空表。()7．用树的前序遍历和中序遍历可以导出树的后序遍历。()8．在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应特殊处理。()9．将一棵树转换成二叉树后，根结点没有左子树。()10.在n个结点的无向图中，若边数〉n-1，则该图必是连通图。()11．一个图的广度优先遍历生成树是唯一的()12．对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的顺序是一样的。()13．负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。()14．对一个堆，按二叉树层次进行遍历可以得到一个有序序列。()15.对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O(n2)。()三＞(15分)已知一棵度为M的树中有n1个度为1的结点，2个度为的2结点，・・・nm个度为m的结点，证明其叶结点个数为1+£(i-1)ni。i=1四、(15分)试编写一个高效算法，查找未排序文件A(1..n)中的第K个最小的元素，并分析你的算法的时间复杂度。注：第K个最小的元素：若M是A(1),A(2),…,A(n)中的第K个最小的元素，则A(1),A(2),…,A(n)中至少有K个元素小于等于M，并且最多有K-1个元素小于M。五、(15分)试写一个判定所给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不同。期末考试试题参考答案科目名称：数据结构、1.广义表为：list=(((a,b,()),()),(a,(b)),())长度为3深度为32、从顶点A到其他个顶点的最短路径及距离为：C:A>C15B:A>C>B19F:A—>C-->F25E:A-->c-一〉B——>E29D:A-->c-->F-—>D293•①插入(20)后的3阶B-树如图所示。②再删除(150)后的3阶B-树如下图所示。4.初始堆为：”908、/653、897、/503、462170/5122756187Z5.对应二叉树为:二、答案：X2.V3.V4.X5.V6.V7.V8.X9.X10.XTOC\o"1-5"\h\zX12.V13.V14.X15.V三、答案依题意：设n为总的节点个数，叫为叶子结点(即度为0的结点)的个数,则有：°n=n+n+n+…+口①012m又有：n-1=度的总数，即：n-1=n*l+n*2+・・・+n*m②12m①-②式得：1=n-n-2n-(m-1)n012m则有：n=1+n+2n•••+(mT)n023m=1+£(i-1)nii=1共共4页第3页四、思想：调用一趟快速排序以后，有P-1(P:轴元素位置)个元素小于等于轴元素，且n-P个元素大于等于轴元素，若KvP,则第K个最小元素在A(1..P-1)中；若心卩，则A(P)就是第K个最小元素；若K>P,则A(1..n)中的第K个最小元素就是A(P+1..n)中的第(K-P)个最小元素。PROCEDUREqpass(R:listtype;lqw,hig:integer;vardivinteger)Begini=low;j:=hig;x:=R[I];whileI<jdo[while(i<j)and(R[j]>x)doj:=j-1R[i]:=R[j];While(i<j)and(R[i]<=x)doI:=i+1R[j]:=R[i]]R[I]:=x;div:=I;End;proceduresearch_k(ls:listtype,l,h,k:iinteger;varkey:integer)BeginIfl=hthenkey:=ls(l)Else[qpass(ls,l,h,p)Ifk<=p-1thensearch_k(ls,l,p-1,k,key)Elseifk=pthenkey=ls(p)Elsesearch_k(ls,p+l,h,k-p,key)]End.五、解答：为判定二叉树是否为二叉排序树同样是建立在中序遍历的框架基础下，遍历中附设一指针pre指向当前访问结点的中序直接前驱，每访问一个结点便比较前驱结点pre和此结点是否有序，若遍历结束后各结点和其中序直接前驱均满足有序，则此二叉树为二叉排序树；否则只要有一个结点不满足，那么此二叉树就不是二叉排序树。VoidBisortTree(BiTreeT,BiTree&pre,bool&flag){〃初始时pre=NULL,flag=true；若结束时flag为true,则此二叉树是二叉排序树if(T&&flag){BiSortTree(T->lchild,pre,flag);If(pre==NULL){〃访问中序序列的一个结点，不需要比较Flag=true;Pre=T;}else{//比较T与中序直接前驱pre的大小，这里假定没有相同的关键