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

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

1、全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单修选异题(本大J共IS小愚，每小题2分，共30分)在每小JI列出的四个备选项中只有一个是符合题目聂求的，靖将其代码填写在题后的括号内.传选、多选或未选均无分.1 .如果在数据结构中每个数据元素只可能有一个W接前.驱，但可以有多个直接后继，W1.该结构是()B.队列D.图A.栈C.树2,下面程序段的时间更杂度为(for(i=0:im;i+)for(j=0：jnex1.=headB.p-next-next=headC.pnexi=NU1.1.D.p=head4 .若以Sft1.X分别表示进校和退校操作，则对初始状态为空的栈可

2、以进行的栈操作系列是()B.SXXSXSSXD.SSSXXSXXB.含有相同的字符集D.申的长度相等且财应的字符相同A.SXSSXXXXC.SXSXXSSX5 .两个字符审相等的条件是A.邓的长度相等C.都是非空申6 .如果将矩阵An*n的每一列看成一个子表，整个矩阵看成是一个广义表1.,即1.=(a,a皿),(a*a.n),并且可以通过求表头head和求表尾IT的运算求取矩阵中的每一个元素.则求得心的运算是)A. head(tai1.(head(1.)C.tai1.(head(tai1.(1.)B. head(head(head(1.)D.head(head(tai1.(1.)7 .已知一棵

3、含50个结点的二叉树中只有一个叫子结点,则该树中度为】的结点个数为A.0D.49C.488 .在一个具有n个顶点的有向图中，所有顶点的出度之和为Dm.则所有顶点的入度之和为()B.Dtu-1D.nCDOe+19.如图所示的行向无环图可以得到的拓扑序列的个数是)A.3B.4C.5D.6IO.如图所示的带权无向图的最小生成树的权为(A.51B.52C.54D.5611 .对长度为n的关健字序列进行堆排序的空间复杂度为()A.01.og2n)B.0C.O(n)D.0(n*1.og21112 .己知用某种排序方法对关键字序列(51,35.93,24,13.68.56.42.77)迸行排序时,前两楞排序

4、的结果为(35.51.24.13.68.56.42.77.93)(35.24,13,51,56.42.68.77,93)所采用的排序方法是()A,插入排序B.官泡持序C.快速排序D.归并排序13 .已知收列表的存储空间为TI(1.I8.散列函数H(key)=kcy%17.并用二次探测法处理冲突。放列表中已插入卜列关键字：T1.S)=39,T(6)=S7和Tp)=7,则下一个关键字23插入的位置是(A.T2B.T4CT网D.T(IOU.适宜进行批出处理的文件类型是()A.顺序文件B.索引顺序文件C.欣列文件D.多关键字文件15.VSAM文件的索引结构为A.B悯C.BWB.二叉排序树D.最优二叉树

5、二、填空总（本大共IO小题，每小JB2分，共20分）请在每小JB的空格中填上正确答案.错短、不填均无分.16 .如果某籁法时于规模为n的同魄的时间耗费为T（n）=3n.在台计算机上运行时间为I杪，则在另一台运行速度是共64倍的机器上，用同样的时间能解决的问超规模是原问题规模的倍.17 .将两个长度分别为m和n的递增有序单链表，归并成一个按元素通及仃序的单鞋衣.可能达到的豉好的时间更杂度是18 .己却循环队列的存储空间大小为m,队头指针from指向队头元素，队尾指针rear指向队尾元素的下一个位置.则在队列不满的情况下,队列的长度是.字符串-Sgabacbadfgbacst,中存在有个与字符；1

6、；“ba”相同的GI；.20 .假设以列优先顺序存储二维数组A58.其中元素A00的存储地址为I.OCa1.）.且每个元素占4个存储单元，则数级元素Aij的存储地址为。21 .假设用去示树的边（其中X是y的双亲），己知一棵的的边柒为（.,.该树的度是,22 .n个顶点且含有环路的无向连通图中,至少含有条边.23 .在一般情况下用自接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是.24 .和：分送我相比，顺序杳找的优戊是除了不要求去中数据元素有序之外，对姑构也无特殊要求.25 .顺序文件中记录存放的物理顺序和顺序一致.三、解答JB（本大意共4小题，每小J1.5分，共20分）序列.

7、题26图前序序列:26 .由森林转换得到的对应：叉树如图所示，写出原森林中笫三悌树的前序序列和后序后序序列：27 .图的部接表的类型定义如下所示：“defineMaxVertexNum50typcdc1.Sirucinodeintadjvcx:structJe*next:IEdgeNode:IypcdcfStruc1.VcrtcxTypevertex;EdgeNodetfirsedge;IVcrtcxNodc;IyPCdCfVcrtcxNodcAdj1.ist1.MaxVcrtcxNum;IyPedefstruct(Adj1.istadj1.is(;intn.c:A1.Graph:为便于删除和

8、插入图的顶点的操作，可将领按表的表头向量定义为链式结构，两种定义的存储去示实例如下图所示，请写出正新定义的类型说明，二MZB22FH-i11:fcC1.E_H2IS27图28.某类物品的娘号由一个大写英文字母及2位数字(0.9)组成，形如E32.运刖基数排序时下列物品编号序列进行按字典序的排序,写出每一趟(分配和收集)后的结果。EI3,A37,F43,B32，B47,E12,F37,B12第一卷第二呼第二:搐29.(1)画出对表长为13的有序顺序去进行二分查找的判定树：(2)已知关键字序列为(12.14,16.21,24,28.35.43,52,67,71.84,99),写出在该序列中二分查找

9、37时所需进行的比较次数.(1)(2)四、算法网读题(本大题共4小题，每小JS5分，共20分)30 .已知线性表的存储结构为顺序表，阅读下列峰法，并回答问遨；(1)改魏性表1.=(21,-7,-8,19,0.-Ih34.30,-10),写出执行EX&1.)后的1.状态：(2)简述算法BO的功能.voidOO(Seq1.isi*1.)!intij;for(i=j=0ug1.h:i+)if(1.-dau(i=0)(if(i!=j)1.xJaaj=1.-x1.aa(i:jf)1.-gth=j;I(1)(2)31 .阅读下列算法，并回答问题；()Q.Q1.4UQ2都是队列结构，谀队列Q=1,0.-5.

10、2.-4,9),其中1为队头元索.写出执行f31(&Q.&Q1.&Q2)之后认列Q、Q1.和Q2的状态：(2)陆述律法f31.的功能。(注：Ini1.Queuc、EnQueue.DeQUeUe和QUCUeEmP1.y分别是队列初始化、入列、出队和判队空的操作)void111.(Qucuc*Q,Qucuc+Q1.Qucuc*Q2)|inte;IniiQueue(Q1.);InitQucuc(Q2);whi1.eCQucucEnipiy(Q)e=DcQucuc(Q)：if=O)EnQueue(Q1.e):e1.seEnQueue(Q2,e)I)(1)(2)32 .阅读下列算法，并回答问题：(I)假

11、设申由合法的英文字母和空格殂成，并以MT作结束符。设申s=U1.111.Jam1.Ja1.J1.J1.J!itudcn门1.J表示空格符)写出f32(三)的返网值：(2)简述算法扫2的功能i11(02(charts)inti.n.Mwond:n=inword=0;for(i=Oisi!=Oi+)if(s(i!=*1.J&nword=0)inwond=1.;n+:)e1.seif(si*u*&inword三三1.)inword=f1.;returnn:J(1)(2)33 .回读下列对正整数关犍字序列1.操作的算法，并【可答问时：设S(28,19,27,49,56,12,10,25,2(X50).

12、写出03(1.4)的返回值：(2)陆述函数J33的功能.intPanition(Scq1.iste1.,int1.ow,inthigh);对U1.oW.high做划分,返I可基准记录的位跣并使左部的关键字都小于或等于基准记录的关迸字，右部的关键字林大于基准记录的关键字intf33(Scq1.is1.1.intk)int1.ow.high,pivoipos;Iow=I;high=gth;if(k1.owQhigtOreturn-1;doJpivxos=Paftition(&1.1.ow.high)；/调用快速排序的划分算法if(pivopos1.ow=pivo1.ps+1：e1.seif(piv

13、ocposk)high=pivotpos-1;)whi1.e(pivops!=k):return1.data(pivopos;)(1)(2)五、算法设计(本io分)34.二叉排序树的类鞭定义如MIypedefstructBSTNodeIi二叉排序树的结点结构intdata;数据域siructBSTNodcTchiIdJrchiId;左、右核子指针BSTNodc.xBSTree:设计递归算法,蜕计一棵二叉排序树T中值小于a的结点个数.285绝密启用前2008年10月高等教育自学考试全国统一命题考试夕数据结构试题答案及评分参考（.课程代码2331）一、单项选择题（本大眩共15小题，卷小题2分，共30分）18.(rear-front+m)%m19.320.1.(a00)+4(5j+i)21.322.n-23.选择排序24.存储25.逻辑共20分）三、解答强（本大JS共4小题，播小髭5分,26 .前序序列：GHIJ后序序列：HJIG（2分）（3分）27 .typedefstructArcNodeVNode,advex;I1.该瓠所指向的顶点的位置（2分）StructArcNodeFextarc;指向下一条弧的指针.ArcNode;typedefstructVNodeVertexTypedata;/顶点信息structVNodeFextVertex;指向下