PDF《2018 年秋季学期《算法基础》期末试题》

2018 年秋季学期《算法基础》期末试题 Edited by Lyncien 2018.

12.28

一、 简答题 4*5% (1) 写出快速排序和归并排序的最坏时间复杂度,说明为什么实际应用更多使 用快速排序而不是归并排序 (2) 对于 n 个元素的二叉堆和二项堆,分别对于那个操作更具有时间优势? (3) 说明动态规划解题的一般过程/步骤 (4) MR 算法对于一般的伪素数检测算法作了哪些改进措施?

二、 计算题 4*10% 1. (1)T(n) = T(2n/3) +

1 ,求解 T(n) (2)求解线性同余方程组: X≡4(mod 5), X≡5(mod 11) 2. 用动态规划方法计算下面多段图 s 到t的最短路径,给出计算过程 3. 0-1 背包问题中,如果所有物品按价值递增的顺序和按重量递减的顺序是一样 的,则可以贪心地选择价值率最高的物品,证明贪心解就是最优解. 4. (1)Kruskal 算法的贪心策略是什么?用该算法求下图的最小生成树. (2)该算法需要合并操作,应该用我们学过的哪种数据结构来实现?

三、 设计题 15% + 15% + 10% 1. 写出递归版本的二分查找,在A[1..n]上查找 x,不存在返回 0,并分析时间复 杂度. 2. A[1..n]为数组, 其中 1