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

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

1、2011年10月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)一、单项选邦题(本大J共15小I1.每小题2分，共30分)在每小J冽出的四个备选项中只有一个是符合题目聂求的，靖将其代码填写在题后的括号内.错选、多选或未选均无分.1 .在数据的逻辑结构中，树结构和图结构郴是【】A.非战性结构B.成性结构C.动态结构D.峥态结构2 .在一个长度为n的顺序表中插入一个元素的算法的时间更杂度为【】A.0(1)B.O(I0En)C.0(n)D.0(02)3 .指针P1.和P2分别指向两个无头站点的非交单循环链表中的尾站点，要将两个链表链接成一个新的的循环链表，应执行的操作为【】A. p

2、111ext=p2-next：p2-next-PInext;B. p2-next-=p1-next；p1.-next-=p2-next;C. =p2-next;P1.-next-=p;p2-next=p1.-next;D. p=1.-nextsp1.-next=p2-nextsp2-next-=ps4 .设栈的初始状态为空.入栈序列为1.2.3,4,5,6,若出栈序列为2.4.3.6.5.1,则操作过程中栈中元素个数最多时为【】R.2个B.3个C.4个D.6个5,队列的特点是【】.允许在表的任何位比进行插入和删除B.只允许在表的一崩进行插入和删除C,允许在表的两端进行插入和删除D.只允许在表的

3、一端进行插入，在另一端进行删除6.一个展串的结点类型定义为【】SdefineNodeSize6typedefstructnode(chardataNx1.cSizcsstructnode*next:I1.inkStrNode:如果好个字符占1个字节，指针占2个字节，该链申的存储密度为【】A.1/3B,1/2C,2/3D,3/47 .广义式A=如.B.(a,B.(a.B.)的长度为【】.1H.2C.3D.无限(ft8 .己知10x12的：维数祖A,按“行优先顺序“存储，每个元素占1个存箍单元，己知A1.I的行储地址为420,则R55的存偌地址为【】A.470B.471C.472D.4739 .在

4、一棵二叉树中，度为2的结点数为15,度为1的结点数为3,则叶子结点数为【】A.12B.16C.18D.2010 .在带权图的最短路径问题中，路径长度是指).路径上的原点数B,路径上的边数C.路径上的顶点数与边数之和I).路径上各边的权位之和11 .具有n个顶点，e条边的无向图的邻接矩阵中，等元素的个数为【】A.cB.2eC.n,-2eD.n1.-1.12 .要以0(n1.ogn)时间复杂度进行枪定的排序,可用的排序方法是【】A.归并排序B快速排序C.堆排序D,日泡持序13 .若希望在1000个无序元素中展快求得前10个最大元素应借用【】.堆排序B.快速排序C.目泡排序D.归并排序14 .对有序

5、表逆行二分查找成功时，元点比较的次数【】A.仅与表中元素的(ft有关B.仅与我的长慢和被查元素的位置有关C.仅与被杏元素的值有关I).仅与表中元素按升序或降序排列有关15 .敌列文件是一种【】A.顺序存取的文件B.随机存取的文件C.索引存取的文件D.索引以序存取的文件二、填空体大J共10小,每小M2分，共20分)请在每小题的空格中填上正确答案.借填、不填均无分.16 .若一个算法中的语句频度之和为T(n)f00gi0.G,则该算法的渐近时间11杂度为17 .在单铢表中，除了第1个元素结点外,任一结点的存储位置均由指示，18 .栈的修改是按的原则进行。19 .字符串中任意个连续的字符组成的子序列

6、称为该率的.20 .假设一个10阶的上三角矩阵A按z顺I序乐设存储在一维数组B中,若矩阵中的第一个元素a1.,1在B中的存储位置k=0,则元索a5,5在B中的存储位置k=21 .在一棵具有n个结点的严格二叉树中，鹿为1的结点个数为,22 .对于稀疏图，来用表示法较为节省存储空间.23 .在排序过程中.如果.则林真为外部排序.24 .设有一组记录的关连字为(19,14,23,1,68,12,10,78,25),用/地址法构造敞列表，故列函数为h(key)=key%1.1.,散列地址为1的链中有个记录。25 .多关键字文件的特点是除主文件和主索引外,还建有0三、解答题(*大愚共4小题，每小JB6分

7、，共20分)26 .对于下列稀优矩阵(注：矩阵元素的行列下标均从I开始)0000O1.07-100-8050000000.006-29(D画出三元组表:(2)画出三元组表的行表.27 .已知一个森林的前序遍历序列为CBA1.)HECF,后序遍历序列为ABCI)EFGH.(D画出该森林：(2)i出该森林所对应的二叉树28 .对关用字序列(429,653,275.897.170.908.473.256.726)进行基数排序.写出每一趟的排序结果.29 .对下列关键字序列(87.25.310.08.27.132.68.96,187,133.70.63.47,135)构造散列表,假设散列函数为h(ke

8、y)-key%13,用拉徒法解决冲突.(D画出该散列表：(2)求等概率情况下也找成功的平均宜找长度AS1.；(3)写出捌除值为70的关键字时所需进行的关键字比较次数。四、算法阅读题(*大共4小JB,每小届6分，共20分)30 .阅读下列如法,并问答问题：(D假设d(3,7,7,I1.20,20,20,51.51),写出执行函数=f3Q(&D后的1.(2)简述f30的功能.voidf30(Seq1.ist*1.)(/I.为非空的有序表inti=1.,k=0；uhi1.c(ith)(if(1.-datai!=1.-datak)1.-data+kJ=1.-datai；i+：11.-1.ength=k

9、+1.:(1)(2)31.阅读下列W法,并S答问遨：(D假设栈5=(3,8,6,2,5),其中5为校顶元素，写出执行函数f31(&S)后的S：(2)简述函数31的功能.voidf31(Stack*S)(QueueQ：InitQUeUe&Q)：whiIe(!StackEinpty(三)EnQucue(&Q.Pop(SS)；whi1.e(!QueueEmpty(Q)Push(ftS.DeQueue(AiQ):(1)(2)32 .假设具有n个结点的完全二叉树顺序存储在向肽BT1.n中，阅读下列算法,并回答问即：(D若向用BT为：IA1.B1.CIDIEiFiG1.1234567画出执行函数f32(B

10、T,7,D的返回结果:(2)简述函数F32的功能BinTreei*32(DataTypeBTintninti)(BinTrcep：if(in)returnNU1.1.：p=(BinTNode*)ma11oc(siZeof(BinTCode)：-data=BTi:p-1.chi1.d=f32(B1.n,i2);p-rchi1.d三f32(BKn.i*2*1.):returnp：)(1)(2)33 .已知有向图的物接表和第接矩阵定义如下：力defineHaxNum50图的城大顶点数tyedefstructnode(intadjvex；邻接点城structno(k半next：处指针域)EdgeNod

11、e:边表结点结构typedefstruct!charvertex：顶点域EdgeNodefrrstedge：边表头指针VertexNode;顶点表结点结构IypederStruct1.VertexNodeadj1.istMaxNum：邻接表i11tn,e：图中当前丁兔点数和边数A1.Graph;邻接表描述的图Iypedcfstruct(charvertexMaxNumJ：顶点表intadjmatrixMaxumMaxNu三：部接矩阵intn,e；图中当前顶点数和边数IAMGraph;邻接矩阵描述的图下列算法是相邻接表描述的图G1.改为邻接矩阵描述的图G2趁.在空白处填上适当内容使算法完整：vo

12、idf33(A1.GraphG1.AMGraphG2)inti,j：EdgeNodetp:G2-n=G1.n：G2-e=0)；for(i=0:ivertexi三：P=G1.adj1.istij.firstedge：for(j=0;Jadjnatrixij=0:uhi1.e(P)(G2-adjaatrixipadjvex-1.:：)(1)(2)(3)五、算法设计题(*10分)34 .设顺序发I.是一个递增有序表.编写算法，要求利用二分查找法确定插入位置.将元素N插入到1.中，使1.保持有序。编号：219绝密启用前2011年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码

13、02331）、单项选择Ii（本大题共15小题，每小题2分，共30分）I. A2.C3.D4.B5.D6. D7.C8.C9.B10.DII. C12.A13.A14.B15.B二、填空题（本大JS共10小建16.O（n,）18.后进先出20.3422.邻接表24.4每小JK2分，共20分）17.前驱结点的链指针19.子串21.023.需要在内、外存之间交换数据25.次关健字索引22723-131-833553654-2559三、解答无（本大题共4小题，锤小超5分，共20分）26. 1）三元组表如下：0|227123-1231-83 335（3分）4 5365 54-26559（2）行表如下：（

14、2分）|。|。|2口|4|27.(1)森林:（2）对应二叉树:（2分）（3分）（说明：如果森林Bi错，但森林与二叉树之间的对应关系正确仍得2分）28.第一趟:170,653,473,275,256,726,897,908.429第二的170,473,275,897第三趟：170,256,275,429,473.653,726.897,90829.(1)（2分）（2分）（1分）（3分）（表中桂结点铅画错一个扣1分，扣完3分为止）（2）AS1.-（81.+42+1.3+1.4）/14-23/14（或1.64）（I分）（1分）(3)3（说明：如果每次新插入的结点都是在链表头部，则站点越接顺序应该与上图所示恰好相反，散列表也为正确.此时（3）的答案为2）四、算法阅读即（本大IS共4小胶，每小JS5分，共20分）30.（1）（3,7