02142数据结构导论2016年04月份真题及答案.docx

《02142数据结构导论2016年04月份真题及答案.docx》由会员分享，可在线阅读，更多相关《02142数据结构导论2016年04月份真题及答案.docx（6页珍藏版）》请在三一办公上搜索。

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

2、”的相应代码涂黑。错涂、多 涂或未涂均无分。1. 一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是A.线性表B.队列C.树D.图2. 计算 n!(整数 nN0)的递归算法是：int Factoria1(int n)if(n= =o)return 1； else returnn*Factoria1(n-1) ； 其时闯复杂度为A. 0(n)B. 0(1og2n)C. O(n。)D. O(n2)3. 将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是A. p=q；B. p-: next=q；C. qne

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

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

5、A.v ,v ,V ,V ,V ,vB.v ,V ,V ,V ,V ,v012543012345C.vo,V,V5,V2,V3,v4D.vo,vV4,V5,V2,V311. “在旅游时从某地出发要去某个目的地，如何选择线路才能使得路程最短”，从图的应用角度.最合理的解决 方案是A.深度优先搜索B.最小生成树C.拓扑排序D.最短路径12. 二分查找算法的时间复杂度是A. O(n2)B. O(n log2n)C. O(n)D. O(log2n)13. 已知一个散列表如题13图所示，其散列函数为H(key)=key modll，采用线性探测法处理冲突，则下一个进入 散列表的关键字49的地址为:20H

6、5也0123456739 10A. 2B. 3C. 8D. 914. 用冒泡排序方法对n个待排序的键值进行排序，则整个排序过程所历经的趟数是A. 1B.n 1C. rlD.至少为1、至多为n115. 现对关键字序列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)D.8, 7, 6, 5, 4, 3, 2, 1)第二部分非选择题(共70分)二、填空题(本大题共13小题，每小题2分，共26分)16

7、. 计算机图灵奖获得者N. Wirth曾提出一个著名公式：算法+_数据结构_=程序。17. “即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。”这种评价算法 好坏的因素称为健壮性。18. 设某非空双向链表，其结点结构为匝4丝四竺若要删除指针q所指向的结点，则需执行如下两条关键语句：q一priortnext=qnext； _q-next-priort=q-prior;。19. 大小为MaxSize的循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断该循环队列为 空的条件表达式是_front=rear。20. 对稀疏矩阵进行压缩存储的一种方法

8、是_三元组表。21. 若一棵二又树中只有叶结点和左右子树皆非空的结点，设二叉树叶结点个数为s,则左右子树皆非空的结点个 数是s-1。22. 若一棵二叉树的前序、中序、后序遍历的结果序列均相同，则该二叉树一定是_空二叉树 或是只有一个 根结点的二叉树。23. 采用邻接表表示一有向图，若图中某顶点的入度和出度分别为1）1和D2，则该顶点所对应的单链表的结点个数为_D2。24. 对有序顺序表（07,12,15,18, 27, 32, 46, 65, 83）用二分法查找，若查找成功，则查找所需比较次数最多的键值是 18 83。25. 由n个键值构造的二叉排序树，在等概率查找的假设下，查找成功的平均查找

9、长度的最大值可能达到L（_N +1）_/2。26. 对关键字序列26,36, 41, 38, 44, 15, 68, 12, 06, 51,设 HashSize=13, H（key）=key mod HashSize,并 用链地址法解决冲突，则构造得到的散列表中的指针HP_12所指向的一个单链表（同义词子表）最长。27. 在直接选择、直接插入、冒泡、快速等四种排序方法中，经一趟排序后，任一元素都不能确定其最终位最的排 序方法是直接插入。28. 若采用直接选择排序方法对初始关键字序列5, 3, 5, 1）进行升序排序（其中包括2个值相同的关键字，均为 5），则排序结束后的关键字序列是_（1,3,

10、5,5_）。三、应用题（本大题共5小题.每小题6分。共30分）29. 如题29图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：typedef structDataType dataMaxSize； int： ront2, 1ength2； ）Queue2；对于i=0或1，fronti和1engthi-分别为第i个队列的队头位置和实际长度。分别写出这两个队列满的条件。题图30. 将如题30图所示的含有3棵树的森林转换成相应的二又树，并分别给出该森林先序、中序遍历的结果序列和 相应的二叉树的先序、中序遍历结果序列，根据所得到的遍历结果序列你会得到什么结论？题3。壑31. 对一

11、个图 G,按顺序输入顶点对1, 3、1, 2、2, 4、2, 3、4, 3、4, 2、4, 1,根据建立图的邻接表的算法画出相应的邻接表，并写出在该邻接表上，从顶点2开始搜索得到的一个深度优先搜索 序列和广度优先搜索序列。32. 设顺序存储的线性表共有100个元素，按分块查找（索引查找）的要求等分成5块。若对索引表采用二分查找来 确定块，并在确定的块中进行顺序查找，则在概率相等的情况下，分块查找成功时的平均查找长度是多少（要求利 甩EPiCi来计算并给出详细算式）？33. 若采用堆排序方法对关键字序列265, 301, 751, 129, 937, 863, 742, 694, 076, 43

12、8进行升序排序，写出 其每趟排序结束后的关键字序列。四、算法设计题（本大题共2小题。每小题7分，共14分）34. 假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedef struct nodeint data；struct node*next； ）LinkedNode, *LinkedList,；编写算法，删除值无序的线性表中值最大的元素（设表中各元素的值互不相同）。约整诊后用前登牡性撰;L rnsr -麝.1遗 ，仁直按擂A排序2016年4月高等教着自学考试全国统一命题琴遂 数据结构导论试题答案及评分参考（课程代码槌IU）单璃选择期本太逸共世小踱，每小魏三分森林的先序.中序艇

13、脸结果序列分别为，性34诡7、笙心做了口 5H相应的二此捌的先序：中序遍尚的果序列分别为；MS43曙、诳胰肩1分结论:先序退场森林等同于光序遍压诙溺林对应的.叉构中序泡历森林等同十中序退所该森林对应的二黑耕，3分）核帽的驱搂表为：应果题（本大题共普彩理：猝小眇;i分.共耕分）2&,队列0撕的条件祐I皿tM+Q而妙西） Max 队列 1 沛的条片 JQ-fmn化门+, 1eiiStb|据一转换明到的.一叉树为、埴空厦1本大题共译小题，每小甑芝分 成数据结枸13. qneAt -priDi： -：qprior； 如，三元组表示检找，空二哭橱35.假设树的存储结构采用孩子兄弟表示法，写出树的先序遍历

14、算法。该算法的函数头为 void PreOrderTree（TNode*root，void（*Visit）（），树的孩子兄弟表示法数据类型定义 为： typedestruct tnodeDataType data；struct tnode*firstchilcl， *nextsibling；TNode， *Tree；从顶点2开始搜崇的涂应优先祗室序列：焉41 2分）从顶点2开始报索吟匚度祗先搜成序列：2341（2分）3土分块查找成功财瓣临找长度白对索引表和对块内查拢两龈欢毓。其中对索引袁 查找的 ASLSW 14-2X24-2X3）/5-3. 2C2 分），对查找的 ASL=（Pr 3-r.+

15、30-10. 5（2分兀 所以，分玦查我成功时糊平.拘杳找长度ASLS. 2 + ID, 5=JZ；（2 分）nxt ； j/删牌表中最大元素y?F件分分）（I分）（3分）。分）（1分）G分？第一枚排序重建堆工跚3 8汛751 765 .1-33第二度排序篦建推，肋加74226；J第三次排序.重建堆:1?4卫-53-1 如L 23-438 129 C76J 751 &63 937荒四次排序重建堆京耳43S 301吗5 07C 129J742 71 SG3 937 第五摊序重建堆：必8罕?海 1即076 694 742 751 863 9S7 第六次辨序笊建堆：3E ?G5 07C 129?13

16、8河4 ?42 751舶3 937 第七次排序重建璀死阳卜129 O763O1 43S扣4 742 751 863 937 第八次排序更建堆苔窈07CJ阀5 301 43H WL 742 751 563，奇 第九排序募荏金的6 129 265 301 4明&94 742 751拥3地 四、算法设计题(木大题共i小踵，每小捱7分,共14殳)34. void delete .MAXCUnkList head) /设经性表我狭藉点由童传hftid蚩向 讦 h eatt tiux N u H rtarn jiuhk_P = head next i ma x_P_Pe =： h 七日 d LirrcDf

17、_P = huEcl n尊xt A next； cvrrtint. P_pre head ,* .nexi twhile (current P)(我表中瑟大元素，用指针mzt*_F指而Lf ( urrem. F、e A 山1 Ea n】P % dkta) niax_P CLai ren t _P maxPcurrt：nt_P_pTftrn:i cP_pre it：t majl-Jjni2xt； ficcCtnax.P);Ewen；)工:/拓.以下两种描述形式一均* Evoid PreOrderTrcCTMode * rooti void ( * Visit)O) p root ； iff p) ViAtt ( p - 血匕D s-._ .Pr 卓0 rdt iTr tin Cp fiTJstcbi Id ；PreOrtlrTrcc(p nextsibLri|) j JjftA fK-Jl 或私七7-void PrtiOrr.lerTiet!(TN0r.l root, void t * Visit)。) p=root：hiie (p I I 1 StackEjnpty(jj)(whi3e(p) (Visitfp；如引】f h,p) jp: p -brjjichilci； 口 =叫:叩(5)s p-r p- nexlsihlihg ；,人、Q觐廉结M导论试瓯答案及评分参考第硕(共诚