华中科技大学软件学院887数据结构与算法分析历年考研真题汇编.pdf

目录2006年华中科技大学软件学院451数据结构与算法分析考研真题及部分参考答案2007年华中科技大学软件学院427数据结构与算法分析考研真题及部分参考答案2011年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）及部分参考答案2012年华中科技大学软件学院数据结构与算法分析考研真题及部分参考答案2013年华中科技大学软件学院数据结构与算法分析考研真题及部分参考答案2014年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）及部分参考答案2015年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）及部分参考答案2016年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）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 83【答案】4【答案】5【答案】A:11B:01010C:0111D:00E:011111F:10G:0100H: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）2KT（2K2）2K12KT（20）2K2K12K22K112*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 65【答案】H（key）key MOD 7H（key）（key/100（key/10key/100）*10）（key（key（key/10）*10）MOD 7四、应用编程题：1【答案】（a）（b）该算法的时间复杂度为O（n3）。（c）2略【答案】2011年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）及部分参考答案2011年数据结构与算法分析试题部分参考答案一、术语解释：1线性表：n个数据元素的有限序列。【答案】2树的节点的层次：从根开始定义，根为第一层，根的孩子为第二层。若某节点在第l层，则其子树的根就在第l1层。【答案】3排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。【答案】4完全图：有1/2*n*（n1）条边的无向图成为完全图。【答案】5最小生成树：构造连通网的最小代价生成树。【答案】二、选择题：1A【答案】min0，max9，（minmax）/24，直接命中5。【解析】2B【答案】关键词：主定理，解决一切类似问题的通用公式。【解析】3D【答案】错题。【解析】4C【答案】栈是先进后出，队列是先进先出，都只能在端点操作。【解析】5C【答案】三、简答题：1关键思路在于，一个栈从数组顶往数组底生长，另一个栈反之。【解析】2【答案】hash表的基本构造方法【解析】3【答案】Func（1）:1Func（2）:1 4 1Func（3）:1 9 1Func（5）:1 4 1 25 1 4 1该算法的时间复杂度为O（n）。4【答案】A:101B:00C:111D:10010E:110F:010G:01111H:100I:01105【答案】深度优先遍历：V1 V2 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年数据结构与算法分析试题部分参考答案一、术语解释：（略）二、选择题：1D【答案】整理一下之后可以得到hanoi（n）Hanoi（n1）*21，容易看出是指数时间复杂度了。【解析】2B【答案】快排的特点，如果取开头/结尾第一个元素作为枢纽元，那么在数据完全正序/逆序的情况下，其时间复杂度为n方，这个是最坏的情况。一般情况下，时间复杂度是n*logn。【解析】3A【答案】装填因子的定义，哈希表长度为11，放了11个元素。【解析】4D【答案】结果是0。【解析】5A【答案】B-树的定义，p238，第3条。除根以外的所有非终端节点至少有m/2棵子树，在本题就是，至少3颗子树。【解析】三、简答题：1【答案】2【答案】函数调用过程如下：由于我们不关心函数的返回值，代码实际上可以转换为【解析】这样就很容易处理了，如果实在不能理解，建议敲到编译器里，单步调试。3模式串的next值：0 1 1 1 2【答案】考察的是Kmp算法的定义，具体匹配过程如下【解析】4深度优先遍历：V1 V2 V3 V6 V4 V5 V7【答案】深度优先遍历，跟着定义做就行了，把原图画出来也许有助于理解，解不止一组。【解析】5【答案】A:0010B:1101C:11001D:111E:000F:0011G:10H:01I:110000J:11001重复出现很多次的题目了，树的画法不唯一。【解析】四、算法题1【答案】该算法的时间复杂度为O（n）。建立两个指针，分别放置在数组的头和尾；计算两个指针所指向元素的和，如果大于x，尾指针前移一位，如果小于x，头指针后移一位；如果两个指针相遇，那么说明无解。【解析】2【答案】标准递归，空节点高度为1，其他节点的高度为max（左子树高度，右子树高度）1。【解析】2013年华中科技大学软件学院数据结构与算法分析考研真题及部分参考答案2013年数据结构与算法分析试题部分参考答案一、术语解释（略）二、单选1没有正确答案【答案】题目是错的。这是阿克曼函数，其正确定义为【解析】若m0，返回n1；若m0且n0，返回Ackermann（m1，1）；若m0且n0，返回Ackermann（m1，Ackermann（m，n1）。在这个定义下：Ackermann（2，1）5。2C【答案】T（1）1，T（2）T（1）23，T（N）n*（n1）/2，即N2的时间复杂度。【解析】3D【答案】先序第一个为A，说明根节点为A，那么后续遍历的最后一个必然为A，但是没有一个符合。【解析】4A【答案】准确来说应该就是栈stack，不是堆栈。【解析】5C【答案】kmp的特点。【解析】三、简答1【答案】2【答案】3【答案】4【答案】5【答案】四、应用编程题1题目应该是有问题的，123456所有位加起来是21，再加起来是3，而不是题目中给的6。2【答案】分治思想，先分别求出前半部分和后半部分数组的最大值和最小值，然后两部分中的最大值和最小值分别比较求出整个数组的最大值和最小值，比较次数为3*N/22次。【解析】2014年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）及部分参考答案一、填空题：1写出数据结构的四种基本逻辑结构。2写出算法的四种特性。3一个栈中有六个数字，要求对其进行重新排序，求堆栈的最小容量。4求出一串数字的非平凡子串个数。5求一平衡二叉树的成功查找长度和不成功查找长度。二、选择题：（略）三、分析题：1给出一个算法过程，要求列出它的开销公式并解出开销函数。2根据题意画出Huffman前缀码树并求出编码长度。3该题关于KRUSKAL（V，E，w）的最小生成树算法，由给出的具体算法写出其中元素A的变化过程，并求出最小生成树的权。4由题中给出的网络流图求剩余流图，在图中标出最小切割，解出St的最大网络流。5给出一个图，从a开始深度优先搜索，算出每个节点发现和结束的时刻d/f，根据搜索结果标出图上边的类型。四、算法题：1根据最短路径延伸算法给出递归表达式，将全成对最短路径填写到题目中的44表格中，并写出表格中某一阴影指定位置的路径。2证明：A（u，v）是图G最小生成树的子集。3权重函数f，动态划归，写递推式，用伪码描述算法。2014年数据结构与算法分析试题部分参考答案一、填空题：1集合，线性结构，树形结构，图状结构或网状结构（教材p5）。【解析】2有穷性，确定性，可行性，输入，输出。任选4个。【解析】3题目应该是有问题，只有一个栈的话，没法排序啊，弹出来的元素没地方保存。【解析】4题目想说的可能是，给出一个字符串S，求出其互异非平凡子串（非空且不同于S）的个数。那么如果S中的字符各不相同，且长度为n的话，那么答案是n*n/2n/21。【解析】5大概跟有序数组的二分查找时的成功长度/不成功长度的算法差不多吧。【解析】三、分析题1略，估计会用到主定理。【解析】2霍夫曼树的构建是基础了，11年的试卷就有一题。【解析】3课本p175。【解析】4算法导论p396-430，第26章最大流。【解析】2015年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）及部分参考答案2015年数据结构与算法分析试题部分参考答案一、名词解释（略）二、单项选择题1A【答案】n为非负奇数的时候，递归的复杂度容易知道为n/2，n为非负偶数时，通过常数次操作即可转换为奇数的情况，所以总的复杂度是O（n）。【解析】2D【答案】参见下图，只有归并排序在最好与最坏的情况下的时间复杂度都是n*log（n）。ps：这个图的希尔排序的时间复杂度有点问题。【解析】3略4C【答案】希望查找的元素落在数组每一位上的几率均等，那么进行n次查找，理论上需要进行（123n）（1n）*n/2次比较，除以n，得到时间复杂度为（n1）/2。【解析】5O（n）【答案】三、分析题1【分析】基础题了，算法如下：2【分析】哈夫曼树的构建出现很多次了，11年，12年都有。3【分析】原地调整为最大堆。参考课本先关章节例题，从第n/2个元素到第一个元素，做“筛选”操作。这个题目可以跟2013年的3.4题做比较，2013的题目应该是将元素逐个插入空白的最大堆中，然后每次插入都需要维护这个堆的性质，需做n1次插入维护操作。2015的题目是将数组原地直接调整为最大堆，需要做n/2次“筛选”操作。4【分析】Dijkstra算法。5【分析】跟一般的二分查找指定元素类似，只是判断条件由arraymid和target的比较改成arraymid和mid的比较：如果arraymidmid，那么取后半段继续二分比较；如果arraymidmid，那么取前半段继续二分比较；如果arraymidmid，那么命中了。时间复杂度是log（n）。四、算法设计题1【分析】思路：递归，这个思路可以用来解决相似的问题，譬如求树高，或者求树的所有Node-data的和。2【分析】逆序对的计算是一个经典算法问题，方法有多种，比较优化的是分治的思想，把一个数组拆分为两个子数组，不妨称为L和R，那么原数组的逆序对数就等于L的逆序对数加上R的逆序对数，再加上一个元素在L中另一个元素在R中构成的逆序对数。可以在分解时独立求出L和R中逆序对数，然后合并时再加上L和R共同构成的逆序对数。中间的过程和归并排序非常类似，时间复杂度可以做到n*log（n）。算法参考代码如下：2016年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）一、术语解释1队列2森林3线性表的链式存储结构4图的遍历5哈希函数的同义词二、单项选择12167的个位数是（）。A2B4C6D82int func(int n)if(n=0)return n;else return(n%7+func(n/7);求该函数执行的时间复杂度（）。AO（logN）BO（N）CO（NlogN）DO（N2）3下列哪个选项的执行时间与规模无关？（）A数据的初始值B问题规模C计算机的主频D操作执行的次数4以下哪个出栈顺序不可能是1 2 3 4 5入栈的序列（）A1 2 3 4 5B3 2 1 4 5C3 4 5 2 1D4 2 5 3 15对数列10,20,30,40,50进行哈希排序，哈希函数为H(i)=i MOD 7，已知装填因子为0.6，处理冲突采用线性探测再散列，在查找不成功的情况下，平均查找长度（）。A16/7B16/9C17/9D18/9三、简答1对于数组1 8 2 3 4 5 6 7进行堆排序，先构造小根堆，然后利用堆求降序排序数组，画图表示过程。2用一次遍历的方法找到单链表的倒数第三个节点，画出图形说明计算过程。3画出图的邻接矩阵，并找出所有的拓扑序列。4证明快速排序算法的时间复杂度是O（NlogN）。5对于长度分别为m和n的两个升序数组，试找出两个数组所有数据的中位数，即第（mn）/2小的数，试用对数复杂度来求解。四、应用编程1在二叉树中用函数int FindMaxLength(NODE*root)，求出二叉树内任意两个结点的最长距离，双亲结点与孩子结点之间的距离为单位距离。2有两个等长升序数组n，请用函数void print_intersection(int a,intb,int n)打印出两个数组的交集。2018年华中科技大学软件学院数据结构与算法分析考研真题及部分参考答案一、名词解释（25分）1递归函数2空间复杂度3满二叉树4装填因子5再哈希法二、选择题（25分）1ABCD入栈，不可能的出栈顺序是（）。AABCDBBACDCDCABDDCBA2下列函数，fun(5)的结果是（）。int fun(int n)if(n1)return0;printf(%d,n);return(1+fun(2*n/3)+fun(n/3);A96421116B9642112123211C5321116D543213堆排序的时间复杂度（）。Alog（n）Bn*log（n）CnDn24一棵树的中序DJGBEHAFIC，先序ABDGJEHCFI，则后序是（）。AJGBHEBIFCABGBDEFIHCACJGDEHBIFCAD都不对5基数排序的时间复杂度和（）无关。A基数的选择B数组的最大元素C数组长度D数组是否排序三、简答题（60分）1有3扇关闭着的门，其中2扇门后面各有一只羊，另一扇门后面有一辆车。参与者：一个游戏者和一个主持人。主持人事先知道各扇门后的物品，而游戏者不知道。游戏目的：游戏者选择到车。游戏过程：游戏者随机选定一扇门；在不打开此扇门的情况下，主持人打开另一扇有羊的门。此时面对剩下2扇门，游戏者有一次更改上次选择的机会。问：（画出判定树）游戏者是否应该改变上次的选择，以使选到车的概率较大？2（1、8、2、3、4、5、6、7）利用数组建成一个小根堆并使用堆排序将其排序成唯一的降序数组。要求画出所有中间过程。312个权值为3、4、6、8、12、15、18、22、25、33、36、58，画出哈夫曼树并设计编码。415,25,36,47,58,69表长11。H(k)=k%11，用二次探测再散列处理冲突，画出散列表。5用算法设计的思想，不全部计算出来求3的96次方的第十位数值。四、算法设计（40分）（请使用类C语言编写）1求二叉树的结点个数，如果根节点为空，则返回0。2打印出非递减数组a与b的升序并集（去除重复元素）。2018年数据结构与算法分析试题部分参考答案一、名词解释（25分）1递归函数对于某一函数f（x），其定义域是集合A，若对于A集合中的某一个值x0，其函数值f（x0）由f（f（x0）决定，那么就称f（x）为递归函数。【解析】2空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S（n）O（f（n）。【解析】3满二叉树也称丰满二叉树，一棵深度为k且有2k1个结点的二叉树。【解析】4装填因子填入表中的元素个数/散列表的长度。【解析】5再哈希法（蛤六）这种方法是同时构造多个不同的哈希函数：Hi=RH1(key)，其中i1，2，k。当哈希地址Hi=RH1(key)发生冲突时，再计算Hi=RH2(key)，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。【解析】二、选择题（25分）1ABCD入栈，不可能的出栈顺序是（）。AABCDBBACDCDCABDDCBAC【答案】2下列函数，fun(5)的结果是（）。int fun(int n)if(n1;四、算法设计（40分）（请使用类C语言编写）1求二叉树的结点个数，如果根节点为空，则返回0。【解析】写明算法的整体思想算法思想：使用后序递归算法遍历该树，如果有结点，则计数(count)+，如果根结点为空，则返回0。编写程序typedef struct Bintreenode int data;struct Bintreenode*right;struct Bintreenode*left;*Bintreenode;int count=0;/count记录拥有两个子女节点的节点个数int Count_Node(Bintreenode*root)/输入：根节点 if(!root)/非空时 Count_Node(root-left);Count_Node(root-right);count+;/计数(count)+/if return count;/Count_Node 进行时间复杂度的分析遍历整棵树。时间复杂度为O（n）。2打印出非递减数组a与b的升序并集（去除重复元素）。【解析】写明算法的整体思想算法思想：用两个指针p，q分别指向a与b的头结点。如果aq的data大于ap的data，记录ap，如果ap与上一打印结点不同，则打印该结点。之后p+。如果aq的data小于ap的data，记录aq，如果aq与上一打印结点不同，则打印该结点。之后q+。如果aq的data等于ap的data，记录aq（ap也行），如果aq与上一打印结点不同，则打印该结点。之后p+，q+。当p或q有一个等于数组的长度，结束循环，打印没有遍历完数组的所有非重复值。*/编写程序void Print_Union(int a,int b)int p=0,q=0;/初始化指针 int flag=Integer.MIN_VALUE;/初始化记录上一打印元素 while(p!=a.length&q!=b.length)/a与b均非空时 if(apaq)/如果aq的data小于ap的data if(aq!=flag)System.out.print(aq+);flag=aq;/记录当前打印元素 q+;continue;/if if(ap0)p=p*2;r=r/2;4先序遍历和后序遍历能否确定一个二叉树，中序遍历先序遍历能否确定一颗二叉树，并分别解释原因（6分）5如何用优先队列实现先进先出队列？实现后的出队与入队操作的时间复杂度是多少？（10分）四、代码题（50分）1在二叉树中求最小值，并分析时间复杂度。2实现邻接链表转化成邻接矩阵，并分析时间复杂度。3有一种数据结构叫做双端队列，支持在队列两端插入删除，在大小为n的数组中实现双端队列相关操作，出入队时间复杂度O（1）。