《自考数据结构真题和答案》由会员分享，可在线阅读，更多相关《自考数据结构真题和答案（20页珍藏版）》请在金锄头文库上搜索。
1、2016年10月高等教育自学考试全国统一命题考试数据结构试卷（课程代码02331）本试卷共7页，满分100分，考试时间150分钟。考生答题注意事项：1 本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸2. 第一部分为选择题。必须对应试卷上的题号使用 2B铅笔将“答题卡”的相应代码涂黑3. 第二部分为非选择题。毖须注明大、小题号，使用0. 5毫米黑色字迹签字笔作答。4 合理安排答题空间，超出答题区域无效。第一部分 选择题（共30分）一、单项选择题（本大题共15小题，每小题2分，共30分在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 卡”的相应
2、代码涂黑。错涂、多涂或未涂均无分。1. 下列选项中，不属于线性结构特征的是A.数据元素之间存在线性关系B.结构中只有一个幵始结点C.结构中只有一个终端结点D.每个结点都仅有一个直接前趋2. 设17个元素的顺序表中，若将第个元素e移动到第个位置,不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是A. AMB, i-iC.上汁】D讨3 .若用一个大小为7的数组作为循环队列的存储结构，且当前 rew和盘Ont的值分别为2和4,在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3个操作之前rear和矗Ont的值分别是A. 0 和 I B. 0 和 3 C . 3 和 6D . 4
3、和 54 .已知广义表 LS=(a) , (b , (c) , (d , (e , f) , 0) , LS 的长度是A. 2B. 3C. 4D. 55.棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点于中包含的结点数是A. kB. 2k-1 Ck2D.2k-16.如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序遍历序列是A. cedba Bdecba Cecdba D . ecbad7.个森林有m棵树，顶点总数为n,则森林中含有的总边数是A. mB. n-l Cn-mn+m8.设图的邻接矩阵 A如下所示。各顶点的度依次是0 10 10
4、 0 11A. 1, 2, 1, 2 B . 2, 2, 1,1 C . 3, 4, 2, 3 D . 4, 4, 2, 29.若对下厦无向图进行深度优先遍历，得到的正确遍历序列是A.h, C, a, b, d, e, g, f.e, a, f, g, b, h, c, dC. d , b, c, a, h, e, f , g.a, b,C,d, h, e, f, g10 .己知有向图G如下所示G的拓扑序列是A . a, b, e, c, d, f,gB.a, c, b, f, d, e, g,c, d, f, b, e, gC. a , C, d, e, b, f, gD. a11.下列排序
5、算法中，在每一趟都能选出一个元素放到其最终位置上的是A .插入排序.希尔排序.归并排序 D .直接选择排序12对一组数据 （2，l2 ， 16， 88， 5， 10）进行排序，若前 3趟排序结果如下：第一趟：2， 12， l6 ， 5， 10， 88第二趟：2， 12， 5， l0 ， 16， 88第三趟：2， 5， 10， l2 ， l6 ， 88则采用的排序方法是A.冒泡排序B.希尔排序C.归并排序D.基数排序13设有序表为 9 ， l2 ， 21， 32， 41， 45， 52 ，当二分查找值为 52 的结点时，元素之间的比较次数是A. 1B.2. 3D. 414.下列选项中，既熊捌回事
6、存储结构也能在链式存储结构上进行查找的方法是A.散列查找B.顺序查找C.二分查找D.以上选项均不能15.在一棵5阶B树中，每个非根结点中所含关键字的个数最少是A. 1B. 2C. 3D . 4第二部分 非选择题 （共 70分）二、填空题 （本大题共 l0 小题，每小题 2 分，共 20分）16 .两个栈S和S2共用含100个元素的数组S0 一 99，为充分利用存储空间，若S2的栈底兀素保存在 S99中，则Si的栈底兀素保存在 中。17在一个单链表中，已知指针变量q所指结点不是表尾结点，若在 q所指结点之后插入指针变量S所指结点，则正确的执行语句是 。18 .设顺序表第1个元素的存储地址是100
7、0,每个数据元素占6个地址单元，则第11个元素的存储地址是o19 二叉树采用顺序存储方式保存，结点Z保存在数组A7中，若X有右孩子结点L则Y保存在中。20.一棵二叉树中，度数为I的结点个数为n1，度数为2的结点个数为n2，则叶结点的 个数为o21 .已知广义表 LS=（b），c，d），head（LS）是。22 .在无向图G的邻接矩阵A中，左则A仏门=o23. 已知大根堆中的所有关键字均不相同，最大元素在难项，第2大元素可能存在的位置有2个，第3大元素可能存在的位置有 个。24. 在有n个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等，则查找成功时平均查找长度是 甘肃自考网。25 .线
8、性探查法和拉链法解决的是散列存储中的 问题。三、解答题（本大题共4小题，每小题5分，共20分）26 .对题26图中所给的二叉排序树 T回答下列问题。(1)给出能生成r的2种关键字插入序列;(2)给出r的前序遍历序列27 .对题27图所示的无向带权图G,回答下列问题。(1) 给出图G的邻接矩阵；(2) 给出图G的一棵最小生成树。瓏27图28 .现有5个权值分别是20、31、16、7和15的叶结点，用它们构造一棵哈夫曼树，画出该树。29.对于给定的一组关键字序列26 , 18 , 60, 65, 45, 13, 32，写出使用直接选择排序方法将其排成升序序列的过程。四、算法阅读题(本大题共4小题，
9、每小题5分，共20分)30 .设非空双向循环链表 L的头指针为head,表结点类型为DLNode定义如下。type血f ini DaiaType;typedcf struct d Inode DataType data; data 足敌据域rtrtKi dlrt&depngUM; prints向前着结点nexl擔向右堆结点 DLNode;typedef DLNode * DLinkList;初始时，L中所有结点的prior域均为空(NULL)，next域和data域中已经正确赋 值。如题30图a所示函数f30完成的功能是：将L中各结点的prior域正确赋值，使L成为双向循环链表。如 题30图b
10、所示。将空白处应填写的内容答在答题卡上。void 00 (DLinkLisi head)DI Node p;p = head;while ( p-neKl !=(】illp；p - p-nejci;P；31.已知二叉树的二叉链表类型定义如下，阅读程序，并回答问题。lypetkf struct nodedata魁数据tS分别8向左.右按子AMIDataType data:sttuct node khild, rchiidtJBinTNode;typedef EinTN网帯 BinTrigid Q ( BinTree M )(iff Vt!-NULL(printf( %cH. btdma); i
11、(bt* Ichild);若二叉树如下所示，写出调用f31(T)的输出结果DB32 .阅读下列程序，写出f32的输出结果voia B2()SeqSUck *S;char 治 y; lnitSiack S k x-Ti*;yE*ush(S,x);Fush(S,V)；x - Pop ( S ); Pu曲(S. x); Push ( St y X PushtS.aK PuslX Stx);while !SUtEmpty (S) (y Pop( S ); prints y Xpdntf( %W,曾)；33 .阅读程序，回答下列问题。int f33 G3的功能是件么？五、算法设计题（本题10分）34 .
12、已知单链表类型定义如下:tj-pedef stnict node ini data;smici node * next ListNode;tpedcf LiNode * Listjnr;单链表L中结点数不少于2。设计算法判断L中存储的全部n个数据是否是斐波那契序列的 前n项。如果是，则函数返回1否则返回0。函数原型如下：int 15F(Listjmt head);判定是否是斐波那契序列注：斐波那契序列的罡义为：Wh f严1*卢(円322016年10片高等教育自学考弑全统-命题考试数据结构试题答案及评分参考C课程代匹02331J一学顶选择題丈翌关小査，爭J亜2分.艾纟:1. D二 C丄B4. 3
13、66. C7- C9 C9- DLC. Dil. D!2. A15. C14. B15. B二 填空融本大題共11）小1L毎小题2分，共20分）16. S!7 s-nctq-ncxt; qGgrf=s:181则拭16】2G.顷“21. O22123. 624. (nriyz25.三解答题为K共4小賦毎小题S分.夷20知26. Cl） ag e f b dc agcb fd c翊:本色答褰不唯一，込丽外砖:却及agcbdcf,只茨沱辻視洽lb兰慙2科壽可给兮，C3处令)2）蔚祕历字列：agcbdcf27. Cl G的蜀廉C巨为为：5x462 - -一 、(s)辭g T?;眇空(Svaaaav，淤轩*第if(gjoydvpssq f0(4K)Jouc -二gc V .; :(召i)严（佻氏详弟彗斗立：送虽区壬吏 53S9如衣啦*81 H -抽練w u妙的0应兀$1粤湘班($1)S9*099 tEX81 *U :理姗鮒d賈如中労X9P :当吨爭程二（&【）弐宪0厂刃彷 預1乍帶鶯矗二d抚玄井誉9
