大连理工大学2008年秋季博士入学考试计算机算法试题
Mar162009
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个结点的不同的二叉树有多少棵,并证明。