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

该【02142数据结构导论2024年04月份真题及答案 】是由【小屁孩】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【02142数据结构导论2024年04月份真题及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2016年4月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码02142)本试卷共6页。满分l00分,考试时间l50分钟。考生答题注意事项:。答在试卷上无效,试卷空白处和背面均可作草稿纸。。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。。必须注明大、小题号,。,超出答题区域无效。第一部分选择题(共30分)一、单项选择题(本大题共l5小题。每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。、每个部门负责人领导若干名部门员工,!(整数n≥0)的递归算法是:intFactorial(intn){if(n==o)returnl;elsereturnn*Factorial(n--1);}(n)(logn)(n0)(n2)=q;--:>next=q;>next=p--:>next;p-->next=q;>next—q;q-->next—p--:>next;,s表示人栈操作,x表示出栈操作,,(假设表尾结点为当前队列的队尾元素),若只设头指针,则入队操作、(n)、O(1)(1)、O(1)(1)、O(n)(n)、0(n)(一维数组)结构存储一棵如题7图所示的二叉树,根结点1的下标为l,(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时,,每个元素占2个存储单元,(v,v,v,v,v,v)的无向图的邻接矩阵如题10图所示,则从顶点V出发进行深度优先搜0123450索可能得到的顶点访问序列为A.{v,v,v,v,v,v}B.{v,v,v,v,v,v}0**********C.{v,v,v,v,v,v}D.{v,v,v,v,v,v}01523401452311.“在旅游时从某地出发要去某个目的地,如何选择线路才能使得路程最短”,(n2)(nlogn)(n)(logn),其散列函数为H(key)=keymod11,采用线性探测法处理冲突,,、至多为n—{6,1,4,3,7,2,8,5)进行快速排序,那么以第1个元素6为工作基准的第一趟快速排序结束的结果序列为A.{5,l,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分)二、填空题(本大题共l3小题,每小题2分,共26分):算法+__数据结构__=程序。17.“即使输入非法数据,算法也能适当地做出反应或进行处理,不会产生预料不到的运行结果。”这种评价算法好坏的因素称为__健壮性______。,其结点结构为,若要删除指针q所指向的结点,则需执行如下两条关键语句:q一>priort>next=q-->next;__q->next->priort=q->prior;_______。,若front与rear分别表示队头元素和队尾元素的位置,则判断该循环队列为空的条件表达式是_front==rear_____。。,设二叉树叶结点个数为s,则左右子树皆非空的结点个数是__s-1______。、中序、后序遍历的结果序列均相同,则该二叉树一定是__空二叉树______或是只有一个根结点的二叉树。,若图中某顶点的入度和出度分别为D和D,则该顶点所对应的单链表的结点个数为12__D2______。(07,12,15,18,27,32,46,65,83)用二分法查找,若查找成功,则查找所需比较次数最多的键值是____1883____。,在等概率查找的假设下,查找成功的平均查找长度的最大值可能达到__(_N+1)_/2____。{26,36,41,38,44,15,68,l2,06,51},设HashSize=13,H(key)=keymodHashSize,并用链地址法解决冲突,则构造得到的散列表中的指针HP[__12____]所指向的一个单链表(同义词子表)最长。、直接插入、冒泡、快速等四种排序方法中,经一趟排序后,任一元素都不能确定其最终位最的排序方法是__直接插入______。{5,3,5,1)进行升序排序(其中包括2个值相同的关键字,均为5),则排序结束后的关键字序列是__(1,3,5,5__)____。三、应用题(。共30分),利用同一循环向量空间实现两个队列,其类型Queue2定义如下:typedefstruct{DataTypedata[MaxSize];int:[ront[2],length[2];)Queue2;对于i=0或l,front[i]和length[i-]分别为第i个队列的队头位置和实际长度。分别写出这两个队列满的条件。,并分别给出该森林先序、中序遍历的结果序列和相应的二叉树的先序、中序遍历结果序列,根据所得到的遍历结果序列你会得到什么结论?,按顺序输入顶点对<1,3>、<1,2>、<2,4>、<2,3>、<4,3>、<4,2>、<4,l>,根据建立图的邻接表的算法画出相应的邻接表,并写出在该邻接表上,从顶点2开始搜索得到的一个深度优先搜索序列和广度优先搜索序列。,按分块查找(索引查找)的要求等分成5块。若对索引表采用二分查找来确定块,并在确定的块中进行顺序查找,则在概率相等的情况下,分块查找成功时的平均查找长度是多少(要求利甩∑PC来计算并给出详细算式)?{265,301,751,129,937,863,742,694,076,438}进行升序排序,写出其每趟排序结束后的关键字序列。四、算法设计题(本大题共2小题。每小题7分,共l4分),单链表的类型定义如下:typedefstructnode{intdata;structnode*next;)LinkedNode,*LinkedList,;编写算法,删除值无序的线性表中值最大的元素(设表中各元素的值互不相同)。,写出树的先序遍历算法。该算法的函数头为:voidPreOrderTree(TNode*root,void(*Visit)()),树的孩子兄弟表示法数据类型定义为:typede{structtnode{DataTypedata;structtnode*firstchilcl,*nextsibling;}TNode,*Tree;