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

全国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(nk>gn)D.h(n)是(X.n。3.指针p、q和r依次指向某循环胜表中三个相邻的结点.交换结点组和结点*r在表中次序的程序段是()A. p->nex1.=r:q->nex(=r->next:r->nex1.=q;B. >nex=r:r->next=<q>next=r>nex(:C. r>ne,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指向队尾元素所在的存储位付，则在少用一个元素空间的前提下，队列满的判定条件为()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.=(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.c»d,b»a,eB.c,a,db.cC-c,de,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分)请在每个空格中填上正确答案.错填、不填均无分,16 .数则的链式存储结构的特点是借助衣示数据元素之间的逻辑关系.17 .如果霜要对线性表频繁进行或操作,则不宜采用电序存储结构.topitop2S18ffi18 .如图所示，可以利用一个向量空间同时实现两个类型相同的校，其中栈I为空的条件是Iop1.=O,校2为空的条件是1.op2=n1.,则“栈满”的判定条件是,19 .静态存储分配的顺序串在进行插入、置换和等操作时可能发生越界.20 .广义表1.=(a,<b,()>的深度为.21 .任意一棵完全：叉树中，度为1的结点数以多为。22 .求最小生成树的克佟斯卡尔(KnISkaI)算法耗用的时间与图中的数目正相关.23 .在5阶B-树中，每个结点至多含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及其在电文中出现的频度构建的哈夫曼树如图所示.已知某段电文的哈夫曼娘码为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.inti)：厂从夙点V.出发进行深度优先搜索,访问夙点VjHIiYtvisitcdUI*/int()(Graph*g)Iinti,k：for(i=0：i<g->n:i+)/*g>n为图g的顶点数目，/visitcdi=0：for(i=k=0:i<g->n;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,成绩魅表A和B如图所示，画出执行算法O1(A.B)后A所指的推表:H1.1回|-HTI40-fHT90FH448ZHT1.56仄!BH"H4同-HT*INS31图(2)简述算法的功能.voidf31.(1.ink1.istA,1.ink1.istB>1.ink1.istp,q;p=A->ncxt:q=B->nex(;whi1.e(p&&q>(if(p>id<q>id)p=p->ncxt;e1.seif(p->id>q->i<i)q=q->ncxt;e1.seIif(p->score<60)if(q->score<60)p->scorcq->scorc;e1.sep>scorc-60;p=p->ncxt:q=q>>ext:32 .阅读下列算法,并回答问遨：设串s=*,OncWorIdOncDreamw,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;>)whi1.e(i+1.t<=1.s&&j>=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.KeyTyPex)(BSTNodc*p;if(T=NU1.1.)returnNU1.1.:p=133(T>!chi1.d,x);if(p!=NU1.1.)retump:if(T->key>x)r(umT;returnf33(T->rchi1.d.x);)五、算法设计题(本凝10分)34.假设线性表采用顺序存储结构,其类型定义如下：#define1.istSize100typcdcf'structintdata1.istSize;int1.ength:)Seq1.isi.5t1.ab1.e;编写舞法,将收序表1.中所有值为奇数的元本调悔到去的前端。夕;G铲滑夕产Tk肄叶2009年IoH高等教育电学考试全国隼一命题考试夕:-.单据匡H（本大籍蜗瓜IS,每小题2。；求30分）UkI.C2,C3.A4.BS.D二、境蜘（本大II共I0J,每小0：分,渤I两个空格.餐个MI分.共20分）16.指计(,q7撞入IK除1.18.top博松&top2"to碟娑!1.*p2网畔"2f仍-20.仍/21.122,边父二次脸Md44三、解*1广本大量共4忖»广盲小超S分，&»分）26.（i）p>8螳，攀"，-1世贻誓,储解27.e华小X"（/如每个字找*、'"6：数据鳍构试聂答案及评分知老Sn页（共3靖Z护夕丁仍2分严3分S分次3分）分,夕:扣完3分夕，（说明I每HH个顶点或边.扣OS分,伊,29.(96.”,宏48.22.31.5½37.II)第IS：（63“S5.SO.48.22.1.11.37.96）（2分）第僵乘"5oV”，牛壮仔也彳”分）fS3/法蜀演K（本大?荚，儡,每小气户."我20分）小，夕。30.（!）3（3分）&中7*./I"tFHT11国A中32.(Di脩3分为1汕啰产附装6中也有财将装A中的成缜修改为其在表B的成绩：但若其I个值扣%脾为8分.（2分）SOJ=OF哪美,乘曲每个婚弊（3父”玄回申tfi：*燧血次畋.并将%&现的位置依照蠢&.33.（!）依b是空期或T5访点的关键“C分）n'（2分）于给定值Xq厂面面空指计.（粉<3>如果二叉柞序树T中存在含力美健字大于给定值X的站点，鼾返回抬针指向34.voidf34(Tab1.e1.)瑞缪盛期返回警然r（Jf5*h份/伊k(除”夕可=1.->gtrwhi1.eU<J)（或者群数说明为：St。分)/小ist1.1分).>f仍，（循环控制.I分）:沸;3：湃whi1.e(i1.->datajJ-；!分）2分）=1.-Ada1.a籍多/1.>dasi仍，1.数抠X%i题答案及评夕；£第2页（共堪;参考答案二；:曙"1.；：湃紧fcr(i¼i<1.->1.enth½w)if(1.->datai)Sftt/-><bti-taj;1.->djt;/-)炉”仍，)尔豁.：算法描述鬻%可金黑评姆承!俨b那雷h”,或常解觌讪*觑解.卅JJ（吸汗分）V（福相制，2分）便依处理据柒，I分卜依娠，如-1.->tXf,I分）幡分）/R