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

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

1、2017年4月高等教育自学考试全国统一命题考试数据结构试卷（课程代码02331）本试卷共7页.满分100分，考试时间150分钟.考生答题注意事项：1 .本卷所有试题必须在答题卡上作答.答在试卷上无效，试卷空白处和背面均可作草稿纸。2 .第一部分为选择题.必须对应试卷上的题号使用2B船篦将“答题卡”的相应代码涂黑。3 .第二部6为非遗异题.必须注明大、小题号.使用0.5充米I1.色字迹筌字笔作答.4 .合理安排答题空间，超出答Jn区域无效.第一部分选择题（共30分）一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”

2、的相应代码涂黑.错涂、多涂或未涂均无分.1.下列叙述中，不正确的是A.算法解决的只能是数值计续向即B.问一问题可以有多种不同算法C.舞法的每一步操作都必须明确无歧义D.算法必须在执行有限步后结束2.下列关于栈中逻森上相邻的两个数据元素的叙述中，正确的是A.顺序存储时不一定相邻，链式存储时一定相邻B.喉序存储时不一定相邻，族式存储时也不一定相邻C.顺序存储时一定相邻.链式存储时也一定相邻D.顺序存储时一定相邻,一式存储时不一定相邻3.对带头结点的单循环链表从头结点开始遍历（head为头指针,p-hcad-next）.若指针P指向当前被遍历结点，则判定遍历过程结束的条件是A.P=NU1.1.B.h

3、ci-d=NU1.1.C.p=headD.hcad!*=p4.设栈的入栈序列为1.2,3,4,5,经过入、出栈操作后，可能得到的出栈序列是A.2,3.5,1,4B.4,2,1,3,5C.3.4,1,2,5D.3,4,2.1,55.数组A2(3J按行优先顺序存放，A的首地址为10.若A中每个元素占用一个存储单元，则元素A1.2的存储地址是A.10B.12C.14D.156 .广义表(a,b),(c,d)的表尾是A.bB.dC.(c,d)D.(c,d)7 .若完全二叉树7包含20个终端结点，则T的结点数最多是A.38B.39C.40D.418 .对下面的二叉树进行中序战索化后，结点f的右指针指向的

4、结点是A-1B.n10.若从顶点a开始对下图进行广度优先遍历碌&(A.a.b,c,e,f,dC.a,c,e,b,d,f11.下列排序算法中，程定的是C. n(n+iy2D.n(n+1.),则不可能祖到的遍历序列是图B.a,c,b,e,f,dD. a,c1.bfctCd9.若图G是一个含有个顶点的强连通有向图，则G的边数至少是A.堆排序C.目泡排序B.直接选择排序D.希尔揖序12 .下列排序算法中，比较操作的次数与待排序序列初始排列状态无关的是A.快速排序B.直接选择排序C.日泡排序D.直接插入排序13 .若对二叉排序树进行遍历.则下列遍历方式中，其遍历结果为递增有序的是A.前序遍历B.中序遍历

5、C.后序遍历D.按层遍历14 .设一组记录的关键字为12,22,10,20,88,27,54,11),散列函数为HRey产key%II,用拉依法解决冲突,则散列地址为0的链中结点数是.A.1B.2C.3D.415 .在下面3阶B树中插入关键字65后，其根结点内的关值字是第二部分非选择题（共70分）二、填空题（本大Ifi共10小题，每小题2分,共20分）16 .散列方法的基本思想是根据元素的关键字直接计算出该元素的17 .一个需要频繁埔删;的线性表宜选择存储结构.18 .若中级表达式为9+（62）*8,则相应的后SR表达式是,19 .对任何一棵二叉树T,若其叶子结点数为为,度敷为2的结点数为小，

6、剜小等于.20 .若某二叉树7的前序遍历序列是A,B,CD,中序遍历序列是B,A,D,C,则T的后序遍历序列是.21 .在给定个叶子结点权值且不含度数为1的结点的所有二叉树中，其最小的二叉树称为哈夫曼树.22 .用邻接表存储含个顶点e条边的有向无环图G,对G进行拓扑排序，算法的时间复杂度为23 .连通图G的一个子图如果是一棵包含G的所有JS点的树，则该子图称为G的W.24 .二分查找的速度快效率高，但是它要求表按关健字有序并且25 .除了问想的规模和分量个数之外，还有是影响基数排序时间复杂度的主要因素.三、解答藤（本大题共4小题，每小题5分，共20分）26 .对题26图所示的带权无向图G,试回

7、答以下问题.26R（1）西出G的最小生成树;(2)若用克务斯卡尔(KnISkaI)算法求最小生成树，请按被选中的次序写出最小生成树上各条边的顶点和权值27 .已知散列表的长度为11,散列函数为H(key)ukcy%1.1.,散列表的当解状态如下：下标.0.23456789IO关键字1.nI60I17129II-现要插入关快字38,回答下列问题(I)若用线性探查法解决冲突，则38所在位置的下标是什么？(2)若用二次探查法解决冲突，则38所在位置的下标电什么？(3)以上两种方法中，各需要多少次探查次数？28 .试回答下列关于拓扑排序算法的问题。(D算法中利用一个栈保存入度为。的顶点，其目的是什么？

8、(2)若在算法中将队列改为栈，相应地将入、出枝及判栈空操作改为入、出队列和判队列空操作，其他部分不变，是否依然能够得到拓扑排序的正确结果？29 .考虑用快速排序、堆排序和归并排序3种捧序方法对数据序列进行推序，针对下列不同情况，宜分别选择先种排序方法？(1)使用尽量少的存储空间；(2)要求排序结果是稳定的：(3)快速找出数据序列中关健字值较大的若干项四、算法阅读题(本大题共4小题,每小践5分,共20分)30 .设铳表中结点类型定义如下，阅读程序，回答下列问题.typedcfintDataiypc;typedcfstructnodeDataiypcdata;structnodenext;RecT

9、ypc,1.ink1.ist;intDO(1.ink1.isthead)if(head=NU1.1.)return0;e1.sereturnmax(headdata,(30(hcad-ncxt);/max(atb)返回Qb中的较大者(1)若链表1.2.12.16,88,5.10,写出调用CJo(1.)的摘出结果:(2)函数130的功能是什么？31 .函数B1.的功能是逆序输出链表中所有结点的数据域值.请在空白处填充适当的内容,使其完成指定功能.VoidD1.(1.ink1.isthead)(if(head=NU1.1.)：e1.seO1.(head-next);printf(%d,(2);.)

10、32 .函数f32的功能是统计N个顶点的有向图中边的数量，有向图用邻接矩阵A赛示.阅读程序，并在空白处填入适当内容，使其完成指定功能.intD2(intAN)(inti,j;intsum三0;for(t-0;iN;M)for(；jctnode!chi1.d,rchiM;BiTNode;typedefBiTNodcBiTree;以下程序为求二叉树深度的递归算法，请填空完善之.intdepth(BiTree*bt)bt为指向根结点的指+/inth1.=Othr-O;if(1)retum(0);h1.=depth(btIchiId);hr=depth(btrchi1.d);if()return(h1

11、.1.);e1.se(3)；五、算法设计题(本题10分)34 .已知二叉树的结点类型定义如下：typedefstructnodeintdata;structnode!chi1.d.rchi1.d;BinTNodc;typedefBinTNodcBinTree;请编写函数SearchXNum.计算任意二叉树7中其数据域的值大于或等于X的结点的个数井返回该值.函数原型如下：intSearchXNum(BinTreeT.intx);/返回二叉树T中数据域的值大于或等于X的结点的个数绝密启用前2017年4月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码02331）一、单项选择频（

12、本大SS共15小题，诲小题2分，共3。分）I.2.D3.C4.DS.D6.U7.C8.D9.B10.CH.C12.D13.B14.C15.D二、情空题（本大超共W小渔，每小题2分，共20分）16存储地址17.钻式18.962-8+19.n-I20.BD.C,A21.带权路泾长度（或WP1.）22.0(n+c)23.24.灿序存楮25.越散大小三话答逆（本大88共4小园，每小联5分，共2。分）26（D最小生成例G分）（2）,OI,2,3,4,5（2分）27.1）插入位置的下标是8（2分）（2）插入位Ja的下标是4.（2分）（3）探杳次数分别是4和3Q分）28（I）减少找入度为。的顶点的时何.提高

13、效率，3分）（2）用以.（2分）.致据蛀构法题等案&评分畲考第I页（共2页）29 .(1)难排序(1分)C2)归并排序(2分(3)维持序(2分)四、算法阅读题(本大IS共，小风，每小期5分，共20分)30 .输出结果：88(3分)(2)返回俅表各结点中的最大值2分)31 .dta.(3分)32 .(1i+1分)(2) j-02分)(3) AijJM)2分33.Dbt=NU1.1.1.r(1分)(3) return(hrH)(2分(4) 算法设计JS(木8IO分)M.参考答案：int1.TXNum(BKTreCtT,ini)(it11;If(T-NU1.1.)rttumO;2分)if(T-)n-1.;2分)e1.sen=0;(I分)returnn+1.TXNum(T-k)ikJ,x)+I.TXNun(T-rchiW,x);(5分)数据结构试想答案及讨分静考第2页（共2观）