02331数据结构201210真题及答案.docx

《02331数据结构201210真题及答案.docx》由会员分享，可在线阅读，更多相关《02331数据结构201210真题及答案.docx（8页珍藏版）》请在优知文库上搜索。

1、2012年10月高等教育自学考试全国统一命题考试数据结构试题课程代码：02331清考生按规定用簿将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1 .答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字名或钢隹埴写在答题册规定的位置上。2 .每小题选出答案后.用2B铅笔把答跑纸上对应即目的答案标号涂黑,如需改动.用橡皮擦干净后，再选涂其他答案标号.不能答在试即卷上.一、单项选择题(本大筮共15小题，每小题2分，共30分)在每小SS列出的四个备选项中只有一个是符合踵目要求的，请将其选出并将.答SS纸”的相应代码涂黑，错涂、多涂或未涂均无分.1.个算法的时间耗费的数玳级称为该

2、算法的A.效率C.可实现性2.顺序衣便于A.插入站点C.按侦查找结点B,难度D时间更杂度B.删除结点D.按序号查找结点3.设带头结点的单循环胜表的头指针为head.指针变力tP指向尾结点的条件是A.p-ncxt-ncxt=hcadB.p-ncxt=hcadC.pnextnex(=NU1.1.D.pnext=NU1.1.4 .设以改组A0.m-1.存放循环队列，伍,m指向队头元素，mar指向队尾元嘉的下一个位置,则当前队列中的元素个数为A.(rear-from+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m5 .下列关于顺序校的叙述中,正

3、确的是A.入栈操作需要判断栈满.出栈操作需要判断栈空B.入栈操作不露要判断栈满，出校操作命要判断栈空C.入栈操作需要判断栈满，出校悚作不需要判断栈空D.入栈操作不需要判断栈满，出栈操作不需要划断校空6. A足一个IoXIO的对称矩阵,若采用行优先的下三角压缩存储,第一个元素a险的存储地址为I，每个元素占一个存储单元，则a3的地址为A.25B.26C.33D.347 .树的后序遍历等价于该树对应二叉树的A.层次遍历B.前序遍历C中序遍历D.后序遍历8 .使用二叉城索树的目的是便于A.二叉树中结点的插入与删除B.在二叉树中查找双亲C,确定二叉树的高度D.查找一个结点的前趋和后继9 .设无向图的顶点

4、个数为n,则该图边的数目以多为B.n(n-1.)2D.n2B.无向图D.无向连通图B.宜接选择抗考D.快速排序B.75,65.45.30.25.15D.75.45.65,25.30.15A.n-1.C.n(n+1.)/2IO,可进行拓扑排序的图只能是A.有向图C.有向无环图11 .下列排序方法中稳定的是A.直接插入排序C.堆揖序12 .卜列序列不取隹的是A.75.45,65.30.1505C.75,65.30.15.25.4513 .对线性表进行二分杳找时,要求线性我必须是A.顺序存储B.链式存谛C.顺序存储且按关键字有序D.链式存储且按关键字有序14 .分别用以卜序列生成二叉持序树,其中三个

5、序列生成的二叉排序树是相同的，不同的序列是A.(4.1.233)B.(4.2.3.I.5)C.(4,5.2.1.3)D.(4.2.1.5.3)15 .下列关于m阶B树的叙述中，州医的是A.每个结点至多有m个关键字B.每个结点至多有m棵子树C.插入关键字时，通过结点分裂使树而烯加D删除关键字时通过结点介并使树高降低非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答卷纸匕不能答在试跑卷.二、填空题(本大题共IO小题，每小JS2分，共20分)16 .数据元素之间的逻辑关系称为数据的结构，17 .在线性表中,去的长度定义为。18FI1.S表示入栈操作，X表示出找操作,若元素入栈的顺序为I、2、

6、3、4,为了得到1、3、4、2的出栈顺序，相应的S和X的操作序列为。19 .在二叉树中，带权路径长度G短的树林为.20 .已知广义表Ghead(G)1.jtai1.(G)的深度分别为4和6.则G的深度是_21 .一组字符(a,b,c,d)在文中出现的次数分别为(7,6.3,5),字符d,的哈夫曼编码的长度为.22 .在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。23 .直接选择排序筌法的时间复杂度是.24 .对于长度为81的表，若采用分块查找,每块的最佳长度为.25 .H1.:又造表保存有n个结点的：叉树，则结点中有个空指针城。三、解答题(本大髭共4小题，每小超5分，共20分)26

7、 .锻设Q是一个具有I1.个元素存储空间的循环队列(认尾指针指向队尾元素的下一个位田，队头指针指向队头元素)，初始状态Qfrom=Qmar=O:写出依次执行下列操作后头、尾指针的当前值。ahc.dcf入队，ab.c.d出认：(1)Q.front=:Q.rcar=.g,h,ijk,1.入队，c,f,g,hti1.R：(2)Q.from=：Q.rcar=.Mm.o.P入队，ij.kj.m出队：(3)Q1.roni=；Q.rear=。27 .已知一个无向图如题27图所示，以为起点，用普里姆(Prim)算法求其最小生成树,两出最小生成树的构造过程，H27S28 .用归并排序法对序列(9836.90.4

8、7.23,1进行排序,问:(1) 一共需要儿植归并可完成排序.(2)写出第一趟归并后数据的排列次序.29 .组记录关键字(55.76,4432,64,82,20.16.43),用散列函数H(kcy=kcy%11将记录敌列到Ift列表Hno.12中去，用我性探测法解决冲突，(I)Bi出存入所有记录后的散列表。(2)求在等概率情况下,查找成功的平均查找长度.四、算法阅读题I本大题共4小题，每小Sfi5分，共2Q分)30 .顺序表类型定义如下：#define1.istSize100typcdcfstruct(intdaa1.iMSize:int1.ength；ISeq1.ist:阅读下列豫法，并回答

9、问跑：voidE)(Scq1.iSt*1.)intij；i=0；whi1.digth)if(1.-dtai%2!=0)for(j=i+kj1.engh;j+)1.-dataj-!)=1.-data(j;1.-gth-:e1.sei+(1)若1.Adata中的数据为(22.4.63.0.15.29.34.42.3),则执行上述算法后1.data中的数据以及1.A1.sgIh的值各是什么？(2)该算法的功能是什么？31 .有向图的邻接矩阵类鞭定义如下:#dcfincMVN100最大顶点数IyPCdCfimETypc;/边上权(类型IypedefsrcETypeedgesMVNMVN):/邻接矩阵，

10、即边表intn;/图的顶点数MGraph;图类型例如，一个有向图的锦接矩阵如下所示；OOOII阅读下列算法，并回答问题:WidDKMGraphG)Inti,j.k=0:S1.cp1.:for(i=0:iGn;i+)for(j=0:jG.n:j+)if(Gedges(iIUI=I)k;PrinIfr%d,k);step2:for(j=0:jGn;j+)(k=0;for(i=():ij；fbr(i=2:in：i+)rO=r(i:j=i-hwhi1.e(r(Or(j)U+1.=rj;j=jT：rU+1.=rO:J(1)这是哪种插入持序算法?该笄法是否稳定？(2)设置r(0的作用是什么？33 .顺序表

11、类型定义如下：Iypedefin(Seq1.istI1.001；阅读卜列算法，并回答问SS：voidD3(Scq1.is1.r.intn)(inta,bi：if(rOe1.se(a=r11：b=r(O:)for(i=2sinsi+)if(r1.b)b=rfi);printf(a=%db=%d-n”,a,b)：)(1)给出该算法的功能：(2)给出该算法的时间更杂衣.五算法设计题i本题10分)54 .二叉树的存储结构类型定义如下IyPedCfstructnixie(intdata：structnode!chi1.d.,rchi1.d:BinNode；IyPedefBinNodeBinTree；编写

12、递归竟法，求只有一个孩子结点的结点总数,并计算这些结点的数据值的和.函数的原型为：Yoid114(BinTrceT.intcount,int*sum),count和sum的初侑为0”绝密启用前2012年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码02331）一ggs选择Ja（本大Ia共15小S1.黜小H2分，共30分）1.D2,D3.B4.AS.A6.D7.CS.D9.B10.C】1.A12.C13.C14.A4一.、,二、填空It（本大I1.共10小题.国小墨2分，共20分）16.史，17.敷光元素的个败19.哈夫曼树（或重优二又材或IS.SXSSXSXX三、解

13、答题（本大H共4小Jtt.银小莪5分,共20分）（2分）QrearQ.rcax-26.（1）Q.from-*三Txtaa;D4(T-1.dn1d.COUBt1.nunX04(TrehiM.counSUm);（2分）（2分）（I分）（I分）因、算法偶工收（本大题共4小题.5小题5分，共20分）30. （1）dK）-（22.4.0.34.42）Icngth=S（2）朋除原序赛中的IiHWKiK元素.3.（1）线计出Da中边的数日.（2）境计a出图中每个顶点的入腐败.32. （I）取接获入排序量该算法稳定（2） ”0）的作用是依枕中加兵.（I）算法的功能是求敏小值和最大信.Jchi1.d&(!p11iM)(ITHchi1.d)AATowhiJd)(2)【评分叁考】芯果用车逼日算法,则不蚣分：领果用其它逐好仲序遗历，后序遍历方法,参照此评分标总给分.我猊结构试国答案及谆分参考笫2页C共2页）_冷