02142数据结构导论201604

《02142数据结构导论201604》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。1.一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是A.线性表B.队列C.树D.图2.计算n!(整数nNO)的递归算法是:intFactorial(intn){if(n==o)return1；elsereturnn*Factorial(n--1)；}其时闯复杂度为A.0(n)B.O(log.n)C.0(n°)D.0(n2)3.将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是A.p二q；B.p—:>next=q

3、；C.q—>next二p--:>next；p-->next二q；D.p一>next一q；q-->next一p一-:>next；4.设初始栈为空，s表示人栈操作，x表示出栈操作，则合法的操作序列是A.sxxssxxsB.ssxsxxxsC.ssxxxssxD.sssxxxsx5.将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是A.顺序表B.单链表C.栈D.队列6.设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素)，若只设头指针，则入队操作、出队操作的吋I'可复杂度分别为A.0(n)、0(1)B.0(1)、0(1)C.

4、0(1)、0(n)D.0(n)、0(n)7.若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树，根结点1的下标为1,剥结点4的下标为A.4B.50.6D.78.按层序(自顶向下、从左到右)遍历二叉树吋需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，队列中所出现的元素个数最多是A.1氏2C.3D.41.一个数组的第一个元素的存储地址是iOO,每个元素占2个存储单元，则第5个元素的存储地址是A.120B.110C.1080.1002.己知含6个顶点(畑V.,V2,vs,v4,3的无向图的邻接矩阵如题10图所示，则从顶点V。出发进行深度优先搜索可能得到

5、的顶点访问序列为01000101100110001010000000001001L—0彳0012345题10图A.{v0»V1,V2,V5,v.1,v3}C・{vo,V1,Vs,V2,V3,V.J11.“在旅游吋从某地出发要去某个目的地,用角度.最合理的解决方案是A.深度优先搜索C.拓扑排序12.二分查找算法的时间复杂度是A.0(n2)B.0(nlog^n)B.(Vo»Vi,V2,V3,v4>v5}D.{vo,V1,V1,V5,V2,V3}如何选择线路才能使得路程最短”，从图的应B.最小生成树D.最短路径C.0(n)D.0(log2n)13.已知一个散列表如题13

6、图所示，其散列函数为II(key)二keymodi1,采用线性探测法处理冲突，则下一个进入散列表的关键字49的地址为厂1538I61i84:i!i012345678910题13图A.2B.3C.8D.914.用冒泡排序方法对n个待排序的键值进行排序，则整个排序过程所历经的趟数是A.1B.n—1C.rlD.至少为1、至多为n—115.现对关键字序列{6,1,4,3,7,2,8,5)进行快速排序，那么以第1个元素6为工作基准的第一趟快速排序结束的结果序列为A.{5,1,4,3,2,6,8,7)B.{5,1,4,3,2,6,7,8)C.{5,1,4,3,6,2,8,7)

7、D.{8,7,6,5,4,3,2,1)第二部分非选择题(共70分)二、填空题(本大题共13小题，每小题2分，共26分)16•计算机图灵奖获得者N.Wirth曾提出一个著名公式：算法+_数据结构「二程序。17.“即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。”这种评价算法好坏的因素称为—健壮性—017.设某非空双向链表，其结点结构为止也邑空J,若要删除指针q所指向的结点,则需执行如下两条关键语句：q—>priort>next=q-->next；q->next->prior=q->prior;□18.大小为MaxSize的循环队列中，

8、若fron