《02331数据结构200510真题及答案.docx》由会员分享，可在线阅读，更多相关《02331数据结构200510真题及答案.docx（12页珍藏版）》请在课桌文档上搜索。
1、全国2005年10月高等教育自学考试全国统一命题考试数据结构试题课程代码：2331本试卷共7页，满分100分.考试时间150分忡.总分题号一二三四五核分人题分3020202010更杳人得分一、单项选择题(本大题共15小题,等小微2分，共30分)在短小题列出的四个符选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1 .若将数据结构形式定义为二元组(K.R),其中K是数据元素的有限集合，则R是K上1A.操作的有限集合B.映象的有限集合C,类鞭的有限集合D.关系的有限集合2 .在长度为n的地序表中州除第i个元武(IWiWn)时，元泰移动的次数为【】A.n-i+1
2、B.iC.i+1D.n-i3.若不带头给点的单链表的头指针为head,则该链表为空的判定条件是【】.head=NU1.1.B.head-11ext-NU1.1.C.head!=NU1.1.D.head-next=had4.引起循环队列队头位置发生变化的操作是B.入队A.出队C,取队头元素D.取队尾元素5,若进栈序列为1.2.3.4,5,6,且进校和出校UJ以穿插进行，则不可能出现的出栈序*列是A.2,4.3.1,5.6C.4,3.2.1.5.66.字符中通常采用的两种存储方式是A.散列存储和索引存储C.顺序存储和链式存储B.3,2,i,1.6,5D.23516.41B.索引存储和链式存储D.散
3、列存储和联序存储7.设主毋长为n,模式小长为m(mSn),则在匹配失败情况下.朴素匹配算法进行的无效位移次数为【】A.mB.nmC.n-tn1.D.n8 .:维数组A1218采用列优先的存储方法，若姆个元索各占3个存储取元，且第1个元素的地址为150,则元素A97的地址为【】A.429B.432C.435D.1：189 .对广义表1=(01.1),(：,0,(0.力)执行操作,门(3门山)的结果是【】.(c,f)B.(e,0)C.(f)D.()10 .下列图示的顺序在催结构表示的：叉料是【】6IAIB1.C1.6eIIIIIF1.O1.23456789!01112H.n个点的强连通图中至少含有
4、.n-1条有向边B.n条有向边C.n(nT)2条有向边D.n(nD条有向边12.对关键字序列(56,23.78.92,88,67.19.34)进行埴量为3的一越希尔排序的结果为11A.(19,23.56,34.78,67,88.92)B.(23,56,78,66,88,92.19,34)C.(19,23,34,56,67,78,88.92)I).(19.23,67,56,34,78,92,88)IX若在9PfrB-树中插入关墟字引起结点分裂,则该结点在插入前含有的关键字个数为.4B.5C.8D.9M由同一关键字集合构造的各探二叉排序树1A.其形态不一定相同，但平均查找长强相同B.其形态不一定相
5、同,平均查找长度也不一定相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同,平均查找长度也都相同15 .1SAM文件和VSAM文件的区别之一是【】A.前者是索引顺序文件，后者是索引非顽序文件B前者只能进行顺序存取，后者只能进行随机存取C.前方建立睁态索引结构,后者建立动态索引结构D.前者的存储介质是破盘，后者的存储介质不是破盘二、埴空题（本大题共10小题，年空2分，共20分）16 .数据的逻轼结构在计算机存储涔内的表示,称为数据的17 .删除双向循环链表中*p的前.驱结点（存在）应执行的语句是.IS-栈下溢是指在.时进行出找悚作.19 .已知substr（s,i,Ien）函数的功能
6、是返回申S中第i个字符开始长度为Ien的子申,Str1.aI函数的功能是返回串s的长度.若s=ABCDEFGIIIJK*,t-wABCD*,执行运笄substr（s,（t）,SIr1.Cn（。）后的返回值为。20 .去除广义表1.S=（ag配，aJ中第1个元索，由其余元素构成的广义衣称为1.S的21 .已知完全二叉树T的第5层只有7个结点，则该树共有一个叶子结点.22 .在有向图中.以顶点V为终点的边的数目称为V的.23 .当关摄字的取值范围是实数集合时,无法进行箱排序和排序.24 .产生冲突现象的两个关键字称为该散列函数的。25 .假设改列文件中一个桶能存放m个记录，则桶“溢出”的含义是,当
7、需要插入新的记录时，该桶中。三、解答应（本大遨共4小区.每小Sfi5分,共20分）26 .我设以数组Seqnb存放循环队列的元素,设变处renr和分别指示循环队列中认尾元素的位置和元素的个数.(D写出队满的条件表达式：(2)写出队空的条件表达式：(3)设m=10,rear=13,que1.en=19,求队头元素的位置：(4)写出一般情况下认头元素位置的表达式.(1)(2)(3)(4)27 .已知一棵：叉树的中序序列为ABCDEFG,层序序列为RAFEGCD,请画出该：叉树。28 .而出下图所示有向图的所有强连通分量.29 .对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较.(
8、D假设关犍字集合为此2,3.1,5.6.7),试举出能达到上述结果的初始关谈字序列:(2)对所举序列进行快速排序,写出排序过程“(2)四、算法回读题(木大题共4小题，诲小SS5分,共20分)30 .阅读下列算法，并回答问题：(D设顺序表.=3,7,II,14.20,51),写出执行f30(1.,15)之后的!.：(2)设顺序表1.=01,7,10,14,20,51),写出执行f30(41.,10)之后的1.：(3)简述算法的功能.voidf30(Seq1.ist1.,DataTypex)(i11ti=0.j：WhiIe(i1.engthh&x1.-datai)i”;if(i1.ength&x=
9、1.-datai)for(j=i+1.:j1.engthjj+)1.-dataj-1.=1.-1.ength一：)e1.se(for(j=1.-1.ength:ji;j-)1.-dataj=1.-dataj-1.：1.-datai=x;1.-1.ength+:)F(1)(2)(3)31.己知图的邻接表表示的形式说明如下；defineMaxMum50图的最大顶点数typedefstructnodeintE1.djVex;邻接点域structnodenext;域指针域EdgeNode;IyPVderstruct边表结点结构描述charvertex:/项点域EdgeNode*firstedge;边表
10、头指针VertexNode;/顶点表结点结构描述typedefstruct(VertexNodeadj1.istMaxNu三:邻接表i11t11.e:图中当前的顶点数和边数A1.Graph:邻接表结构描述下列算法输出图G的深度优先生成树(或森林)的边阅读算法，并在交缺处填入合适的内容，使其成为一个完整的算法，typedefenumFA1.SE,TO1.E)Boo1.ean;Boo1.eanvisitedMaxNum;voidDFSForest(A1.GraphtG)for(i=0;in;i+)visitedi=for(i-0;in:iif(!visitedi)DFSTree(G,i);void
11、DFSTree(1.GraphGinti)(EdXeNUdevisitedi=TRUE;p=G-adj1.isti.firs1.edge:whi1.e(p!=N1.,1.1.)(if(!visitedpadjvex)printf(*m,Gadj1.isti.vertex.G-adj1.istp-adjvex.vertex);一;(3)32.问读下列算法,并回答问邈：(D假设数组1.8-3,0,5,1,6,4,2,7).写出执行函数调用f32(1.8)后的1.：(2)写出上述函数调用过程中进行元素交换操作的总次数.voidf32(intR,intn)(inti,t：for(i=0;in-1.：i
12、+)whi1.e(Ri!=i)t=RRi:RRi=Ri:Ri=t:(1)(2)33.已知带头结点的单能去中的关键字为整数，为提高交找效率，需将它改建为枭用拉链法处理冲突的散列衣。设散列表的长度为小散列函数为HiISh(key)=kcy%n.琏表的结点key；next,请在空缺处填入适当内容，使其成为一个完祭算法。voidf33(1.ink1.ist1.,1.ink1.istH,int)(由带头结点的单超表1.生成散列表II,散列表生成之后原鞋表不再存在inti,J;1.ink1.istp,q;for(i=0;inext;uhiIe(p)q-pnext;j=p-key;；Hj=P：；)freed
13、)：(1)(2)(3)五、算法设计阳(本大JSK)分)收设以带双亲指针的二叉地表作为二叉树的存储结构,其结点结构的类型说明如下所示；WPedefcharDateType:tyedefstructnodeDataTypedata;structnode*1.chi1.d,*rchi1.d;左右孩子指1针structnode*parent：指向双亲的指针BinTNode:tyedefBinTNode*BinTree;11px为指向非空：叉树中某个结点的指针，可借助该结构求得PX所指结点在：叉树的中序序列中的后继，(D就后维的不同情况.简要叙述实现求后继操作的方法：(2)弟写算法求PX所指结点的中序序
14、列后继,并在算法谙句中加注注择.*jBAit2392005年IO月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码2331）一、（本大共15小,小2分.共30分）二、2（本大兴K）小小2分，共20分）16.存硒t构7.ppriorp-ppfior;（1分）p-prior-n三p；（J分）（*p-nor-prior-nextap1.（1分）p-pprir-pc;（1分）*g19.-EFGH-20.M21.I1.22.人次23.M24.周文口25 .巴有0个词义词的记录（或：ew-4S三*:巳）三、WW（*大共4小,每小分.共20分）26 .（1）adjvex)p三pnext(
15、2分)(2分)32.(I)1.(8-i0.1.2,3.4.5,6.71(3分)(2)共进行S次元*交换。(2分)33.(1)NUU.(1分)(2)p-nextzH(j)(2分)(3)P-A(2分)洲。*数据绪构成0答案及评分参考第2(共3页)五、Kftttttf1.（本大IO分）34. （1）分网用情况讨论当N的右子材不为空时,则从*px的右旅于开始,沿其左族子住下充找,亶至找剜一个没有左核子的结点为止,则该给点为R在中序序列中的后,；（2分）当W的右于树为空时.则论px的双亲指计It向上看我.直至找到其左于树中包含PX的年修祖先,用嫉祖先结点为PX在中序序列中的启.i.（2分）（2）BiaTreeD4（BinThIepx）BinTreeq三px-dUd；(1分)(I分)(I分)（I分）（I分）（1分）tf(q!-NU1.1.)I卷左M子往下查找pxq;wh11e(p*_Idu1.d三FnJ1.1.)pxpx!chi1.d；e4希双亲指针法向上查找*rftUe(p!NU1.1.dr&px-rcki1.d三三q)|-Eum展；/返回所找到的中序序列后缗绪点的指针/或者无后曜结点时返烟空指钟I
