《2018年湖北华中农业大学数据结构与算法考研真题》由会员分享，可在线阅读，更多相关《2018年湖北华中农业大学数据结构与算法考研真题（4页珍藏版）》请在金锄头文库上搜索。
1、历年考试真题1/420182018 年湖北华中农业大学数据结构与算法考研真题年湖北华中农业大学数据结构与算法考研真题一、名词解释（共 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.1
2、193、下列叙述中不符合 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，该
3、树对应的二叉树中无右孩子的结点个数是历年考试真题2/4A.115B.116C.18955D.18967、已知字符串 S 为abaabaabacacaabaabcc.模式串 t 为abaabc，采 用 KMP 算法进行匹配，第一次出现失配时，i=j=5，则下次开始匹配时，i 和 j 的值分别是A.i=1;j=0;B.i=5;j=0;C.i=5;j=2;D.i=6;j=2;8、用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是A.存储效率B.数列函数C.装填（装载）因子D.平均查找长度9、循环队列放在一维数组 AOM-1中，endl 指向队头元素，e
4、nd2 指向 队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多 能容纳 M-1 个元素。初始时为空。下列判断队空和队满的条件中，正确的是A.队空end1=end2;队满endl=（end2+1）mod MB.队空 end1=end2;队满end2=（endl+1）mod（M-1）C.队空end2=（end1+1）mod M;队满 end1=（end2+1）mod MD.队空end1=（end2+1）mod M;队满 end2=（endl+1）mod（M-1）10、非空的循环单链表 head 的尾结点（由 p 所指向）满足A.p-next=NULL;B.p=NUL;C.p-n
5、ext=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;历年考试真
6、题3/4B.s-next=p-next;p-next=s;C.p-next=s;s-next=q;D.q-next=S;s-next=p;14、设有一个对称矩阵 A，采用压缩存储方式，以行序为主序存储，al1 为第一个元素，其存储地址为 1，每个元素占一个地址空间，则 a85 地址为A.23B.33C.18D.4015、就平均查找速度而言，下列几种查找速度从慢至快的关系是A.顺序 折半哈希 分块B.分块 折半 哈希 顺序C.顺序分块 折半 哈希D.顺序 哈希 分块 折半三、填空题（共 20 分，每题 2 分）1、广义表 A=（x，（a，b，c，d）的表尾是_。2、在双循环链表中，删除指针 p
7、所指结点的语句序列是_和_。3、快速排序是_排序改进后的结果。4、求解一个图的单源和多源最短路径的算法分别是_和 Floyd 算法。5、通常称表示前驱和后继的指针叫做_，而这种使树中结点的空指针成员存放前驱或后继信息的过程叫做6、图的_优先搜索类似于树的层次遍历。7、设给定权值总数有 n 个，其哈夫曼树的结点总数为 _8、希尔排序、快速排序和冒泡排序中_是稳定的排序方法。其二是调整堆。9、堆排序的两个重要步骤其一是_10、KMP 算法中，串ababaaababaa的 next 数组为_。四、应用题（共 50 分，第 1-6 题每题 7 分，第 7 题 8 分）1、给定二叉树的两种遍历序列，分别
8、是前序遍历序列EBIDGCAHF;中序遍历序列EIGDCBHFA，（1）试画出二叉树;（2）并给出二叉树的后序遍历序列。2、下图是一个无向带权图，请按照 Prim 算法从 A 节点出发构造一棵最小生成树，并画出其生成过程。历年考试真题4/43、给定一组数列（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），请按表中元素顺序构造一棵二叉平衡树，并简单的画出构造过程。其中，无旋转的
9、调整可以直接画在一张图上，有旋转的调整请单独画图并备注清楚。5、给定关键字序列15.38.11.84.49.20.7.33.14.29.36。请写出以下 3 种排序方法的第一趟排序结果（1）选择排序（2）快速排序（3）增量为 4 的希尔排序;请写出建好一个大根堆的结果;请写出第一趟堆排序以后的结果。6、设散列表的长度为 13，散列函数为 H（k）=k，给定的关键码序列为 19.13.22，02，68.15.84.26。试画出用线性探测法解决冲突时所构成的散列表，并求出平均查找长度 ASL。7、用迪杰斯特拉（Dijkstra）算法求下图中 V1 顶点到其他个顶点的最短距离和最短路径，请根据下表补充完整的求解过程。提示Vj 为每次新并入的顶点，S 为已求得最短路径的顶点的集合。五、程序设计题（共 30 分，每题 10 分）1、设计一个求二叉树的宽度的算法。2、已知一个带表头结点的线性链表，试写出用直接插入排序方法将其结点按递增顺序排序的算法，算法中要尽可能少用辅助存储空间。3、请设计深度遍历图的非递归算法。
