重庆大学2013算法考卷B.docx

.
精品文档
重庆大学《算法分析与设计》课程试卷
2012~2aO5 学年第二学期
开课学院：计算机学院 课程号：18016435 考试日期：
题号
A
B
C
D
E
F
G
H
I
J
总 分
得分: .
精品文档
重庆大学《算法分析与设计》课程试卷
2012~2aO5 学年第二学期
开课学院：计算机学院 课程号：18016435 考试日期：
题号
A
B
C
D
E
F
G
H
I
J
总 分
得分
考试方式:
广开卷倩闭卷广其他
考试时间：120分钟
注：答案填写在试题页后的答案纸上，用中文解答。一些重要的关键词句后附有
2. What is the worst time complexity （最坏时间复杂度）to sort this array with quicksort?
3. During each iteration, if we assume that the initial array is split （分割）
accord ing to the ration （比例）1:9, the n write the recurre nee of this situati on,
and prove that the asymptotic time complexity will remain 9（n log n） with
substitution .
中文解释。
A. （15 poi nts）
Use mathematical in duct ion （数学归纳法）to show that whe n n =
2k with
k > 0
the solution of the recurrence equation
（递归等式）
T （n） = T（ n/2） + n, where T（1）=3
is T（ n）=
2n+1.
B. （15
poi nts）
Quicksort （快速排序）is a very interesting
algorithm. Given an
disordered array with n eleme nts,
1. What is the best time complexity （最好时间复杂度）to sort this array with quicksort?
C. （25 points） Suppose that in a 0-1 knapsack problem （0-1 背包问题），the
order of the items when sorted by increasing weight （按重量升序排序）is the same
as their order when sorted by decreasing value （按价值降序排序）.Give an efficient
algorithm to find an optimal soluti