当前位置: 首页 > 电脑网络 > 正文

大连理工大学2008年秋季博士入学考试计算机算法试题

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个结点的不同的二叉树有多少棵,并证明。

本文固定链接: http://www.nuniao.com/dr-dalian-university-fall-2008-entrance-examination-computer-algorithm-question.html | 驽鸟公寓

该日志由 驽鸟 于2009年03月16日发表在 电脑网络 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 大连理工大学2008年秋季博士入学考试计算机算法试题 | 驽鸟公寓
关键字: , ,

大连理工大学2008年秋季博士入学考试计算机算法试题:等您坐沙发呢!

发表评论


快捷键:Ctrl+Enter