02331数据结构200701真题及答案.docx
2007年1月高等教育自学考试全国统一命题考试数据结构试题课程代码2331一、单项选择迷(本大逊共15小曲，每小髭2分，共30分)在每小迫列出的四个备选项中只有一个是符合邈目要求的，请将其代码填写在船后的括号内，错选'多选或未选均无分.I.抽象数据类型的三个组成部分分别为(>A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储费构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型2,若算法中语句的加夫频度为T(n)=2OO6nWnk>gn+291.ug2n.则其时间双杂度为(A.O(Iogn)B.O(n)C.(XnIogn)D.O(1.og3n)3.若线性次的插入和删除操作婉繁地在表头或无尾位置进行，则更适宜采用的存储结构为A.无头结点的双向鞋表B.C.无头结点的单链表D.4 .上溢现象通'常出现在()A.顺序栈的入校操作过程中B.C,鞋栈的入栈操作过程中D.5 .已知串S="aabacbabcaccab".t1.=wt在串s中首次出现的位置,则能求得串A. substr(s1.s.6.in<1.ex(s.1.1.);subs1.r(s2.indeB. subs1.r(SI.7.index(s.t1.>);substr(s2.s.i11de:C.subsr(s1.3,6.index(s.t2);SUbSIr($2(Sjndex(D.substr(sI,s,6,indcx(s,t2);substr(s2,sjndcx16.对广义表1.=(a、b),(c,d),(c,f)执行head。A.dB.C. (e)D.7.已如一探完全二叉树有64个叶子结点，A.7B.带尾指针的循环链表，带头指针的循环就表,顺序栈的出栈操作过程中,链校的出栈操作过程中bc",t2="cban,.函数indcx(s,t)的返回值为串"abcacbau的操作序列为<)x(s.t1.).1>trca1.(s1.s2):«s.t1.).1.):strcat(s2.s1.);s,t2)3)trca(s1.s2);(s.t2),3);strcat(s2.s1.):ai1.(head(tai1.(1.)力操作的结果是()C(e,f)则该树可能达到的最大深度为()8D.IO8.若探：叉,树有I1.个叶子结点，则该二叉树中度为2的站点个数是A.10B.I1.C.12D.不确定的9 .对于有向图其邻接矩阵表示相比邻接表表示更易于进行的操作为)A.求一个顶点的邻接点B.求一个顶点的度C.深度优先诩历D.广度优先地历10 .若用邻接矩阵表示带权有向图，则顶点i的入度等于矩阵中()A.第i行非8元素之和B.第i列非8元素之和C.第i行非8元素个数D.第i列非8元素个数11 .对关堆字序列(5,I，4,3,7,2.8.6)进行快速排序时，以第一个元素5为基准的一次划分的结果为()A.(1.2,3,4,5.6.7,8)B.<1.4.3.2.5.7.8.6)C.(2.I.4,3,5,7.8.6>D.(8,7.6,5,4.3.2.I)12 .下列二叉树中,不平衡的二叉树是()13 .下列序列中，不构成堆的是)A. (1,2,5.3,4,6,7,8,9,10)B. (10.5.8.4.2.6.7.I.3)C. (10.9,8.7,3.5.4.6.2)D. (1,2.3.4,10,9.8,7.6.5)14 .主关键字能唯一标识)A.一个记录B.一组记录C.一个类型D.一个文件15 .稀疏卷引是指在文件的索引表中()A.为好个字段设一个索引项B.为辩个记录设一个索引项C.为好组字段设一个索引顶D.为每俎记录设一个索引项二'填空题(本大亚共】。小Sfi,每小题2分，共20分)请在每小Sfi的空格中填上正确答案.错填、不填均无分,16 .流式存储结构的特点是借助来表示数据元素之间的逻辑关系，17 .假设带头站点的非空球循环链衣中仅设尾指针1.,则在笫I个结点之前插入指针S所指结点的哂句依次是:.18 .无表头结点的桂队列Q为空的条件是.19 .不含任何字符的申称为,20 .假设按行优先IBi序将一个20阶的三对角矩阵A压缩存储在一维数组Q中，其中Q1.O)存放矩阵的第I个元素au,那么矩阵元素a34在Q中的存偌位置k=。21 .前序序列和中序序列不相同的二叉树的特征足.22 .在含有n个顶点的连通图中，任意两个不同顶点之间的简垠路径的最大长度为.23 .Jf1.排序方法对关键字序列(20.25.12.47.15.83.30.76)进行排序时.的三趣排序的结果为：20.12,25,15.47.30.76.8312,20,15,25.30,47,76.8312,15.20,25.30.47.76.8324 .哈希衣常用的两类解决冲突的方法是和,25 .倒排文件和买理友文件的主要区别在于的结构不同.三、解答超(本大踵共4小题，每小题5分，共20分)26 .已知主事为"ccgcgccgcgcbcbv，模式中为"CgcgCbw.下表所列为按照朴素的小匹配算法进行的前两雄匹配，请洙续完成余下各玛匹配，宜至结束,cCBCSCgCgCbCbCBc.8CIgCbi1?1.1：*1OI2345678910H1213匹配失败时j=1.匹配失败时j=527.己知帝权图G如图所示,画出图G的一棵最小生成树。28.对于亘接宜人徘序,格尔排序,甘泡排序,快速排序,直接选择排序,堆排序和归并排序等排序方法，分别写出：(1)平均时间复杂度低于O<n2)的排序方法:(2)所需辅助空间最多的排序方法：(3)最好情况和最坏情况下的时间复杂度相同的排序方法.(1)(2)(3)29 .己知棵践索化的：叉择序树如图所示。(I)说明该利的税索化是基于何种遍历次序的：(2)在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树.四、算法阅读题(本大题共4小题，每小题S分，共20分)30 .假设线性曾采用顺用存储结构,表中元素值为整型.阅读算法f30,并I可答下列问应：(I)设加序&1.=(3,7,321,1,8,7.3),写出执行算法f30后的1.;(2)简述算法f30的功旎.voidf3(XSeq1.iS1.*1.)(intij.k；k=0;forti=0;i<1.->g1.h:i+)tbr(j=(kj<k&&1.->data(i)!=1.->data(jjy+);if(j=k>(if(k!=i)1.-xJatak=1.->daafikk+:)1.->gth=k;(I)31 .例读算法f31,并回答下列问JS：（1）设队列Q=（1.3.5.2.4.6）.写出执行算法f31后的队列Q：（2）简述算法f31的功能.voidf31.(QucucfQ)DaiaTypcc;if(!QucucEmpty(Q)XC=DeQueue(Q);f31(Q);EnQeue(Q.e);I)1 1)2 2)32 .已知树的存储结构为孩子兄弟燧表其类型定义如下:IyPedefsiruciCSTNodechardata;Mruc1.CSTNodc1.cftmschi1.d,*rightsib1.ing;ICSNodc.4CSTrcc:阅读函数f32.并回答下列问题：(1)对于如图所示树,写出函数调用f32(T)的返回值:(2)简述柯T非空时函数f32返回值的含义。intD2(CSTreeT)intc;CSTrccp:if(!-I->1.cftmostchi1.d)return1:e1.seIc=0:for(=T>1.eftmoscchi1.dpp=>rightsib1.ing)c+=f32(p):returnc:(I)33 .已知数组R1.p1中的元的序列为一个大根雄，函数AdjUSt（R,p瀚R1.p乘新诩整为一个大根堆.（1）在函数AdjUS1.的空缺处填入适当内容，使其成为一个完整的函数：（2）简述函数f33<R.n）的功能。voidAdjuWScq1.istRjntp)Iintij:RecType1.enp=R(p:I=P：j=i2;whi1.c(j>-IRU1.keyV1.emP.key)<R>=R1.jhi=j：.R(iJ=;Ivoidf33(Seq1.istR.intn)intk;fortk=2;k<=n:k+)Adjust(R.k);I(1KD(2)五、算法设计题(本大逝IO分)34.已知有向图的邻接表表示的形式描述如下：defineMaxNurn50图的最大顶点数typedefsmc(ArvNode|iniadjvex;邻接点域structArcNode*ncxtArc;座域ArcNodc;孤结点类型typcdcfstructcharvertex;ArcNodc*trs1.Arc;顶点域弧表头指针IVcrtcxNcx1.e:顶点表结点类型typcdcfstructVertexNodeadj1.is(MaxNumhin(n,c;“邻接去图中当前的顶点数和边数IA1.Graph;“邻接表类型按以下函数原型编写算法,求行向图G中第i顶点的度,并写出算法的时间更杂度.inif34(Zk1.GraphtGinti);2007年1月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码2331）.A<'“c、.'一、单项选择J三(本大地共15小题，每小题2分，共30分)I.A2.C3.B4.A5.C8.A9.B10.D13.D14.A15.D7.B12.C二、填空IK（本大题共10小翘，每小段2分，若有两个空格，每个空格1分，共20分）16.17.18.19.20.21.指针8
