2014年华中科技大学软件学院数据结构与算法分析考研真题（回忆版）及部分参考答案
一、填空题：
1．写出数据结构的四种基本逻辑结构。

2．写出算法的四种特性。

3．一个栈中有六个数字，要求对其进行重新排序，求堆栈的最小容量。

4．求出一串数字的非平凡子串个数。

5．求一平衡二叉树的成功查找长度和不成功查找长度。

…
二、选择题：（略）
三、分析题：
1．给出一个算法过程，要求列出它的开销公式并解出开销函数。

2．根据题意画出Huffman前缀码树并求出编码长度。

3．该题关于KRUSKAL（V，E，w）的最小生成树算法，由给出的具体算法写出其中元素A的变化过程，并求出最小生成树的权。

4．由题中给出的网络流图求剩余流图，在图中标出最小切割，解出S→t的最大网络流。

5．给出一个图，从a开始深度优先搜索，算出每个节点发现和结束的时刻d/f，根据搜索结果标出图上边的类型。

四、算法题：
1．
根据最短路径延伸算法给出递归表达式，将全成对最短路径填写到题目中的4×4表格中，并写出表格中某一阴影指定位置的路径。

2．证明：A∪（u，v）是图G最小生成树的子集。

3．权重函数f，动态划归，写递推式，用伪码描述算法。

2014年数据结构与算法分析试题部分参考答案
一、填空题：
1．
【解析】集合，线性结构，树形结构，图状结构或网状结构（教材p5）。

2．
【解析】有穷性，确定性，可行性，输入，输出。

任选4个。

3．
【解析】题目应该是有问题，只有一个栈的话，没法排序啊，弹出来的元素没地方保存。

4．
【解析】题目想说的可能是，给出一个字符串S，求出其互异非平凡子串（非空且不同于S）的个数。

那么如果S中的字符各不相同，且长度为n的话，那么答案是n*n/2＋n/2－1。

5．
【解析】大概跟有序数组的二分查找时的成功长度/不成功长度的算法差不多吧。

三、分析题
1．
【解析】略，估计会用到主定理。

2．
【解析】霍夫曼树的构建是基础了，11年的试卷就有一题。

3．
【解析】课本p175。

4．
【解析】算法导论p396-430，第26章——最大流。