2015年软件工程数据结构852真题

reyonelai · 发表于 2014-12-28 19:36

本帖最后由 reyonelai 于 2014-12-28 19:41 编辑

去年我就是没找到原题，而且考这个专业的好像也不多。不过，网上的历年真题还是挺有用的。所以，我在刚考完就把题目记下来了。虽然自己肯定是没有希望进入复试了，但是希望下一届，甚至下下届的师弟师妹能够得到帮助。

一、选择题  2*15
很简单，基本知识。比如，时间复杂度为O(nlogn)的算法是哪种？最后一题是，问m路b+树是一种什么树。

二、简答题  4*5
1-当数据有序时，快速排序效率低，怎么改进算法。
2-写出一个入栈顺序的所有出栈可能序列。和一个入队顺序的所有出队可能序列。
3-构造一个小顶堆，其中有一个重复关键字，画出过程图。
4-还有一题记不清了（抱歉）

三、算法和应用 5*10
1-一个带权的图G，找出顶点1到其他顶点的最短路径。说明如何找，顶点序列是多少？最短路径为？
2-根据给定序列，构造一棵三路最优归并树。
3-哈希表存储数据，用线性探测法解决冲突。求查找成功和失败的平均查找路径。
4-直接插入，希尔，快速，归并，堆，基数排序哪些稳定，哪些不稳定？不稳定的给出实例。
5-已知二叉树的任意两种遍历序列，能否还原一棵无二义性的二叉树？什么时候可以？什么时候不能？如果可以，给出还原方法。

四、编程题  15+15+20
1-（这是2012年原题）用孩子兄弟结构，写一个求树的叶子个数的算法。
2-奇偶变换排序，先对i为奇数的元素排序，然后对i为偶数的元素排序。写一个排序算法。
3-用邻接表的结构写一个判断图是否存在回路的算法。

以上就是整张试卷的内容了。总的来说，都是很基础的东西，希望还在备战考研的同学多多看书，把严蔚敏那本书看熟了就行了。然后就是重点抓一下真题的编程算法。妥妥的。太遗憾我考研的时候，没有别人发指导的帖子导致走了很多弯路。希望大家从这里得到启发。以上。