2016年10月自考2331数据结构真题和答案

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

2、应代码涂黑。错涂、多涂或未涂均无分。1 .下列选项中，不属于线性结构特征的是A.数据元素之间存在线性关系B.结构中只有一个开始结点C.结构中只有一个终端结点D.每个结点都仅有一个直接前趋2 .设17个元素的顺序表中，若将第1(个元素e移动到第/(旧与,即个位置,不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是A.C*D*3,若用一个大小为7的数组作为循环队列的存储结构，且当前rew和盘0nt的值分别为2和4,在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3个操作之前rear和矗0nt的值分别是A.0和lB.0和3C.3和6D.4和54.已知广义表LS=(a),(b,(

3、c),(d,(e,f),0),LS的长度是A.2B.3C.4D.55.一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。于中包含的结点数是A.kB.2k-1C.k2D.2k-16 .如果某二叉树的前序遍历序列为abced,中序遍历序列为cebda,则该二叉树的后序遍历序列是A.cedbaB.decbaC.ecdbaD.ecbad7 .一个森林有m棵树，顶点总数为n,则森林中含有的总边数是A.mB.n-lC.n-mD.n+m8 .设图的邻接矩阵A如下所示。各顶点的度依次是01010011A=01001000A.1,2,1,2B.2,2,1,lC.3,4,2,3D.4,4

4、,2,29.若对下厦无向图进行深度优先遍历，得到的正确遍历序列是A.h,C,a,b,d,e,g,fC.d,b,c,a,h,e,f,ge,a,f,g,b,h,c,da,b,C,d,h,e,f,gG的拓扑序列是10.己知有向图G如下所示,A.a,b,e,c,d,f,gC.a,C,d,e,b,f,gBD.aa,c,b,f,d,e,g，c,d,f,b,e,g11 .下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是A.插入排序B.希尔排序C.归并排序D.直接选择排序12 .对一组数据(2,12,16,88,5,10)进行排序，若前3趟排序结果如下:第一趟：2,12,l6,5,10,88第二趟

5、：2,12,5,l0,16,88第三趟：2,5,10,l2,l6,88则采用的排序方法是A.冒泡排序B.希尔排序C.归并排序D.基数排序13 .设有序表为9,l2,21,32,41,45,52,当二分查找值为A.1B.2C.3D52的结点时，元素之间的比较次数是.414 .下列选项中，既熊捌回事存储结构也能在链式存储结构上进行查找的方法是A.散列查找B.顺序查找C.二分查找D.以上选项均不能15 .在一棵5阶B树中，每个非根结点中所含关键字的个数最少是A.1B.2C.3D.4第二部分非选择题(共70分)二、填空题(本大题共l0小题，每小题2分，共20分)16 .两个栈Si和Q共用含100个元素

6、的数组S099,为充分利用存储空间，若险的栈底元素保存在S99中，则Si的栈底元素保存在中。17 .在一个单链表中，已知指针变量q所指结点不是表尾结点，若在q所指结点之后插入指针变量S所指结点，则正确的执行语句是。18 .设顺序表第1个元素的存储地址是1000,每个数据元素占6个地址单元，则第11个元素的存储地址是。19 .二叉树采用顺序存储方式保存，结点Z保存在数组A7中，若X有右孩子结点L则Y保存在中。20 .一棵二叉树中，度数为l的结点个数为m,度数为2的结点个数为n2,则叶结点的个数为。21 .已知广义表LS=(=b),c,d),head(LS)是。22 .在无向图G的邻接矩阵A中，若

7、AUJ尸L处|A0,q=。23 .已知大根堆中的所有关键字均不相同，最大元素在难项，第2大元素可能存在的位置有2个，第3大元素可能存在的位置有个。24 .在有n个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等，则查找成功时平均查找长度是甘肃自考网www.gsks.cc。25 .线性探查法和拉链法解决的是散列存储中的问题。三、解答题(本大题共4小题，每小题5分，共20分)26 .对题26图中所给的二叉排序树T回答下列问题。(1)给出能生成r的2种关键字插入序列；(2)给出r的前序遍历序列。出26圈27 .对题27图所示的无向带权图G,回答下列问题。(1)给出图G的邻接矩阵；(2)给出图

8、G的一棵最小生成树。胆27图28 .现有5个权值分别是20、31、16、7和l5的叶结点，用它们构造一棵哈夫曼树，画出该树。29 .对于给定的一组关键字序列26,l8,60,65,45,13,32,写出使用直接选择排序方法将其排成升序序列的过程。四、算法阅读题(本大题共4小题，每小题5分，共20分)30 .设非空双向循环链表L的头指针为head,表结点类型为DLNode定义如下。typedefintDataType;typedefstructdInodeDataTypedata;/data是数据域structdEnode*prior,*next;"prior指向的趋结点，next指向

9、后继结点DLNode;TypedefDLNode*DLinkList;初始时，L中所有结点的prior域均为空(NULL),next域和data域中已经正确赋值。如题30图a所示。bead夫j-力，.*y|豆30图ab所示。函数f30完成的功能是：将L中各结点的prior域正确赋值，使L成为双向循环链表。如题30H300Gb将空白处应填写的内容答在答题卡上。voidGO(DLinkLisibH)(DLNodep;p.head;while(p->nexi!.)(-p;p*p->nexx;)(3)"p;31.已知二叉树的二叉链表类型定义如下，阅读程序，并回答问题。typedc

10、fcharDaiaType;typedefstructtio<k(DauTypedata：structnode,(child,*rchild;JBinTNode;typedefBinTNodc*BinTrw;voidDl(BinTreebt)(if(btl-NULL)(printf(bu>data);Hl(bt->Ichild);printf(bt>data);“dm是数据域"分别指向左、右孩子结点若二叉树如下所示，写出调用f31(T)的输出结果。32.阅读下列程序，写出f32的输出结果。void02()(SeqSucktS;char%y;lnitStack(

11、SXx-Ti*;y-t；Push(S,x);Push($tV);X=POf>(S)；Push(StxXPush(S.y);Push(SOPu$h(Stx);wh>ie(JStackEmptj(S)1yPop(S);prints",yXprintf(T>33.阅读程序，回答下列问题。intB3(Nodeiyp«RQXeyType£irrt口)(inti=Ti-1,count=1jR0.key=k;while(Ri,kcyUk)(IcountH;if(1=0)returnl；elsereturncount;)(1)变量count的含义是什么？(2)6

12、3的功能是什么？五、算法设计题(本题10分)34.已知单链表类型定义如下：typedefstructnodeintdata;structnode*next;ListNode;tjpedefListNode*List_ptr;单链表L中结点数不少于2。设计算法判断L中存储的全部n个数据是否是斐波那契序列的前n项。如果是，则intlsF(List_ptrbead)："判定是否是斐波那契序列函数返回1,否则返回0。函数原型如下：注：斐波那契序列的定义为：圻吟，fa&i+fE5e2)2016年it）月高等教育自学考试全国统-金题考试数据结构试题答案及评分参考（曝程代码02331）-柴

13、同芒择君（江大夏总不小.苞手小班？分,式，分.LD2.C工BB5.B.07.C生C9.DIC，DH.D12.A13.F1>B15.B-.以空题（本大题共而小麦T每小慧2分I共20分）if.SOJ7-qncxr;IS,106019.A；1620,口寸1211a,bj2312j.f：24,MT犯25.#矣三、樨答题（本文兖共小昱,恁小整5分,拄物分）2团11agerbdc蹲仃1）门”（二分二遨明：本信卷赛季唯一，远直另外育肿罐入序弗悔有公茎，：igebdfc2?-,:仃的情接矩库.河二七;X5XSx5jc7x3x:317：462：geg45cc3CJ6工H?rs237金J酉圈若案琵骨生善考第

14、：一5K（3分、及31gcbdo却只签膛正确给曲旦量2种郎可埼令,工-戴浮遍即手如agcbdefa）屋g的tm小生明家下；说朝工本题答案不睢一.转中任一分支结点的左右分支耐以互换只要正确,局择培分.二工五接建专推审过名：钉埼大艮手£M像造65，况0乳一携梵声会0比觉.小,变二工支/宁二越措浮言；。J群由,65,=，26*汽力二电善产后：I三出工以后Y5一亩L”口分；党国排序*:6，！氏;£3±=±66&5U分）三逵持序运：三笫，7注阅,白，门分）六越排序彘士口.捕我3工一,&&®西，算茨觉读整i本大就共4小悲，毫小题5分

15、，共加分：,三口.3d口令）.2：pA=:二->gw】三处；0）headprior：二分！3:输出号果：AI3门0RA仆分）32茹生结果；旃（5分）靠第结扣试蹙瞽案至:一参有篇口页（共3蜀：3孔门：加记施的电状«m百汗如闷黄廉序及我时.找董修m/窿沟比较次谿.禽&的0的功能是主教组中从启河辅送行巅查找一逅同吃裳示爱找不卷乱.返回正整数表刘t找成交,且这下灰霾示赛那比挑次费*:一计；,五.算法设才度：本艇R分）风酢/答案:E;；-.isi.pirrListNorfe*prelhesd->TMxLY冏三he«d->nexE->nexi,*eiirreni=pra3>nea；1-Jif|prM*>.tain.一5：prs-二二：13r?L'jm0:C