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

上传人:夺命阿水 文档编号:1643031 上传时间:2024-11-24 格式:DOCX 页数:13 大小:164.09KB
返回 下载 相关 举报
02331数据结构200910真题及答案.docx_第1页
第1页 / 共13页
02331数据结构200910真题及答案.docx_第2页
第2页 / 共13页
02331数据结构200910真题及答案.docx_第3页
第3页 / 共13页
02331数据结构200910真题及答案.docx_第4页
第4页 / 共13页
02331数据结构200910真题及答案.docx_第5页
第5页 / 共13页
点击查看更多>>
资源描述

《02331数据结构200910真题及答案.docx》由会员分享,可在线阅读,更多相关《02331数据结构200910真题及答案.docx(13页珍藏版)》请在课桌文档上搜索。

1、全国2009年IO月高等教育自学考试数据结构试题课程代码:02331一、单项选择题(本大题共15小题,每小题2分,共30分)在每小迅列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.楣选、多选或未选均无分.1,按值Ur否分解,数据类型通常可分为两类,它们是()A.静态类型和动态类型B.原子类型和表类型C,原子类型和结构类型D.数组类型和指针类里2.对于三个函数f(n)=2008n+8n2+96000,g(n=8n1+8n+2OO8h(n)=8888n1.ogn+3n2,下列陈述中不成立的是()A.f(n)(Kg(n)B.g(n)O(n)C.h(n)是0(nkgn)D.h

2、(n)是(X.n。3.指针p、q和r依次指向某循环胜表中三个相邻的结点.交换结点组和结点*r在表中次序的程序段是()A. p-nex1.=r:q-nex(=r-next:r-nex1.=q;B. nex=r:r-next=next=rnex(:C. rne,M=q;q-next=r-next;p-next=r;D. r-ncxt=qsp-ncxt=r:q-ncxt=r-ncx1.:4若进极次序为a.b,c,旦进校和出栈可以穿插进行,则可能出现的含3个元素的出栈序列个数是()A.3B.5C.6D.75 .翼设以数组An存放循环队列的元素,其头指针伍,m指向队头元素的前一个位置、尾指针rear指向

3、队尾元素所在的存储位付,则在少用一个元素空间的前提下,队列满的判定条件为()B.(front+1.)%n=rcarD.(rcar+1.)%n=IrontA.rear=frontC-rear+1=fron6 .串的操作函数Str定义为:it11strtcharts)(char*p=s;whi1.e(*p!=0)p+:returnp-s:I则str(abcde)的返回值是)A.3B.4C.5D.67 .二批数组A106采用行优先的存储方法,若姆个元素占4个存储单元,已知元素A34的存储地址为IO(K).则元素A43的存储地址为()A.1020B.1024C.1036D.12408 .对广义表1.=

4、(a,()执行操作tai1.(1.)的结果是()A.()B.(0)C.aD.(八)9.已知二叉树的中序序列和后序序列均为ABCDEF.则该二叉树的先序序列为(A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA10.已知森林F=(T,T2,T,T4,T5),各棵树TNi=I,2,3,4,5)中所含结点的个数分别为7,3.5,I,2,则与F对应的二叉树的右子树中的结点个数为(.2B.3C.8D.I1.11 .若非连通无向图G含有21条边,则G的顶点个数至少为(*A.7B.8C.21D.2212 .如图所示的有向图的拓扑序列是()题12图A.cd,ba,eB.c,a,db.cC-c,d

5、e,abD.c.a.b.d.c13 .而关键字序列(6,1,4,3,7.2.8.5)进行快速排序时,以第1个元素为基准的一次划分的结果为A.(5,I.4.3,6.2,8,7)C. (5.I.4.3.2.6.8.7)14 .分块查找方法将表分为多块,并要求(A.块内有序C,各块等长15 .便于诳行布尔查询的文件组织方式是(A. A序文件C.敌列文件二、填空题(本大邈共10小题,每小题2分,B. (5.I.4,3.2,6,7,8)D. (8.7.6.5.4.3,2.1)B.块间有序D.链式存储)B.索引文件D.多关键字文件若有两个空格,每个空格I分,共20分)请在每个空格中填上正确答案.错填、不填

6、均无分,16 .数则的链式存储结构的特点是借助衣示数据元素之间的逻辑关系.17 .如果霜要对线性表频繁进行或操作,则不宜采用电序存储结构.topitop2S18ffi18 .如图所示,可以利用一个向量空间同时实现两个类型相同的校,其中栈I为空的条件是Iop1.=O,校2为空的条件是1.op2=n1.,则“栈满”的判定条件是,19 .静态存储分配的顺序串在进行插入、置换和等操作时可能发生越界.20 .广义表1.=(a,的深度为.21 .任意一棵完全:叉树中,度为1的结点数以多为。22 .求最小生成树的克佟斯卡尔(KnISkaI)算法耗用的时间与图中的数目正相关.23 .在5阶B-树中,每个结点至

7、多含4个关键字,除根结点之外,其他结点至少含个关键字24 .若序列中关键字相同的记录在排序前后的相对次序不变,则称该排序算法是的,25 .常用的索引顺序文件是文件和文件.三、解答跟I本大震共4小题,每小踵5分,共20分)26 .如图所示,在nXn矩阵A中,所有下标值满足关系式i+jVn+1.的元索蚓的值均为0,现将A中其它元素按行优先顺序依次存储到长度为n(n+1.N2的一维数组Sa中,其中元素a.存储在Sa0.设n=IO,元素;U,存储在Sap,写出下标P的伯:(2)设元泰即j存他在Sak中,写出由i,j和n计算k的一般公式.OO,期26图27 .由字符集(s,1,a,e,1及其在电文中出现

8、的频度构建的哈夫曼树如图所示.已知某段电文的哈夫曼娘码为I1.100(X”0100.28 .已知无向图G的邻接表如图所示.网28图(D1.ff1.i出血无向图:29 .对序列(48,37.63.96.22,31,50,S5,II)进行升序的堆排序,写出构建的初始(大根)堆及前两趟建堆之后的序列状态.初始堆:第Iah第2曲四、算法阅读题(本大题共4小题,为小题5分,共20分30 .阅读下列算法,并回答问题:(D无向图G如图所示,写出算法f3(X&G)的返回值;(2)简述算法口0的功能。C#dCfineMaxNum2()题30图intVisited1.MaxNun;voidDFS(GniPh*g.

9、inti):厂从夙点V.出发进行深度优先搜索,访问夙点VjHIiYtvisitcdUI*/int()(Graph*g)Iinti,k:for(i=0:in:i+)/*gn为图g的顶点数目,/visitcdi=0:for(i=k=0:in;i)if(visi1.ed(i)=0(k:DBS(g.i):returnk:31 .假设学生成例按学号增序存储在带头结点的单链表中,类型定义如下:(ypcdcfMruciNode|intid;*学号in(score:*成绩,structNode4ncxt:)1.Node.*1.ink1.ist:间诜算法门1,并回答问题:(D设结点结岗为1.ii也生丝1,成绩魅

10、表A和B如图所示,画出执行算法O1(A.B)后A所指的推表:H1.1回|-HTI40-fHT90FH448ZHT1.56仄!BHH4同-HT*INS31图(2)简述算法的功能.voidf31.(1.ink1.istA,1.ink1.istB1.ink1.istp,q;p=A-ncxt:q=B-nex(;whi1.e(p&q(if(pidid)p=p-ncxt;e1.seif(p-idq-incxt;e1.seIif(p-scorescorescorcq-scorc;e1.sepscorc-60;p=p-ncxt:q=qext:32 .阅读下列算法,并回答问遨:设串s=*,OncWorIdOnc

11、Dreamw,t=One.pos是一维整里数组.写出算法O2(s.t.POS)执行之后得到的返回值和POS中的值:(2)简述算法132的功能。i11str1.echar*s);尸返回甲S的长度*/intindcx(char*st.char*。:/若串t在用St中出现.则返回在串St中背次出现的下标值,否则返回int2(char*s.char*t.intPoS)(inti,j.k.Is.1(;Is=SirIcn(三);It=SirIcn(I);if(IS=OI1.1.1.=O)return-1:k=0;i=0;do(j=indcx(s+i.t):ifS=O)posk+=i+j;i+=j+1.t;

12、)whi1.e(i+1.t=0);returnk;)33 .二叉排序树的存储结构定义为以下类型:IypedefintKeyTypc;tyedefstructnode(KeyTypekey:产关键字项/InfoDPeOtherinfb;/*其它数据项*/%1.)S题33图sruc(node*1chi1.d,*rchi1.d;芦左、右孩干指针*7)BSTNodc.*BSTrcc:阅读算法f33.并回答问题:对如图所示的二叉排序树T,写出f33(T,8)返回的指针所指结点的关键字;G(2)在哪些情况下算法133返网空指针?(3)简述算法瞪3的功能.(3)BSTNode*B3(BSTreeT.KeyT

13、yPex)(BSTNodc*p;if(T=NU1.1.)returnNU1.1.:p=133(T!chi1.d,x);if(p!=NU1.1.)retump:if(T-keyx)r(umT;returnf33(T-rchi1.d.x);)五、算法设计题(本凝10分)34.假设线性表采用顺序存储结构,其类型定义如下:#define1.istSize100typcdcfstructintdata1.istSize;int1.ength:)Seq1.isi.5t1.ab1.e;编写舞法,将收序表1.中所有值为奇数的元本调悔到去的前端。夕;G铲滑夕产Tk肄叶2009年IoH高等教育电学考试全国隼一命题

14、考试夕:-.单据匡H(本大籍蜗瓜IS,每小题2。;求30分)UkI.C2,C3.A4.BS.D二、境蜘(本大II共I0J,每小0:分,渤I两个空格.餐个MI分.共20分)16.指计(,q7撞入IK除1.18.top博松&top2to碟娑!1.*p2网畔2f仍-20.仍/21.122,边父二次脸Md44三、解*1广本大量共4忖广盲小超S分,&分)26.(i)p8螳,攀,-1世贻誓,储解27.e华小X(/如每个字找*、6:数据鳍构试聂答案及评分知老Sn页(共3靖Z护夕丁仍2分严3分S分次3分)分,夕:扣完3分夕,(说明I每HH个顶点或边.扣OS分,伊,29.(96.”,宏48.22.31.537.

15、II)第IS:(63“S5.SO.48.22.1.11.37.96)(2分)第僵乘5oV”,牛壮仔也彳”分)fS3/法蜀演K(本大?荚,儡,每小气户.我20分)小,夕。30.(!)3(3分)&中7*./ItFHT11国A中32.(Di脩3分为1汕啰产附装6中也有财将装A中的成缜修改为其在表B的成绩:但若其I个值扣%脾为8分.(2分)SOJ=OF哪美,乘曲每个婚弊(3父”玄回申tfi:*燧血次畋.并将%&现的位置依照蠢&.33.(!)依b是空期或T5访点的关键“C分)n(2分)于给定值Xq厂面面空指计.(粉如果二叉柞序树T中存在含力美健字大于给定值X的站点,鼾返回抬针指向34.voidf34(Tab1.e1.)瑞缪盛期返回警然r(Jf5*h份/伊k(除”夕可=1.-gtrwhi1.eUf仍,(循环控制.I分):沸;3:湃whi1.e(i1.-datajJ-;!分)2分)=1.-Ada1.a籍多/1.dasi仍,1.数抠X%i题答案及评夕;第2页(共堪;参考答案二;:曙1.;:湃紧fcr(i;i1.enthw)if(1.-datai)Sftt/-djt;/-)炉”仍,)尔豁.:算法描述鬻%可金黑评姆承!俨b那雷h”,或常解觌讪*觑解.卅JJ(吸汗分)V(福相制,2分)便依处理据柒,I分卜依娠,如-1.-tXf,I分)幡分)/R

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 在线阅读 > 生活休闲


备案号:宁ICP备20000045号-1

经营许可证:宁B2-20210002

宁公网安备 64010402000986号