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

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

1、2015年IO月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)本试卷共8页.清分100分.考试时间150分停.考生答题注意事项，1 .本卷所有试题必须在的!卡上作答.答在就卷上无效，试卷空白处和Ir面均可作草稿纸.2 .第一篇分为选务题,名财应试卷上的号使用2B帕制将“售卡”的相应代码添事.3 .第二部分为非遗舞愚必须注明大、小题号，使用0.5充米黑色字迹签字0作答.4 .合理安挎答题空同.超出答JS区域无效.第一部分选择题一、单项选舞题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合JI目要求的，请将其选出并将“答JI卡”的相应代码涂未涂

2、、储涂或多油均无分.1 .下列选项中，不属于线性结构的是A.网B.栈C.队列D.线性表2 .长度为n的顺序表，删除位置i上的元素(OWiWn-1),需要移动的元素个数为A.niB.ni1C.iD.i*1.3 .栈果用不同的存储方式时，下列关于出栈过程的叙述中,正确的是A.地序栈需要判定栈空，造栈也需要判定B.顺序栈需要判定找空，而链板不需要判定C.顺序栈不需要判定栈空，而锌栈需要判定D.顺序极不需要判定栈空，集校也不需要判定1 .若一个栈以数组V0.n-1.j存储,初始栈顶指针I。P为n,则N入栈的正确操作是A.IoP=IoP+1：Vtop=xB.Vtop=x；Iop=top+1C.top=t

3、op-I：Vmp-xD.Vtop=x:top-top-15 .在二维数组a910中：每个数组元素占用3个存储空间,从首地址SA开始按行优先连续存放，则元素a8j5j的起始地址是A,SA+141B,SA+144C,SA+222D,SA+2556 .广义表A-(X.(y),(（八）.A)的深度是A.2B.3C.4I).87 ,模左子树为空的：叉料在前序践索化后，其空指针域个数为A.0B.1C.2D,不褥定8 .下列关于哈夫亚柯的叙述中,悟误的是A.用n个结点构造的哈夫蚣树是唯一的B.哈夫里树中只有度为。或度为2的结点C.树中两个权俏最小的结点可能是兄弟结点D.同一结点集构造的二叉轲中,哈夫曼树的W

4、P1.最小9. 6个顶点的强连通图中，含布的边数至少是A. B.5C.6D.710.对题K)图进行深度优先搜索遍历,下列选项中，正确的说历序列是IVSV,vsV1v2B. V,V,VjV1V4C. VaV,VjV,v1.DVSv,v4v311.下列选项中，能构成Sfi1.o图中一条路径的是B.V1V2V,VjV4A.V1V,v4V,VjD. v2v1v5t4V,12 .有向图采用邻接矩阵存储，某一行中非零元素的个数等于A,时应顶点V的度B,对应顶点V的出度C.而应顶点V的入度D.依附于对应攻点V的边数13 .F列选项中，符合下定义的中A. (102.24.55.60.89.93)B. (24,

5、89,55.60.93,102)C. 102.93,55,60,89,24ID. (102.60.89.93.55,2414 .已知关健字序列为(66.82.25.51.98.108,利用快速排序方法,以第一个元素为基准得到的一楞排序结果为A. 25,51,66.82.98,108)B. (25,51,66,98,82.108)C. (51.25.66.108.98.82)D. 51,25,66,82,98,108)15 .下列选项中，其平均森找性能与始于二叉排序树的杳扶相当的是A.二分查找B.顺序查找C.分块查找D.索引顺序变找第二部分非选择题二、澳空题(本大J*共10小I1.每小i三2分，

6、共20分)请在答题卡上作答.16 .线性表(a.a”，a,),除外,每个元索都有唯一的直接前趋.17 .指针P指向单链发中某个结点，在P所指结点后插入指针S所指的结点，正确的操作序列是，18 .设PUSh,、Pop分别表示人栈和出栈操作.x=10,y=20,z=30.依次进行卜列操作：PUSh(y)、Push（三）.Push（三）,X=Pop0Y=Pop0,x,y的值分别是一J19 .广义.表1.=(a,(b,efg.h),head(1.)=.2Q.设树T的度为3,其中度为1、2和3的结点个数分别为3、2和1,则T中叶子结点的个数为021 .由一棵二叉树的后序遍历序列和遍历序列可以唯一确定该二

7、义树.22 .在有n个顶点的无向图中，任一顶点的度不大于.23 .借助于一个栈来实现的图的遍历算法是。24 .若在向图中存在拓扑持序序列，则该图一定不存在。25 .已知关圾字序列为66.82.25.51.98,108),一世二路归并排序的结果为三、前答题(本大J共4小题，每小题5分.共20分)请在答题卡上作答.26 .已知n阶对称矩阵A的元素为a,(0Wi.jWn1),采用“按行优先”将下三角部分的元素(含主对角线)保存在一维数组Sa中,且约定元素函”保存在sa0.元素a“(Wi,jWn-D保存在sak中，请给出由下标i,j计算下标k的计算公式.27 .已知二又树T如题27图所示。题27图谙问

8、答下列问题：(1)画出该二叉树对应的森林.(2)写出对森林进行前序遍历的遍历序列i28 .超28图所示为一棵含2个关键字的3阶B树T.现将关谊字序列口0,60.70.20,10)依次插入到T中，画出缶插入一个关键字后得到的树型.3050题28图29 .给定无向天权连通图G如题29图所示,从顶点Vo开始,使用普里姆(PrIm)算法,求G(1)画出最小生成树九(2)计算T中各边权伯之和.四、算法解读题(本大题共4小题，每小题5分，共20分)请在答题卡上作答.30 .请写出下列程序段的输出结果.#define1.istSize100typedefstruct)intdata1._1.istSize；

9、int1.ength；jSeqUst；void(Seq1.ist1.ist)Iinti,j,k;1.br(i=0；i1.ength-2；i+)Ij=i+1；whi1.e(j1.ength-1)(if(1.ist-datai=1.ist-c1.ataj)(fbr(k=j；k1.ength-1；k+)1.ist-datak=1.ist-datak+1；1.ist-1.ength-；Ie1.seJ+；voidmain()ISeq1.istUst=O,3,7,3,3,3,4,0,3,71,10；inti；B0(&1.ist)；printf(,Ien=%dn,*,Bst.1.ength)；fbr(i=0

10、；ina.n；b-n三a.m；b-t.t;if(b-tO)return1；e1.se)q=0；for(co1.三0;co1.a.n；co1.)for(p=O;pdauqi=(3);b-dataq.j(4)；b-data=Bt-data；p1chi1.d=(2)；p-rchi1.d三(3)；returnp；为完成指定功能，请在空白处填写适当内容，使其功旗完整.33 .函数33的参数t指向即33图所示的二叉排印例的根.问读程序，I可答下列问时.typedefintKeyTypc;typcdcfstructnodeKCmrPe3；W%node!chi1.d,rchi1.d；-ZV4IBSTNodc,

11、BSTree；r-.)BSTree03(BSTrcc1.,KeyTypeK)题33图IBSTreep；whi1.c(f=NU1.1.)Iif(t-key=K)IPrintf(查找成功n“)；returnt；Ip=t;if(t-keyK)t=t-!chi1.d；e1.set三t-rchi1.d；IPrintf(我找不成功n)；t=(BSTrcc)ma1.1.oc(sieof(BSTNodc)；1.-keyK；t!chi1.d=NU1.1.;t-rchi1.d=NU1.1.；if(p-keyK)p-!chi1.d三t;chcp-rchi1.dtreturnNU1.1.；I(D若连续3次词用函数f3

12、3参数K的值依次取10、25、10,写出每次谓用后函数的输出结果：(2)说明函数33的功能。五、算法设计题(本大Ji共I小共10分)请在答题卡上作答34 .已知顺序表Seq1.iSt定义如下：typcdefstructKeyTypekey：InfoTypeotherinfO：RecType：typedefRecTypeSeq1.istM)XSIZE1.i:编号函数，用日泡排序法将n个元素的待排序列R按关键字降序持序。函数原型为：intf34(Seq1.istR.intn).绝密启用前2015年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考,（课程代码023尹汐年项逸择同（本大理共IS小,小髭2分.共30分）12B3U.B二、填空H（本大18共IO三、解答题才大图共