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

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

1、2018年K)月高等数目自学考试全国统一命题考试数据结构试卷(课程代码02331)本试卷共7页.清分100分.考试时间150分钟.考生答遨注意事项：1 .本卷所有试题必须在答题上上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸，2 .第一部分为选择题,必须对应试凳上的题号使用2B铅簿将“存JSK”的相应代码涂黑。3 .第二部分为非选择应必须注明大、小题号,使用0.5氢米黑色字迹签字能作答.-1.合理安排答四空间，起出答庖区域无效.第一部分选择题一、和田班，本大共16小,每小2分.共30分.在小不出的冬选事中只有一特f1.1.目要求的.请将其选出.1 .下列数据结构中，逻辑结构不同的是A.雄

2、性表B.栈C.队列D.二叉树2,将16个数据元泰的找性衣按场序存储方式存储在数批中，若第一个元点的存储地址是1000.第6个元素的存储地址是1310.则最后一个元素的存储地址是A.1112B.1120C.1124D.11283 .设栈的初始状态为空，元索I,2.3,1.5依次入栈，不能得到的出栈序列是A.1.2.3.4.5B.4.5.3.2,1C,1.2.5.4.3D.1.2.5.3.44 .设指针变量P指向非空单琏表中的结点,next是结点的指针域,则判断P所指结点为尾结点前一个结点的逻辑友达式中，正确的是A. p-next!=NU1.1.AAp-next-jnext-next=NU1.1.

3、B. p-ncxt=NU1.1.48p-next-nextNU1.1.C. p-next-next=NU1.1.O.p-nextNUU.5 .已知广义表1.S=(a,b.c),d),(e,(fg.(hi),1.S的深度是A.2B.3C,4D.56 .已知一探完全二叉树T的第5层上共有5个叶结点.则T中叶结点个数最少是.58.8C.101).277 .已知二叉树T的前序通历序列为a,b,c,e,d,中序遍历序列为。，e,b,d,a,则T的后序诩历序列为A.c,e.d,b.aB.d.e.c.b.aC.e.c.d.b.aD.e.c,b.a.d8 .有向图C有JT个顶点和。条边，G保存在邻接矩阵N中，

4、M中0；1的个数差是A.n(n+1.)/2-eB.n(n+1.)/2-2eC.nn-eD.nn-2e9 .有向图G中所有顶点的度数之和是24,则G中孤的数量是.10B.12C.14D.1610 .i殳有向图G含有n个顶点、e条边，使用邻接衣存储.对GjS行浮僮优先搜索遍历算法的时间复杂度是A.0(n)B,0(11)C.O(n+e)D.O(nc)11 .对数据序列(26.14.17.12.7,4.3)采用二路归并排序进行升序排序,两越排序后.得到的排序结果为A.1-1.26,17,12,1.1,3B.12.14,17,26,3.I,7C.14.26.12.17,3.4,7D.14.26.12.1

5、7.3.7,412 .下列选项中,不稳定的排序方法是.希尔排序B.一并排序C.直接插入排仔I.排仔12.1 俎记录的关键字为字5,48,47,23,44,88),利用堆排序算法进行降序排序，建立的初始堆为.23.35.48.47.44.8SB.23,35,47.48.44.88C.35,23,47,48,44,88I).35,23,47.44,48,8814. 一棵：叉排序树中，关键字n所在结点是为谯字In所在结点的孩子，则A.n一定大于mB.n一定小于C.n一定等于mD.n与m的大小关系不确定15 .设数列入长=16.故列函数H(key)=key%15.表中已保存4个关键字:addr(1.8

6、)=3.addr(35)=5.addr(51=6,addr(22)=3其余地址均为开放地址“存储关键字36时存在冲突，采用雄性探测法来处理。则查找关键字36时的探花次数是A.1B.2C.3D.4第二部分非选择题二、坡空本大共10小，小2分，共20分.16 .数据项是具有独立含义的标识单位.17 .指针P和q分别指向单性表1.中的两个相邻结点,即qnext=p.若要在q所指结点后插入指针r所指结点，则执行的语句是r-ne处=p：.18 .递归算法设计中的最小子问题称为递归的1.ength;minva1.uc三S1.2-data0;whi1.e(kdata(kdatak&S1.1.-datekda

7、tak;e1.sei&S1.2-data(k)da1.ak;k+;returnminva1.ue;)intf30(Seq1.ist*S1.1,Seq1.ist*S1.2)32.待排序记录的数据类型定义如下：牧fineMAXSIZE100typedefintKeyType;typedefSmIctKeyiypekey;Reciype;IypedefRecTypeScq1.istMAXSIZE;下列函数实现顺序表的直接播入推序，清在空白处境上适当内容使算法完整.void02(SeqUstR,i11tn)(HiJ;RccTypctemp;fbr(i三1.;i0&temp.keypedefBinTNo

8、deBinTree;阅读下列程序,并回答阿明.void03(BinTYeeroot,in(1.eft,intright)if(rooc=NU1.1.)return;03(root-1.chi1.d.Ieft1right);if(rokcy1.eft&rokcyright)Prin1.H*%d*rookey);D3(roorchi1.d,1.eftright);1)设二叉树T如题33图所示b是指向根结点的指针给出执行f33(g14,30)的输出结果(2)给出该函数的功能五、Jt法设计题：本题10分34.已知个单链表的表头指针保存在数组A中.做链表中的结点类型及数姐类型定义如下，存储形式如题34图

9、所示妆fineMAXSIZE100typcdcfbitDataiype;typed”structnodeDatoiypedau；/data是数据域stnctnodenext;/指向下一结点的指针N41，-N闪题34图试设计算法，在多个链表中或找值为key的数据元素，IS找成功返回1.壹找失Ift返回0的数原型为intB4(SCq1.is1.A,intn,intkey)绝序启用前2018年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码02331）一、单项选择Ji1.本大JK共IS小H,每小题2分.共30分I.D2.B3.D4.B5.B6.C7.C8.D9.B10.C1

10、1.B12.A13.B14.D15.C二、馍空题：本大18共IO小题，每小H2分,共20分.16.最小18.终止条件（或递日出口）20.不唯一（或不能）22.右核子24.拉能法（或倭地址法）17.q-next-119.(c,d)Xf(gJ)21.223. (XnIogn)25. 2I/S(或2.625)（2分）三,解答题：本大题共4小I1.每小题5分,共20分.26. （I）哈夫曼村为t（2分）262I83232=263.（1分）【评分说明】本H（I）和（2）的答案不曜一.若考生给出的答案正确,网祥给分.部分正确的情给分.（I分）27. (I)【评分说明】本18答案不唯.其他答案包括：ABDGEFC.ACDEFGB.AC