复旦2011在职研究生计算机技术数据结构考试

2011-11-19星期六阴有小雨邯郸路220号

上午8：30~11:00

总分：150

试题一，5道选择题，10分，不难，但是第五道竟然出现C和D答案是一样，堆排序，后来有个老师来说明把D改成归并排序，原意是选择一种稳定并且时间复杂度为O(n)的算法；

试题二，讲解画图，每道5分，40分

1，KMP算法

2，霍夫曼编码

3，AVL

4，快速排序

5，普利姆算法

6，笛卡尔积算法

7，最小B树画法

8，线性二次哈希表画法

试题三，编程填空，10分

讲二叉搜索树删除有2个节点的情况

试题四，编程10+10+20,40分

1，数组奇数排在前面偶数排在后面，要求时间复杂度O(n)

2，二叉链表打印正整数，并且节点数据要在子节点之后

3，邻接矩阵无向图的广度优先搜索