2017年04月自学考试02331《数据结构》试题.docx

《2017年04月自学考试02331《数据结构》试题.docx》由会员分享，可在线阅读，更多相关《2017年04月自学考试02331《数据结构》试题.docx（5页珍藏版）》请在第一文库网上搜索。

1、2017年4月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共5d、题,每小题2分，共30分)1 .下列叙述中，不正确的是A.算法解决的只能是数值计算问题B.同一问题可以有多种不同算法C.算法的每一步操作都必须明确无歧义D.算法必须在执行有限步后结束2 .下列关于栈中逻辑上相邻的两个数据元素的叙述中，正确的是A.顺序存储时不一定相邻，链式存储时一定相邻B.顺序存储时不一定相邻，链式存储时也不一定相邻C.顺序存储时定相邻，链式存储时也一定相邻D.顺序存储时一定相邻，链式存储时不一定相邻3.对带头结点的单循环链表从头结点开始遍历(head为头指针，p=head-next)o

2、若指针P指向当前被遍历结点，则判定遍历过程结束的条件是A.P=NU11B.head=NU11C.p=headD.head!=p4.设栈的入栈序列为12345,经过入、出栈操作后，可能得到的出栈序列是A.235,14B.4,2,135C.341,2,5D.3,421,55 .数组A23按行优先顺序存放，A的首地址为10。若A中每个元素占用一个存储单元，则元素A12的存储地址是A.10B.12C.14D.156 .广义表(a,b),(c,d)的表尾是A.bB.dC.(c,d)D.(c,d)7 .若完全二叉树T包含20个终端结点，则T的结点数最多是A.38B.39C.40D.418 .对下面的二叉树

3、进行中序线索化后，结点f的右指针指向的结点是A.aD.e9 .若图G是个含有n个顶点的强连通有向图，则G的边数至少是A.n-1B.nC.n*(n+1)/2D.n*(n+1)10 .若从顶点a开始对卜.图进行广度优先遍历，则不可能得到的遍历序列是aA. a,b,c,e,f,dB. a,c,b,efdC.a.c,eb,d,fD.a,eb,c,f,d11 .下列排序算法中，稳定的是A.堆排序B.直接选择排序C.冒泡排序D.希尔排序12 .下列排序算法中，比较操作的次数与待排序序列初始排列状态无关的是A.快速排序B.直接选择排序C.冒泡排序D.直接插入排序13 .若对二叉排序树进行遍历，则下列遍历方式

4、中，其遍历结果为递增有序的是A.前序遍历B.中序遍历C.后序遍历D.按层遍历14 .设一组记录的关键字为12,22,10,20,88,27,54,11),散列函数为H(key)=key%11,用拉链法解决冲突，则散列地址为0的链中结点数是A.1B.2C.3D.415.在下面3阶B树中插入关键字65后，其根结点内的关键字是二、填空题(本大题共10小题，每小题2分，共K)分)16 .散列方法的基本思想是根据元素的关键字直接计算出该元素的。17 .一个需要频繁增删的线性表宜选择存储结构。18 .若中缀表达式为9+(6-2)*8,则相应的后缀表达式是O19 .对任何一棵二叉树T,若其叶子结点数为,度数

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

6、图所示的带权无向图G,试回答以下问题。题26图(1)画出G的最小生成树；(2)若用克鲁斯卡尔(KnISka1)算法求最小生成树，请按被选中的次序写出最小生成树上各条边的顶点和权值。27 .己知散列表的长度为I1散列函数为H(key)=key%11,散列表的当前状态如下：现要插入关键字38,回答下列问题。下标.0.2345678g0关键字IIIIII60I17I29II-1Z(D若用线性探查法解决冲突，则38所在位置的卜.标是什么？(2)若用二次探查法解决冲突，则38所在位置的下标是什么？(3)以上两种方法中，各需要多少次探查次数？28 .试回答下列关于拓扑排序算法的问题。(1)算法中利用一个栈

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

8、ructnOde*next;RecType,1ink1iSt;int!30(1ink1is(*head)if(head=NU11)retumO:e1Seretummax(head-daia,BO(head-next);/max(a,b)返回a,b中的较大者)(1)若链表1：2,12,16,88,5,10,写出调用f30(1)的输出结果：(2)函数f30的功能是什么？31.函数131的功能是逆序输出链表中所有结点的数据域值。请在空白处填充适当的内容，使其完成指定功能。voidf31(1ink1ist*head)(if(head二二NU11)；e1sef31(head-next):printfC%

9、d,，(2)；)32 .函数f32的功能是统计N个顶点的有向图中边的数量，有向图用邻接矩阵A表示。阅读程序，并在空白处填入适当内容，使其完成指定功能。inif32(intAN)(inti,j；intsum=O;for(i=0;iN：)fbr(：jN：j+)if()sum11+;retumsum；)33 .已知二叉树的二叉链表类型定义如下：typedefstructnodechardata：structnode*1chi1d.*rchi1d;BiTNo1chi1d);hr=depth(bt-rchi1d);iff(2)retum(h1+1)；e1se(3):)五、算法设计题(本大题共1小题，每小题10分，共10分)34 .已知二叉树的结点类型定义如下：typedefstructnodeintdata；structnode*1chi1d,*rchi1d;JBinTNode;typedefBinTNodeBinTree；请编写函数SearChXNUm,计算任意二叉树了中其数据域的值大于或等于X的结点的个数并返回该值。函数原型如下：intSearchXNum(BinTree*T,intx)；/返回二叉树T中数据域的值大于或等于X的结点的个数