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

绝密考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答迹纸上，选择题部分注意事项：I.答啊前，考生务必将自己的考试课程名称、姓名、准考证号用怨色字迹的签字室或别电填写在答SS纸规定的位置上.2.每小时选出答案后，用2B铅笔把答飕纸上对应题目的答案标号涂如一如需改动，用襟皮擦干件后，再选涂其他答案标号不能答在试题卷上.一、单项选择题<本大跑共IS小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，清将其选出并将“答题纸”的相应代码涂黑,错涂、多涂或未涂均无分”1 .算法的时间复杂度表征的是A徵法的可读性B.芽法的难易程度C.执行算法所耗费的时间D.执行算法所耗费的存储空间2 .对需要领联插入和删除结点的线性衣，适合的存储方式足A.Iffi序储存B.链式存储C.索引存储D.散列存储3 .在头指竹为head的锵环链农中，判断指针变量P指向尾结点的条件是A.p->ncxt->ncxt=hcadB.p->next=hcadC.p->ncxt->ncxt=NU1.1.D.p->ncxt=NU1.1.4,迪杰斯特揄DijkS1.ra）算法的功能是.求图中某顶点到其他顶点的嫌短路径B.求图中所右.顶点之间的城短路径C.求图的最小生成树D.求图的拓扑排序序列5.若栈的进栈序列为1.2,3,4,5,则经过出入栈操作不可修获得的出栈序列是A.4.5.3.2.1B.4.3.5.1.2C.1.2.3.4.5D.5.4.3.2.16 .A是7x4的二维数组，按行优先方式顺序存储，元素AIo）网的存储地址为100O,若每个元素占2个字节，则元索A3的存储地址为A.1015B.1016C.1028D.10307 .深度为4的完全二叉树的结点故至少为A.4B.8C-13D.158.若采用邻接矩阵A存储有向图G.则结点k的入度等于A中A.结点k对应行元素之和B.结点k对应列元素之和C.结点k对应行和列元索之和D.非零元素之和9.无向图G的邻接地阵一定是A.对称矩阵B.对角矩阵C-三角矩阵D,单位矩阵10.下列关于有向带权图G的叙述中.斛日的是A.图G的任何一棵生成树祐不含有网路8 .图G生成树所含的边数等于顶点数戚1C.图G含有回路时无法得到拓扑序列D图G的最小生成树总是唯一的11 .在下列排序算法中，关键字比较次数与初始排列次序无关的是A.且泡排序B.希尔挣序C,直接痈入排序D,直接选择排序12 .对下图进行拓扑排序,可以得到的拓扑序列是B.bacdeD-abdccB.於式存储(2.12,5.693.89.34.25)D.徒式存储(2.356912.25.34.89).abcdeC-bcadc13 .下列线性表中,能使用二分查找的是A.A序存储(2J2,5,6,9,3,89,34,25)C.顺序存储(235.6.9.12.25.34.89)14 .在下列i找方法中，平均任找长度与结点数僦无直接关系的是A.顺序查找B.分块查找C.被列查找D.基于B树的查找15 .下列排序算法中.时间复杂度为(XnIogzn)的算法是A快速排序B.日泡排序C.直接选择排序D.直接插入排序非选择题部分注拔出项：用黑色字迹的签字笔或钢笔将答案写在答烟纸上，不能答在试超卷上.二'填空版本大题共10小题，每小SS2分，共20分)16 .数据的同一种能彩结构，可以对应多种不同的17 .若在长度为n的顺序表第i个元本之前插入一个元素，期需要向后移动的元索个数是.18 .顺序校存放在Sm1.1.中，酬0为栈底，栈顶指针top初始值为I，则栈满的条件是top=，19 .队列只能在队尾进行插入操作，在队首进行操作.20 .广义表A=(x,(y.Z),a.b),则函数hcad(hcad(tai1.(A力的值是.21 .以权值分别为4.3.2.1的四个叶子结点构成的哈夫蜕树,其带权路径长度WP1.是.22 .图的遍历方法有两种一种是深度优先遍历,另一种是.23 .如果排序算法是稳定的，则关键字相同的两个记录排序前后相对次序.24 .己知散列表表长m=1.1.,散列函数h(key)=key%1.1.,表中存有三个关谈字15,27,39,其余他址为空，若采用战性探杳法处理冲突，则关键字为60的结点保存的地址是025 .己地图G的邻接及如题25图所示.题25图从顶点V1.出发进行深度优先搜索,得到的深度优先搜索序列是.三、解答Sfii本大犍共4小题，每小踵5分，共20分)26 .设QA”是有M个元素存储空间的循环队列，若fem指向队首元素，皿指向队尾元素的下一位置，请分别用C语言描述下列操作：(口将元素X入队；(2)将队苜元素出队.并保存到变俄y中；(3)计算当前队列中元素个数.27 .己知帝权图GWVE).其中V=(AB.C.D,E),邻接矩阵如下171214«'7888OC4=1288491484300co93CC画出对痈的图G(2泗出图G的最小生成树28 .已知一姐恃持记录的关健字序列为(1S,1517,59.14.35.13.17.24,84>,请给出对应的小根堆序列,29 .已知二叉树如超29图，i?画出该二叉树的前序线索。息29图四、算法阅读逊(本大题共4小题，每小逊5分，共20分)30 .阅读下列函数并I可答问即typedcfstructnodc(DataIypcdata：structnode*ncxt:)1.inkNode:1.,e<1.ef1.inkNode1.inkIisi:voidDcIeXd.ink1.istbead.DataTypcK)(1.inkNockp.*q*s：p=head;q=p->nex1.;whi1.c(q!=NU1.1.)if'(q->data=-x)Js=q：q=q->ncxt:frec(三):p->ncxt=q:Ie1.se(p=q；q=q>next:)J(1)执行该函数后.华趾表head中data值为X的结点数是多少?(2)该函数的功能是什么？31 .阅读下列函数并回答问题typcdcfstructn<>dcDaiaTypedata；structnode4IchiId.4Tchi1.d:>BnTNde:IyPedefBinTNode*cBinTree:voidInoiidcrtBinTrccbt)(if(bt!=NU1.1.)1.norder(b1.->1.chi1.d):printf(n%cbi-x1.a1.a)；1.norder(bt*>rchi1.d);(D给出对如的31图所示的：叉树执行函数IiKHdcr后得到的输出序列.(2)该函数的功能是什么？32 .下列函数实现直接插入排序，请填写适当内容,使其功能完整.voidO2(intrntN)Iiniij；for(i=2:(1)；)(ItOwikj=i-1.:Whik:(3)rj+>1.=J三j=j-i+n=rtj:I)33 .函数BinSCarCh实现二分查找，请回答下列问愿.(1)在空白处埴写适当内容，使函数功能完整。(2)查找成功时函数的返回值是什么?(3)交我失败时函数的返回值是什么？i11BinSearch(Seq1.isR,KeyTyPek,inin)Iin1.ow=().mid.high=n-1.：Whi1.a1.oWV=high”mid=(I)：if(Rmid).kcy=k)returnmid：if(Rmid1.kcy>k)high=mid-1.:e1.se1.ow=mid+1.:Ireturn-1：五、算法设计JS(本题IO分)34 .已知:Iypedefstructnodeintdata：Stn1.C1.node*ncx1.;1.inkNode；Iypedef1.inkNode*1.ink1.ist:请阑写原夔为int1.istisequaK1.ink1.istA,1.ink1.iStB)的函数.指针A、B分别指向两个带头结点的刑镂表“函数功能足：若单桂表A.B中全部对应结点的data值相等.则返回1.否则返回0.绝密启用前2013年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考(课程代码02331)-、单项选择题(本大题共15小题，每小题2分，共30分)I.C2.B3.B4.A5.B6.D7.B8.B9.A10.D11.D12.B13.C14.C15.A二、填空题（本大题共10小题，每小期2分，共20分）16.存储结构（或物理结构）17.n-i+118.m-1,19.删除（或出队）20.(y.z)22.广度优先遍历24.721.1923.不变(或保持不变)25.v1.,v4,v3,v5,v2三、解答题(本大题共4小题,每小825分，共20分)26.(1)if(rear+1.)%M!三front)Qrear三x;rea=(rear+1.)%M;(2) if(rear!=front)y=Qfront;front=(front+1.)%M(3) (M+rcar-front)%M;（2分）（2分）（1分）（3分）（2分）28.小根堆序列是(11J4,13,17,15t35,17t59,24,84)(5分)29.每条线索1分四、算法阅读M（本大题共4小题，每小题5分，共20分）30.(1)O(2分)(2)删除单链表data值为X的全部结点（3分）31.(1)CBDAFE（2分）(2)对二叉树进行中序遍历（3分）32.(1)i<N（2分）(2)i+÷（1分）>10<rU（2分）33.(1)(Iow+highy2（2分）(2)查找成功时，返回值是元素的下标（2分）(3)查找失败时，返回值为7（1分）五、算法设计题(本题IO分)34.int1.istisequa1.(1.ink1.istA,1.ink1.istB)1.ink1.istpa,pb;歹(1分)pa=A->next;pb=B->next;(1分,)whi1.e(pa->data="pb->data)(2分)pa三pa->ncxt;:芦(分)pb=pb->next;(1分)if(pa-NU1.1.&&pbNU1.1.)合、(2分)return1;A、B值域相等返回I(1分)e1.sereturn