华中农业大学2018考研真题之867-数据结构与算法

华中农业大学2018年硕士研究生入学考试试科目代码及名称：867数据结构与算法题纸第1页共4页注意：所有答案必须写在答题本上，不得写在试题纸上，否则无效。一、名词解释（共20分，每题4分）1、算法及算法的特性2、树的度及深度3、完全二叉树4、索引文件5、强连通性二、选择题（共30分，每题2分）1、设核S和队列Q的初始状态均为空，元素ABCDEFG依次进技S。若每个元素出校后立即进入队列Q，且7个元素的出队顺序是BDCFEAG，则核S的容量至少是：A.1B.2C.3D.42、已知一棵完全二叉树的第六层（根为第一层〉有8个叶子结点，则完全二叉树的结点个数最多是：A.39B.52C.111D.1193、下列叙述中不符合m阶B树定义要求的是：A.根结点最多有m棵子树B.所有叶结点在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接4、若无向图中含有7个顶点，贝。保证图在任何情况下都是连通的，需要的边数最少是：A.6B.15C.16D.215、对一组数据（7,17,21,93,10,16）进行排序，若前三趟排序结果如下，则采用的排序方法是：第一趟：7,17,21,10,16,93第二趟：7,17,10,16,21,93第二趟：7,10,16,17,21,93A.冒泡排序B.希尔排序C.归并排序D.基数排序6、已知一才果有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是：A.115B.116C.1895D.18967、已知字符串S为“abaabaabacacaabaabcc.模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失自己”（s[i]!=t[i］）时，i=j习，则下次开始匹配时，i和j的值分别是：A.i=l;j=O;B.i二5;j=O;C.i=5;j=2;D.i=6;j=2;8、用哈希（散列〉方法处理冲突（碰撞〉时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是：A.存储效率B.数列函数C.装填（装载〉因子D.平均查找长度华中农业大学2018年硕士研究生入学考试试科目代码及名称：867数据结构与算法题纸第2页共4页2注意：所有答案必须写在答题本上，不得写在试题纸上，否则无效。9、循环队列放在一维数组A[O···M-1］中，endl指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是：A.队空：endl==end2;队满：endl==(end2+1)modMB.队空：endl==end2;队满：end2==(endl+1)mod(M-1)c.队空：end2==(endl+l)modM;队满：endl==(end2+1)modMD.队空：endl==(end2+1)modM；队满：end2==(end1+1)mod(M-1)10、非空的循环单链表head的尾结点（由p所指向〉满足：A.P一＞next==N1JLL;B.p==NULL;C.p-next==head;D.p==head11、查找效率最高的二叉排序树是：A.所有结点的左子树都为空的二叉排序树B.所有结点的右子树都为空的二叉排序树c.平衡二叉树D.没有左子树的二叉排序树12、下面关于求关键路径的说法不正确的是：A.求关键路径是以拓扑排序为基础的B.关键活动一定位于关键路径上C.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同D.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差13、在一个单链表中，若q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行：A.P甲＞next=s一＞next;s-next=p:B.s-next=p一＞next;p＞next=s;C.P一＞next=s;s一＞next=q;D.q一＞next=s;s-next=p;14、设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储，all为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为：A.23B.33C.18D.4015、就平均查找速度而言，下列几种查找速度从慢至快的关系是：A.JI顶序折半哈希分块B.分块折半哈希顺序C.顺序分块折半哈希D.顺序哈希分块折半三、填空题（共20分，每题2分）1、广义表A=(x，旬，b,c,d））的表尾是一一一华中农业大学2018年硕士研究生入学考试试科目代码及名称：867数据结构与算法题纸第3页共4页32211注意：所有答案必须写在答题本上，不得写在试题纸上，否则无效。2、在双循环链表中，删除指针p所指结点的语句序列是一一一和一一一。3、快速排序是一一一排序改进后的结果。4、求解一个图的单源和多源最短路径的算法分别是一一一和Floyd算法。5、通常称表示前驱和后继的指针叫做一一一’而这种使树中结点的空指针成员存放前驱或后继信息的过程叫做一一一。6、图的一一一优先搜索类似于树的层次遍历。7、设给定权值总数有n个，其哈夫曼树的结点总数为一一一。8、希尔排序、快速排序和冒泡排序中一一一是稳定的排序方法。9、堆排序的两个重要步骤其一是一一一’其二是调整堆。10、KMP算法中，串＇ababaaababaa’的next数组为一一一。四、应用题（共50分，第1-6题每题7分，第7题8分）l、给定二叉树的两种遍历序列，分别是：前序遍历序列：EBIDGCAHF;中序遍历序列：EIGDCBHFA,(1）试画出二叉树；(2）并给出二叉树的后序遍历序列。2、下图是一个无向带权图，请按照Prim算法从A节点出发构造一棵最小生成树，并画出其生成过程。7812101683、给定一组数列（10,18,16,25,6,9,16）分别代表字符A,B,C,D,E,F,G出现的频率，试画出哈夫曼树的构造过程，并给出各字符的编码值。4、已知长度为12的表（jan,feb,mar,apr,may,june,july,aug,sep,oct,nov,dec），请按表中元素顺序构造一棵二叉平衡树，并简单的画出构造过程。其中，无旋转的调整可以直接画在一张图上，有旋转的调整请单独画图并备注清楚。5、给定关键字序列：15,38,ll,84,49,20,7,33,l4,29,36。请写出以下3种排序方法的第一趟排序结果(1）选择排序（2）快速排序（3）增量为4的希尔排序；请写出建好一个大根堆的结果；请写出第一趟堆排序以后的结果。20华中农业大学2018年硕士研究生入学考试试科目代码及名称：867数据结构与算法题纸第4页共4页4注意：所有答案必须写在答题本上，不得写在试题纸上，否则无效。6、设散列表的长度为13，散列函数为H(k)=k%13，给定的关键码序列为19,13,22,02,68,15,84,26。试画出用线性探测法解决冲突时所构成的散列表，并求出平均查找长度ASL。7、用迪杰斯特拉（Dijkstra）算法求下图中Vl顶点到其他个顶点的最短距离和最短路径，请根据下表补充完整的求解过程。终点从vl到各终点的距离值和最短路径的求解过程I=lI=2I=31=4V2V3V4V5Vjs提示：Vj为每次新并入的顶点，S为巳求得最短路径的顶点的集合。五、程序设计题（共30分，每题10分）l、设计一个求二叉树的宽度的算法。2、已知一个带表头结点的线性链表，试写出用直接插入排序方法将其结点按递增顺序排序的算法，算法中要尽可能少用辅助存储空间。3、请设计深度遍历图的非递归算法。