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

2013年1月高等教育自学考试全国统一命题考试数据结构试题课程代码：02331考生答翌注意事场：1 .本卷所有试卷必须在答艘卡上作答.答在试卷和草隔纸上的无效.2 .第一部分为送挣!£.必须对应试卷上的题号使用2B铅宅将“答题卡”的相应代码涂黑.3 .第二部分为非选建题,必须注明大、小题号，使用05充米黑色字迹笃作答.4 合理安撑答超空间，超出答题区域无效。选择题部分一、单项选择题(本大题共15小题，每小逊2分，共30分)在每小迎列出的四个备选项中只有一个是符合Sfi目要求的，话将其选出并将“答题纸的相应代码涂黑"错涂,多券或未涂均无分.1 .数据的逻辑结构可以分为A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.简单结构和构造结构2 .践性表是一个彳i网序列，组成线性去的阳本单位是A.数据项B.数据元素C.数据域D.字符3 .栈中有a、b和C：.个元素，a是校底元素，C是栈顶元素，元素d等待进栈，则不可便的出栈序列是A.dcbaBxbduC.CadbD.cdba4 .稀疏矩阵的三元组我是A.顺序存储结构B.链式存储结构C.索引存储结构D.Jft列表存储结构5 .己知广义表G,Mad(G)与IaiI(G)的深度均为6.则G的深度是A.5B.6C.7D.86 .下列编码集合中，M于前蝴编码的一封1是D.O.IO.110,1011)题7图A.(II,IO.(X)I,1OI.(W()IC.1.1.,O1.,(X)1.,OIOI,()G()1.I7 .如即7图所示二叉树的中序序列为A. ACDBB. DCBAC. CDBAD. ABCD8.仃向图巾所仃乐点入度之和与所有顶点出位之和的比於A.1/2R.IC.2D.49,含有n个顶点和e条边的有向图的邻接矩阵中，零元索的个数是A.cB.2eC.n2-2cD.n2-e0.n个顶点的无向连通图.其生成树的边数为B.nA.n-IC.n+ID.nk>gn11.用自底向上的日泡排序方法时序列(8.13.2655.29.44)从大到小排序,第一趟排序需进行交换的次数为A.2B.312 .对序列(8,1326,55,29,44)从小到大进行基数排序,第一端排序的结果是B.(!3.26.55.44.8.29)D.(29.26,8,44,55,I3)B,分块有序D.每块中数据个数必须相同A.(13.44.55.26.8.29)C.(8,13.26,29.44,55)13 .采用分块查找时,要求数据A.块内有序C.分块无序14 .下列关于故列函数的说法正确的是A.散列函数越复杂越好B.汝列函数越简单越好C,用除余法构造的放列闲数是最好的D.在冲突尽可能少的情况下，放列函数越渝单越好!5.卜列关于m阶B树的叙述中，我退的足A.每个结点至多有m棵子树B.f个结点至多行m1个关键字C.所有的叶结点均在同一层上1）报结点至少有棵子树非选择题部分注意事项:用思色字迹的签字笔或制笔将答案写在答题纸上,不能答在试跑卷上.二、填空题（本大题共IO小题，每小密2分，共20分）16 .算法的时间双杂度与实现时枭用的程序设计语言。17 .在长度为n的顺序去的第i（1.wisn）个元素之后插入个元素时，衙向后移动个元素。18 .设循环队列存放在向I1.tdata0.m中，在出队操作后,队头指针front变化为.1%树的前序遍历序列等同于该树对应二叉树的一遍历序列.20 .一个K）OX90的整型稀疏矩阵有10个非零元索，设每个整型数占2个字节则用三元组表存储该矩阵时，所需的字节数是。21 .当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是一。22 .采用邻接表去示n个顶点的有向图时，若表结点的个数为m,则该干j向图的边数为.23 .对同一个基本有序的待排序列分别进行堆排序、快速排序和目泡排序，最省时间的霓法是.24 .在16个记录的有序顺序表中迸行二分查找，最大比较次数是。25 .在排序算法中，若排序附后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是的。三'解答迎（本大题共4小题，每小题5分，共20分）26 .在定义顺序表时，存放在结点的向麻空间不宜过大也不宜过小，为什么？SS27图27 .而出超27图所示树的孩子链表.28 .己知一个无向图G如题28图所示，以顶点为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树.题28图29 .判别以下序列是否为堆,若不是，将其调整为大根堆,并画出大板堆.©(1.5.7.20.18.8.10.40)(18958417.21.6)四、算法阅读题(本大题共4小题，每小题5分，共20分)30 .单就表类型定义如下：typcdcfS1.rUbnode(DataTypcdata:structnode*ncxt:)1.istNodc;IyPedef1.istNodefr1.ink1.ist:阅读下列算法，并回答问SS：voidOOdJnkI1.isthead,DataTypcx)bead是带头结点的非空单链友的头指针1.istNodc4q:p=head;whi1.e(p->nex(->next)p=p->ncxt;q=(1.is(Nodc*)ma1.1.oc(sizcof(1.isNodc);q->dxta-:q->nex1.=p>nex(:p->ncxt=q:I(1)该算法的功能是什么？(2)若单链衣的长度为n.算法的时间”杂度是多少？该时间复杂度和链衣的初始状态有美吗？31 .阅读下列算法假设栈的操作函数都已定义),并回答何起：voidO1.()(SeqStackS：charx，y：x=zc,：Push(&S.x)sPush(&S.,a,)：Push(&S.y)sx=Pop(S):PUSh(&S,'1.')：PUSh(&S,x)：X=POP(&S);PUSh(&S,'s,)：whi1.e(!S(ackEmp(y(S)(y=Pop(&S)：>ichar(y)：)putchar(x)：)(1)自底向上写出执行whi1.e语句之前栈S中的元泰序列。(2)写出该函数的最后输出结果。32 .下列算法的功能是在中序线索树中查找结点，P的前趋,填上适当内容使办法完整.typcdcfenum(1.inkJIhrcadPointerTag;枚举Gi1.ink和Thrgd分别为O和1Iypedefstructnode(DmaTyPedata;PoinierTagItag,nag;Structnode“chi1.d、rchi1.d;JBinThrNOde:BinThrNOdc，f32(BinThrNode*p)/在中序线索树中找结点*p的中序前趋.设P非空BinThrNode*q：if(p>1.iag=Thread)：e1.seq=->1.chiki:whi1.e(q->rtag=1.ink)(2)：returnq；J33 .分析下列持序算法中语句1.和谱句2的短度以及此算法的时间复杂度,并指出该尊法是属于喙一种排序方法.void(33(in(a).in(n)i11(i»j.k,(；for(i=0：i<n：i+)语句I(j=i：for(k=j+1：k<=n：k+)if(a(k<a(j)j=k：语句2t=ai1.:ai1.=ajhaj)=t:II五,籁法设计题(本题IO分)W.二叉排序蚓的类型定义如下：【ypedefSirucinode(intdata;structnode叫ChikIJrChi1.d;)tBSTrec:编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据.函数原型为、oid114<BSTrecT.intm.intn)数据结构试题答案及评分参考（课程代码02331）绝密启用前2013年1月高等教育自学考试全国统一命题考试7单项选律题（本大即共15小题,每小JS2分，共30分）I. C2.B3.C4.A5.C6.B7.A8.B9.D10.AII. C12.A13.B14.D15.D二、填空题（本大题共10小髓，每小Si2分,共20分）17.n-i19.前序（或先序）21.n+123.冒泡排序25.稳定三、解答题（本大题共4小B.每小题5分，共20分）2Q扇饱过小，产生滋出.岸空间过大，浪费.c<27.【评分参考】头结点和链式结构正确3分:孩子链正碑2分.以1DFS生成树BFS生成树【评分参考】深度（DFS）生成树3分；广度（BFS）生成树2分29.是堆，不是堆调成大根雄为：（21,9,18,8,4,17,5,6）续评分分考】画出堆图或方给出堆序列均算作正确四*法阅读题（本大题共4小题，每小题5分，共20分）.30（D在单陡表的最后一个结点之前插入数据城值为,<2）0（n）,无关31. <1）枚中存有，c'a','t',四个元素（2）suck32. （1）returnp->1.chi1（2）q=q->rchi1.d;33.语句1的频度为：n+1语句2的频度为：M1.y2时间复杂度0（明。直接选择排序P（2分）（3分）Se，的结点.（3分）（2分）（3分）（2分）（2分）（3分）（1分）（1分）（2分）（1分）（出口条件，2分）（递归右子树,（递归左子树，2分）（符合输出条件,（输出数据，2分）五、算法设计题(本题10分)34.void04(BSTrccTiintm»intn)G4(>1.chi1.d,m,n);if(T->data>m&&T->data<n)printf(%d-,T->data);(34(T->chi1.d,m,n);【评分参考】若采用前序遍历或者后序遍历后再揖序的方法，的情给分.