1、第 3次作业 一、填空题（本大题共 30 分，共 10 小题，每小题 3 分） 1. 矩阵连乘问题的算法可由（ ）设计实现。 2. 算法的时间复杂度随着问题规模 n的增大而 _ 。 3. 一个 30行 20列的矩阵可与一个 _行 75列的矩阵相乘。 4. Huffmann算法是一种： _ 。 5. 下列关于算法的说法正确的是 _ . (填上正确的序号 ) 某算法可以无止境地运算下去 一个问题的算法步骤不能超过 1万次 完成一件事情的算法有且只有一种 设 计算法要本着简单方便可操作的原则 6. 有如下递归过程： void print(int w) int i; if(w!=0) print(w-
2、1); for(i=1;i (3,5),(1,9) - (1,3,5,9) 快速排序： (5,3,1,9)-(5,3,1),(9)-(1),(3,5),(9)-(1),(3),(5),(9) 解题方案： 评分标准： 5. 参考答案： 假定 T(n) c 1 n log n 和 T(n) c 2 n log n 对于任何 n n0 都成立。 通过归纳法证明： P_2697166C16DC92CBFB359D9A4F3AA542 和 P_5CF2942503B47F3A67E3FA959B3E4312 (1) 证明 P_C7CB81D5C946C1DEA98D445A210A2F0C 当 n n0时， T(n) c 1nlog n 所以 (c1 - d)n 0 当 c1 d 时， T(n) = O(n log n) 成立 。 (2) 证明 P_5CF2942503B47F3A67E3FA959B3E4312 P_33D7D1EB0F31D0A6DD8058FD7A5A4714 当 n n0时， T(n) c 2nlog n 所以 (c2 - d)n 0 当 0c2 d ， T(n) = (n log n) 成立。 解题方案： 评分标准： P_5B6650A354EEC5B38EC3132EEE9F4E67
