《02331数据结构201410真题及答案.docx》由会员分享，可在线阅读，更多相关《02331数据结构201410真题及答案.docx（13页珍藏版）》请在第壹文秘上搜索。
1、2014年10月高等教育自学考试全国统一命题考试数据结构试卷（课程代码02331）本试卷共8页，清分100分.考试时间150分立,考生答题注意事项I1 .本卷所有试必须在答题卡上作答.等在试卷上无效，试卷空白处和Ir面均可作Uk2 .第一部分为选界A1.必对应试卷上的f1.!号使用2B砒曲“答JK卡”的相应代码京事3 .第二部分为非选界JB.必须注明大、小题号.使用0.6亳米I1.色字迹签字塔作答.4 .合理安樗答题空间，超出答题区域无效.第一部分选择题一、学项选算（本大J共16小,每小2分.共30分）在每小I1列出的四个备选项中只有一个是符合J1目要求的，请将其选出并将“答题卡的相应代码涂.
2、未涂、幡浊或多流均无分.1 .下列选项中，属于逻辑结构的是A,线性表B.锌表&顺序板D.循环队列2 .下列关于寺法输出的叙述中，正确的是A.算法一定没有输出B.算法可以没有输出C.算法至少有一个输出D.算法必须有多个谕出3 .针对线性在逻辑上相邻的两个元素,下列叙述中，正确的是,采用顺序存储时一定相邻，采用链式存储时也一定相邻B.采用顺序存储时一定相邻,采用链式存谛时不一定相邻C.采用眼序存储时不一定相邻，采用链式存储时一定相邻D,米用帧序存储时不一定相邻，采用链式存储时也不一定相邻4队列和栈的特征分别是A.先进先出，先进后出B.先进先出，先进先出C.先进后出，先进先出D.先进后出，先进后出5
3、 .在二维数ff1.a81.中,每个数组元素aij）占用3个存储空间,所育数组元素存放在-个连续的存储空间中,则该数组需要的存储空间个数是.80B.100C.240D.2706 .广义表A=(a,(b,e,(e,f.g,h)的表长是A.27 .谀深度为k(k31)的二叉树中只有度为0和度为2的结点,则该二叉树中所包含的结点数至少是A.kUB. 2k+1.C. 2k-1.D. 2k8 .下列选项中,可以唯确定一棵二叉树的两种遍历序列毡A.前序测历序列和中序遍历序列B,前序遍历序列和后序诩历序列C.前序遍历序列和层次遍历序列D.后序通加序列和层次遍历序列9 .下列关于无向连通图特性的奴述中，正确的
4、是A.边数大于顶点个数减1B,所有顶点的度之和为我数U度为1的丁兔点个数一定为佃数D.度为1的点个数一定为奇数10.下列关于无向图广度优先搜索序列的叙述中，正确的是A.广度优先搜索序列只有一种B.广度优先搜索序列可能不存在C.广僮优先搜索序列可能力.多种D.广健优先搜索序列一定有多种11.设帝权连通图G中含有n(n1.)个顶点e条边,卜列关于G的最小生成树的叙述中.正确的是A.生成树中一定含有权值以小的e条边B.生成树中可能含有权值数小的n+1.条边C.生成例中一定含有权值最小的n条边D.生成树中可能含有权值最小的n-1条边12.下列排序方法中.时间发杂度与数据初始状态相关的是A.直接选择排序
5、B.怏速排序C.基数排序D.箱排序13.卜列排序方法中,效率较高且检定的方法是.直接插入排序B.日泡排序C.快速排序D.归并排序11.下列叙述中，不符合m阶B树定义的是A.根结点最多有m探子树B,所有叶结点都在同一层上C.各结点内关世字均升序或降序排列D.叶结点之间通过指针链接15 .假设做列衣长m=U,微列函数H(key)=key%1.1.表中已有4个表点：H(39)=6.11(41)-8.11(53)-9.11(76)-10,占了,1个位置.其氽位更为空“现采用线性探查法处理冲突,存储关键字85时需要探查的次数是第二部分非选择题二、填空M(本大共10小,每小2分，共20分).请在答Ii卡上
6、作答16 .著名计算机科学家沃思普指出:算法+=程序。17 .描述算法占用内存空间效率的术语是.18 .设履序我第1个元素的存佬地址是2000,每个数据元素占4个字节，则第41个元素的存储地址是O19,校和队列是操作受限的线性表,其中只能在赛的一端进行插入或加除操作的是o20 .广义装A=(a,b,c,(e,f,g,h),Si1.（八）=。21 .一株左子树为空的二又树在中序线索化后,其空指针域的个数为o22 .除郃接表外,图的另一种链式存储方式是。23 .含n个Iftae条边的带权连通图G,果用迪杰斯特拉算法得到的某个给定顶点到其余各顶点最短路椅的条数是O24 .DFS算法的中文名掰是。25
7、 .若构造一棵具有11个结点的二又排序树,在最坏情况下,其深度为。三、简答题(本大J共4小j1.,每小Ji5分.共20分).请在密卡上作答.26 .设Q是有N个存储空间的循环队列，初始状志front=rear=0,约定指针rear指向的单元始终为空,回答下列同时.(D写出数据元素X人队的喷句序列：(2)写出队苜元崇出队并保存到变量Y的语句序列:(3)给出计算队列长度1.的表达式.27 .已知稀疏矩阵M如下，采用三元组表存偌.00=203000000000-20000000080000000007请回答下列问题.(1)给出三元组表的类型定义。(2)画出矩阵M按行优先的三元加表.28 .将百分制成
8、绩分成五个等级,已知成绩的对应关系及分布情况如下表所示:百分制成绩S059606970-79808990100等级grade不及格及格中等良好优秀百分比515452510请根据最优二义树的基本原理,采用类C谱言,描述你所设计的成绩判定过程.29 .给定有向无环图G如Sfi29图所示,写出G的5种不同的拓扑排序序列，四、算法阅读题(*大共4小题，每小题6分.共20分)请在答题卡上作答.30 .请写出卜列程序段的输出结果。SeqStackS;/初始化栈Scharx,y;x三*1.,;y=,0,;Push(S,x);Push(S,x);Push(S,y);x=Pop(三);Push(SJE)PUSh
9、(S,x)；x-Pop(三);Push(SJH)WhiIe(!StackEmpty(三)y三Pop(三);putchar(y);PUtChar(x)；输出结果：31 .带头结点的单链表定义如卜，其中Cy域记录本结点被访问的次数,初值为0,单链我始终以freq值从大到小有序,函数f31完成的功能是：查找给定关键字所在结点，若查找成功，则该结点的freq域加1,并按freq值调整站r旨位P1.请将空白处(D(3)补充完整.在答他卡上作答.typedefintKeyTypc;typedefstructnodeKeyiypekey;intfreq;structnodenext;RecType,1.in
10、k1.ist;1.ink1.istD1.(1.ink1.istH,KeyiyPeK)1.ink1.istp三H,q;whi1.e(p-next&p-next-key!=K)p=p-next;if(p-ncxt=NU1.1.)returnNU1.1.;/查找不成功：if(p-freqnext-freq)调整结点位置q=p-next;/取下该结点p-ncxt三q-next;pH;U找到合适位置并插入whi1.e(p-next-freqq-freq)：q-nextp-next;3):returnq;32 .阅读程序，回答下列问题。typedefintKey1.ype;typedefstructKey
11、IyPekey;InfbTYpeOtherinfo;Reciype;typedefRecTypeSeq1.istMAXSIZE+1;void2(Seq1.istR,intn)inti,1.ow=1,high=n;whi1.e(1.owhigh)(fbr(i=1.ow;iRi+1.key)R0=Ri;Ri=Ri+1;R(i+1=RO;)high-;fbr(i=high;i1.ow;i-)if(Ri.keyR(i-1.key)R0=Ri;Ri=R(i-1.;Rp-I=R(O);)1.ow+;for(i=1.;i1.chi1.d);：p=Bt-Ichiid;BtAkhiId三(3);Bt-rchi1
12、.d-(4);五、算法收计（本大JB共1小,共TO分）请在答题卡上作答.34 .已知带头结点的单蟋表类型定义如下:typcdefstructnodeintdata;structnodenext;J1.istNodc;typedef1.istNodc1.istjtr;请箱写函数Invert1.ist实现总链表的原地逆转要求在原链表上进行逆转，不允许申请新的表结点空间函数原型如下，1.istjJtrInvenUst(1.ist-ptrhead);/原地逆转单链表head绝密启用前2014年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考一、单项选择题（本大题共15小题,1. A6.A11. D(课程代码02331)IJJ17.空间复杂度19.枝21.2夕2分，共30分)4.A9.B14.D二、填空Jg（本大题箕10小题，每小默2分，共20分）16. 数据结构18. 216020.z(b,c,(e,Cg,h)22,逆邻接表24.深度优先搜索三,解答题(本大题共4小膝，每小J5分，共20分)26. (D数据元素X入队：ScOif(rcar1.)%N-fton1.)printf(1.4Queucoverf1.ow)dseQrear1三X;rear=(rear1)%N;2）队甘元素出队并保存到变量Yif（rcar-front）printf（
