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

2018年K)月高等数目自学考试全国统一命题考试数据结构试卷(课程代码02331)本试卷共7页.清分100分.考试时间150分钟.考生答遨注意事项：1 .本卷所有试题必须在答题上上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸，2 .第一部分为选择题,必须对应试凳上的题号使用2B铅簿将“存JSK”的相应代码涂黑。3 .第二部分为非选择应必须注明大、小题号,使用0.5氢米黑色字迹签字能作答.-1.合理安排答四空间，起出答庖区域无效.第一部分选择题一、和田班，本大共16小,每小2分.共30分.在小不出的冬选事中只有一特f1.1.目要求的.请将其选出.1 .下列数据结构中，逻辑结构不同的是A.雄性表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-j>next->next=NU1.1.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中，M中0；1的个数差是A.n(n+1.)/2-eB.n(n+1.)/2-2eC.n×n-eD.n×n-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(n×c)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.17.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)=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.中的两个相邻结点,即q>next=p.若要在q所指结点后插入指针r所指结点，则执行的语句是r->ne处=p：.18 .递归算法设计中的最小子问题称为递归的<.19 .广义表(a,b),(c,d),c,(f(),h)的表尾是20 .已知二叉树的前序遍加序列和后序遍历序列,则对应的二叉树确定.21 .如果有向无环图G中仅有一个皿点的入度为0,若要求G的拓扑序列不唯一,MG中必须存在一个出度至少为的顶点。22 .将森林T转换为一棵二叉树T1.在T中结点A是结点B的右邻的兄弟(下一个兄弟),则在T1.中,A是B的结点.23 .对含灯个元素的数刖序列采用快速排序算法进行排序，平均时间复杂度是.24 .汝列存储中,常用的解决冲突的方法有开放地址法和两大类.25 .效设顺序存储的有序表R含有8个关搂字,进行二分查找时,平均查找长度为.三、善本大共4小,小5分，共20分.26 .设电文字符集是他1,e2.c3,ei,c5),各字符出现的次数分别为(36,13,26,18,23.现要为该字符集设计哈夫蛀第眄.请回答下列问遨.(D给出构造的哈夫姑树.(2)给出各字符的哈夫姓编码.(3计算电文编码总长。27 .已知图G采用匏接矩阵存谛.邻接矩阵如题27图所示“GO-题27图O)根据铭接矩阵画出图c.(2)根据图G写出从顶点A开始图G的1个深度优先搜索地历序列。(3)根据图G写出从原点A开始图G的1个广度优先搜索涧历序列.28 .有数据序列(12,17,05,10,20.24.45.11.10.，使用希尔排序方法将其排成升序序列.请W1.等下列何时.(D分别写出增量为3和1的希尔排序结果。(2)计算第一趟希尔排序中数据元素之间的总交换次数(两个（八）元素之间的交换记1次).29 .谀有二叉排序树T如阳29图所示.现嵇在T中捌除结点。，请回答下列问SS,(D画出删除后的二叉排序树(仅需画出一棵)。(2)在你实现的删除过程中,指针域更新的次数是多少？题29图四、算法朗读，本大共4小,每小6分共20分.30 .顺序表类型定义如下：#define1.is1.Size100typcdcfstructintdata1.istSizc);i11t1.ength;Scq1.tsr;阅读下列程序，并回答问题，intPartmin(Seq1.ES1.I,Scq1.istS1.2)intEgth,minva1.uc,k0;min1.ength=S1.2>1.ength;minva1.uc三S1.2->data0;whi1.e(k<min1.ength)if(S1.1.->data(k<S1.2->datak&&S1.1.->datek<minva1.uc)minva1.uc.S1.I->datak;e1.sei&S1.2->data(k)<minva1.uc)ninvaiue-S1.2->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.;i<»(1)；i+)temp-R(i;j-whi1.e(j>0&&temp.key<R(j1.key)(RW三R(i1.;2：)(3):33.二叉树的存储结构类型定义如下：typedefintData1.ypc;IypedefstructnodeDataiypekey;Udata是数据域structnodeIchi1.d.rchi1.d;H分别指向左右孩子JBinTNode;t>pedefBinTNodeBinTree;阅读下列程序,并回答阿明.void03(BinTYeeroot,in(1.eft,intright)if(rooc=NU1.1.)return;03(root->1.chi1.d.Ieft1right);if(ro<X->kcy>1.eft&&ro<X->kcy<right)Prin1.H*%d*»roo<->key);D3(roo<->rchi1.d,1.eftright);<1)设二叉树T如题33图所示b<是指向根结点的指针给出执行f33(g14,30)的输出结果(2)给出该函数的功能五、Jt法设计题：本题10分34.已知个单链表的表头指针保存在数组A中.做链表中的结点类型及数姐类型定义如下，存储形式如题34图所示妆fineMAXSIZE100typcdcfbitDataiype;typed”structnodeDatoiypedau；/data是数据域stnctnodenext;/指向下一结点的指针N<xJe;CypedefNodeScq1.istMAXSIZE;73A(JA(T二_1.W：T1.-÷I-H1.i-"HIWII->41，-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.C11.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分）<2）各字符的哈夫曼修现为，字符CiG6UI1.100O1.IOI00（3）电文修码总长-362*I33>262÷I83÷232=263.（1分）【评分说明】本H（I）和（2）的答案不曜一.若考生给出的答案正确,网祥给分.部分正确的情给分.（I分）27. (I)【评分说明】本18答案不唯.其他答案包括：ABDGEFC.ACDEFGB.AC