驽鸟公寓

1、给出在最坏情况下只需3n/2－2次关键字比较的同时找n（n为偶数）个元素最大最小值的算法，并证明该问题在最坏情况下至少需要3n/2－2次关键字比较。
2、给出对n个元素进行排序的好的算法，并说明你的算法是好的理由。
3、给出在最坏情况下只需40n/3次关键字比较的同时找n个元素中间元的算法，并证明该问题在最坏情况下至多需要40n/3次关键字比较。
4、给出由一棵空红黑树开始，依次插入关键字的构造红黑树的算法，同时给出依次插入10，7，5，8，4，2，9，1，3，6所得到的10棵红黑树。（20分）
5、给出kruskal算法描述与程序，同时给出算法的时间复杂度与算法正确性的证明。（15分）
6、给出dijkstra算法描述与程序，同时给出算法的时间复杂度与算法正确性的证明。（15分）
7、矩阵A，B，C，D的维数为15×2，2×10，10×5，5×3，给出最优矩阵乘法顺序的cost阵与root阵及最优矩阵乘法顺序。
8、N个结点的不同的二叉树有多少棵，并证明。

博士, 考试, 计算机

本文发表 于 星期一, 三月 16th, 2009 ，5:18 下午 ，并归档于 电脑网络。 您可以通过 RSS 2.0 feed跟踪本文的讨论。 您可以 发布留言，或者从您的站点发送 trackback 。