湖南大学-计算机866 数据结构考研真题（2015-2020年）.pdf

luolifeng 湖南大学866 数据结构真题 目 录 2015年湖南大学866数据结构真题回忆版 2 2016年湖南大学866数据结构真题回忆版 2 2017年湖南大学866数据结构真题回忆版 3 2018湖南大学866数据结构真题回忆版 4 2019年湖南大学866数据结构真题回忆 5 2020湖南大学计算机866数据结构真题回忆版 6 2015年湖南大学866数据结构真题回忆版 一、10个选择题，每个2分，题目较简单 二、2个简答，10分一个 第一题：一堆数字排序有：2、20n、Log2 n、Log3、n^2、n^2/3之类的一些数。 第二题：高为h 的完全二叉树最多节点数。 三、6个解答题 10分一个 第一题：一组进栈，2组出栈，判断出栈是否正确。 第二题：给出二叉树前序和中序，要求画出二叉树然后求后序。 第三题： 第四题：给一个图，求所有拓扑排序，然后求关键路径和长度。 第五题：给出一组字母和出现频率，求哈夫曼编码。 第六题：哈希表数据是否可以直接删除，然后给出关键字和构造函数，构造出哈希表，然后写出 每个的查询次数。 四、4个算法一共50分，前2个 10分一个，后2个15分一个 第一题：有序单链表插入一个数，保持有序。 第二题：求二叉树中度为2的节点个数。 第三题：深度优先搜索非强连通图。 第四题：对一个单链表用冒泡法排序。 2017年湖南大学866数据结构真题回忆版 一、10个选择 根据下列哪个选项不能确定一棵树 A. 先序和中序B.后序和中序C.层次和后序D.层次和中序 二、3个简答 第一题：给出两个算法，分析它们的时间复杂度。 第二题：一个在一个数组上实现m个栈 如何实现进栈和出栈操作 。 三、5个解答题 第一题：给定中序和后序序列，画出二叉树并前序遍历。 第二题：给定图，画出邻接矩阵，广度优先遍历，迪斯卡杰夫求最短路径。 第三题：散列表，求查找成功的平均长度。 第四题：快速排序。 第五题：直接插入排序和堆排序。 四、4个算法设计 （要求写出算法思想和代码，以及计算出时间复杂度） 第一题：设计一个算法，在数组上查找一个数，找到就将其放在第一位，找不到则将所有元素后 移，并将其放在首位。 第二题：设计一个算法，逆置队列的元素 （要求使用栈实现）。 第三题：设计一个算法，统计存储在二叉树中的正整数个数。 第四题：设计一个算法，基于深度优先遍历统计无向图中的连通分量个数。 2018湖南大学866数据结构真题回忆版 一、选择题 （一分一个 一共十个 很简单） 二、简答题 （五分一个 一共三个） 第一题：给出一段代码，求时间复杂度。 第二题：判断一个单链表是否存在回路。 第三题不太记得了 三、分析题 （15分一个 一共5个） 第一题：给出一组序列，判断是什么排序，然后说出归并排序的思想，根据原始序列进行排序直 到序列有序，最后是增加一个数字，以第一个为驱值，说出快速排序的思想，根据原始序列 进 行排序直到序列有序。 第二题：给出一个图，写出邻接表的形式，利用prim算法画出最小生成树，写出拓扑排序。 第三题：给出一组二叉排序数，告诉前序排序，画出这棵树，写出后序排序。 第四题：哈夫曼编码，等长编码，比较平均码长。 第五题不太记得了，好像挺简单的。 四、程序设计题 （共四题，前两题10分一个，后两题15分一个） 第一题：首先定义ADT规范式，给出算法的设计思想，以及伪代码，关键步骤给出注释。 第二题：设计算法及写出伪代码，加上注释。 第三题：一个有向图以邻接表的形式存储，删除给出的任意一条边。 第四题：给出一个时间复杂度优于0 （n^2）的算法,给定两个数组A,B 以及K,要求a∈A，b∈B， a+b K。 2019年湖南大学866数据结构真题回忆 今年真题取消了选择题，第一大题是简答题共五个，第二大题也是简答，第三大题算法 程序设计。 —、简答题 1、 给出一段代码，求时间复杂度，给出说明。 2、 给出一个栈和一个队列，只有栈中有元素。栈的操作规定只能出栈输出或者入队，队列的 操作规定只能出队输出或者入栈。给出一个输出数组序列，问能不能得出来。 3、 n个结点的4叉树，问最小高度，并写出求解步骤。 4、 给出四种情况，问哪一种情况最适合排序算法来做，给出原因。 5、给出几个字母和出现顺序，做赫夫曼树和等长编码，并求两种情况的平均长度