




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
中国海洋大学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的大小,这里假定没有相同的关键
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年紧急意外抢救预案试题
- 小学生英语游戏教学课件
- 思维导图教学第三版课件
- 住宅小区地下车库产权转让违约金规定合同
- 餐饮企业承包经营合作协议范本
- 国家电网电气安全作业知识相关内容试卷
- 家用纺织品设计元素考核试卷
- 危险化学品仓储安全应急预案演练评估准则考核试卷
- 培训评估与组织战略匹配度分析考核试卷
- 燃料储存罐材料考核试卷
- 2025年4月自考03346项目管理试题
- 艾梅乙反歧视培训课件
- 浙江省杭州市2024-2025学年高二下学期6月期末教学质量检测英语试题(含答案)
- 2025年河南省中考地理试题(含答案)
- 2025安全生产月一把手讲安全公开课三十二(91P)
- 2025课件:红色基因作风建设七一党课
- 在线网课学习课堂《人工智能(北理 )》单元测试考核答案
- 康复科护理管理制度
- 《中国近现代史纲要(2023版)》课后习题答案合集汇编
- 国家综合性消防救援队伍消防员管理规定
- 第6章_悬移质泥沙运动2014
评论
0/150
提交评论