标题：大连理工大学2008年秋季博士入学考试计算机算法试题
时间：2009-03-16 (5:18 下午)
分类：电脑网络
标签：博士, 考试, 计算机
作者：驽鸟

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个结点的不同的二叉树有多少棵，并证明。
上一篇：[转] 这些短信，你真的懂吗?
下一篇：山东省2009年教师资格考试认定工作通知

返回首页
切换访问：2.0版 | 1.1版