《(NEW)华中科技大学软件学院887数据结构与算法分析历年考研真题汇编》由会员分享，可在线阅读，更多相关《(NEW)华中科技大学软件学院887数据结构与算法分析历年考研真题汇编（109页珍藏版）》请在金锄头文库上搜索。
1、目录 2006年华中科技大学软件学院451数据结构与算法分析考研真题及部分 参考答案 2007年华中科技大学软件学院427数据结构与算法分析考研真题及部分 参考答案 2011年华中科技大学软件学院数据结构与算法分析考研真题（回忆版） 及部分参考答案 2012年华中科技大学软件学院数据结构与算法分析考研真题及部分参考 答案 2013年华中科技大学软件学院数据结构与算法分析考研真题及部分参考 答案 2014年华中科技大学软件学院数据结构与算法分析考研真题（回忆版） 及部分参考答案 2015年华中科技大学软件学院数据结构与算法分析考研真题（回忆版） 及部分参考答案 2016年华中科技大学软件学院数据
2、结构与算法分析考研真题（回忆版） 2018年华中科技大学软件学院数据结构与算法分析考研真题及部分参考 答案 2019年华中科技大学软件学院数据结构与算法分析考研真题及部分参考 答案 2006年华中科技大学软件学院451 数据结构与算法分析考研真题及 部分参考答案 2006年数据结构与算法分析试题部分参考答案 一、术语解释：（略） 二、选择题： 15：CDCDC 三、简答题： 1 【答案】 2 【答案】 第一趟：6 8 5 7 2 4 1 3 第二趟：5 6 7 8 1 2 3 4 第三趟：1 2 3 4 5 6 7 8 3 【答案】 4 【答案】 5 【答案】 A:11 B:01010 C:0
3、111 D:00 E:011111 F:10 G:0100 H:0101 四、应用及编程题 1 【答案】 该算法的时间复杂度为O（n），空间复杂度为O（n）。 2 【答案】 该算法为中序遍历，时间复杂度为O（n）。 2007年华中科技大学软件学院427 数据结构与算法分析考研真题及 部分参考答案 2007年数据结构与算法分析试题部分参考答案 一、术语解释：（略） 二、选择题： 15：BCDCD 三、简答题： 1 【答案】 2 【答案】 由邻接矩阵可得该图为： 3 【答案】 设N2K，T（N）T（N/2）N，即T（2K）T（2K1）2K T（2K2）2K12KT（20）2K2K12K22K 11
4、2*2logn12n1，所以时间复杂度为O（2n1）。 4 【答案】 第一趟：1 6 5 4 3 2 第二趟：1 2 6 5 4 3 第三趟：1 2 3 6 5 4 第四趟：1 2 3 4 6 5 第五趟：1 2 3 4 5 6 5 【答案】 H（key）key MOD 7 H（key）（key/100（key/10key/100）*10）（key（key （key/10）*10） MOD 7 四、应用编程题： 1 【答案】 （a） （b）该算法的时间复杂度为O（n3）。 （c） 2 略【答案】 2011年华中科技大学软件学院数 据结构与算法分析考研真题（回 忆版）及部分参考答案 2011年数
5、据结构与算法分析试题部分参考答案 一、术语解释： 1 线性表：n个数据元素的有限序列。【答案】 2 树的节点的层次：从根开始定义，根为第一层，根的孩子为第 二层。若某节点在第l层，则其子树的根就在第l1层。 【答案】 3 排序：将一个数据元素（或记录）的任意序列，重新排列成一 个按关键字有序的序列。 【答案】 4 完全图：有1/2*n*（n1）条边的无向图成为完全图。【答案】 5 最小生成树：构造连通网的最小代价生成树。【答案】 二、选择题： 1 A【答案】 min0，max9，（minmax）/24，直接命中5。【解析】 2 B【答案】 关键词：主定理，解决一切类似问题的通用公式。【解析】
6、3 D【答案】 错题。【解析】 4 C【答案】 栈是先进后出，队列是先进先出，都只能在端点操作。【解析】 5 C【答案】 三、简答题： 1 关键思路在于，一个栈从数组顶往数组底生长，另一个栈反 之。 【解析】 2 【答案】 hash表的基本构造方法【解析】 3 【答案】 Func（1）: 1 Func（2）: 1 4 1 Func（3）: 1 9 1 Func（5）: 1 4 1 25 1 4 1 该算法的时间复杂度为O（n）。 4 【答案】 A:101 B:00 C:111 D:10010 E:110 F:010 G:01111 H:100 I:0110 5 【答案】 深度优先遍历：V1 V
7、2 V4 V5 V7 V8 V9 V3 V6 广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8 V9 四、应用编程题： 1 【答案】 定义两个指针p，q； 初始化时p指向数组中负数部分的结 尾，q指向数组中正数部分的开头； 循环执行下面的逻辑； p指针 向后移动，碰到正数停下，q指针向前移动，碰到负数停下； 两个指 针都停住之后，如果p和q还没相遇，则交换p，q所指向元素的值； 如 果p，q相遇了，那么跳出循环。 【解析】 2 【答案】 递归遍历树【考点】 2012年华中科技大学软件学院数 据结构与算法分析考研真题及部 分参考答案 2012年数据结构与算法分析试题部分参考答案 一、
8、术语解释：（略） 二、选择题： 1 D【答案】 整理一下之后可以得到hanoi（n）Hanoi（n1）*21，容易 看出是指数时间复杂度了。 【解析】 2 B【答案】 快排的特点，如果取开头/结尾第一个元素作为枢纽元，那么在 数据完全正序/逆序的情况下，其时间复杂度为n方，这个是最坏的情 况。一般情况下，时间复杂度是n*logn。 【解析】 3 A【答案】 装填因子的定义，哈希表长度为11，放了11个元素。【解析】 4 D【答案】 结果是0。【解析】 5 A【答案】 B-树的定义，p238，第3条。除根以外的所有非终端节点至少有 m/2棵子树，在本题就是，至少3颗子树。 【解析】 三、简答题：
9、 1 【答案】 2 【答案】 函数调用过程如下： 由于我们不关心函数的返回值，代码实际上可以转换为【解析】 这样就很容易处理了，如果实在不能理解，建议敲到编译器里，单步调 试。 3 模式串的next值：0 1 1 1 2【答案】 考察的是Kmp算法的定义，具体匹配过程如下【解析】 4 深度优先遍历：V1 V2 V3 V6 V4 V5 V7【答案】 深度优先遍历，跟着定义做就行了，把原图画出来也许有助于 理解，解不止一组。 【解析】 5 【答案】 A:0010 B:1101 C:11001 D:111 E:000 F:0011 G:10 H:01 I:110000 J:11001 重复出现很多次
10、的题目了，树的画法不唯一。【解析】 四、算法题 1 【答案】 该算法的时间复杂度为O（n）。 建立两个指针，分别放置在数组的头和尾； 计算两个指针 所指向元素的和，如果大于x，尾指针前移一位，如果小于x，头指针后 移一位； 如果两个指针相遇，那么说明无解。 【解析】 2 【答案】 标准递归，空节点高度为1，其他节点的高度为max（左子树 高度，右子树高度）1。 【解析】 2013年华中科技大学软件学院数 据结构与算法分析考研真题及部 分参考答案 2013年数据结构与算法分析试题部分参考答案 一、术语解释（略） 二、单选 1 没有正确答案【答案】 题目是错的。这是阿克曼函数，其正确定义为【解析】
11、 若m0，返回n1； 若m0且n0，返回Ackermann（m1，1）； 若m0且n0，返回Ackermann（m1，Ackermann（m，n1）。 在这个定义下：Ackermann（2，1）5。 2 C【答案】 T（1）1，T（2）T（1）23，T（N）n*（n 1）/2，即N2的时间复杂度。 【解析】 3 D【答案】 先序第一个为A，说明根节点为A，那么后续遍历的最后一个必 然为A，但是没有一个符合。 【解析】 4 A【答案】 准确来说应该就是栈stack，不是堆栈。【解析】 5 C【答案】 kmp的特点。【解析】 三、简答 1 【答案】 2 【答案】 3 【答案】 4 【答案】 5 【
12、答案】 四、应用编程题 1题目应该是有问题的，123456所有位加起来是21，再加起来是3，而 不是题目中给的6。 2 【答案】 分治思想，先分别求出前半部分和后半部分数组的最大值和最 小值，然后两部分中的最大值和最小值分别比较求出整个数组的最大值 和最小值，比较次数为3*N/22次。 【解析】 2014年华中科技大学软件学院数 据结构与算法分析考研真题（回 忆版）及部分参考答案 一、填空题： 1写出数据结构的四种基本逻辑结构。 2写出算法的四种特性。 3一个栈中有六个数字，要求对其进行重新排序，求堆栈的最小容 量。 4求出一串数字的非平凡子串个数。 5求一平衡二叉树的成功查找长度和不成功查找
13、长度。 二、选择题：（略） 三、分析题： 1给出一个算法过程，要求列出它的开销公式并解出开销函数。 2根据题意画出Huffman前缀码树并求出编码长度。 3该题关于KRUSKAL（V，E，w）的最小生成树算法，由给出的具 体算法写出其中元素A的变化过程，并求出最小生成树的权。 4由题中给出的网络流图求剩余流图，在图中标出最小切割，解出 St的最大网络流。 5给出一个图，从a开始深度优先搜索，算出每个节点发现和结束的时 刻d/f，根据搜索结果标出图上边的类型。 四、算法题： 1 根据最短路径延伸算法给出递归表达式，将全成对最短路径填写到题目 中的44表格中，并写出表格中某一阴影指定位置的路径。
14、2证明：A（u，v）是图G最小生成树的子集。 3权重函数f，动态划归，写递推式，用伪码描述算法。 2014年数据结构与算法分析试题部分参考答案 一、填空题： 1 集合，线性结构，树形结构，图状结构或网状结构（教材 p5）。 【解析】 2 有穷性，确定性，可行性，输入，输出。任选4个。【解析】 3 题目应该是有问题，只有一个栈的话，没法排序啊，弹出来的 元素没地方保存。 【解析】 4 题目想说的可能是，给出一个字符串S，求出其互异非平凡子串 （非空且不同于S）的个数。那么如果S中的字符各不相同，且长度为n 的话，那么答案是n*n/2n/21。 【解析】 5 大概跟有序数组的二分查找时的成功长度/
15、不成功长度的算法差 不多吧。 【解析】 三、分析题 1 略，估计会用到主定理。【解析】 2 霍夫曼树的构建是基础了，11年的试卷就有一题。【解析】 3 课本p175。【解析】 4 算法导论p396-430，第26章最大流。【解析】 2015年华中科技大学软件学院数 据结构与算法分析考研真题（回 忆版）及部分参考答案 2015年数据结构与算法分析试题部分参考答案 一、名词解释（略） 二、单项选择题 1 A【答案】 n为非负奇数的时候，递归的复杂度容易知道为n/2，n为非负偶 数时，通过常数次操作即可转换为奇数的情况，所以总的复杂度是 O（n）。 【解析】 2 D【答案】 参见下图，只有归并排序在
16、最好与最坏的情况下的时间复杂度 都是n*log（n）。ps：这个图的希尔排序的时间复杂度有点问题。 【解析】 3略 4 C【答案】 希望查找的元素落在数组每一位上的几率均等，那么进行n次查 找，理论上需要进行（123n）（1n）*n/2次比较，除以 n，得到时间复杂度为（n1）/2。 【解析】 5 O（n）【答案】 三、分析题 1 【分析】基础题了，算法如下： 2 【分析】哈夫曼树的构建出现很多次了，11年，12年都有。 3 【分析】原地调整为最大堆。参考课本先关章节例题，从第n/2个元素 到第一个元素，做“筛选”操作。这个题目可以跟2013年的3.4题做比较， 2013的题目应该是将元素逐个插入空白的最大堆中，然后每次插入都需 要维护这个堆的性质，需做n1次插入维护操作。2015的题目是将数组 原地直接调整为最大堆，需要做n/2次“筛选”操作。 4 【分析】Dijkstra算法。 5 【分析】跟一般的二分查找指定元
