算法与算法复杂性理论试卷
2010
简答题：(30分，每题5分)
1.证明：
1log(log)
n i n
n n i
==Θ
∑。
2.如果P!=NP，那么所有NP完全问题都没有多项式时间解。
判断该描述是否正
确，并解释理由。
3.简要描述有向图强连通分量的求解算法。
4.一颗不满的二叉树能否与一种最优编码对应？说明理由。
(不满的二叉树即
存在某节点只有一个孩子)
5.利用指示器随机变量来计算掷n次骰子总和的期望值。
6.已知快速排序算法如下，其中Partition函数的3～6行称为循环不变式，证
计算分析题：（70分，每题10分）
1.找换硬币问题：考虑使用最少的硬币数来找n分钱的问题，假设每个硬币的
值都是整数。
a)请给出一个贪心算法，使得所换硬币包括一角、五分、两角五分和一分
的。
证明所给算法能产生最优解。
b)假设可换的硬币单位是c的幂，也就是c0, c1, … , c k, 其中整数c>1, k>=1。
证明贪心算法总可以产生一个最优解。
c) 请给出一组使贪心算法不能产生最优解的硬币单位集合。
所给集合应当
包括一分，比保证对任意n 都有解。
d) 请给出一种O(nk)的算法，能够对任意k 种不同单位的硬币集合进行找
换，假设其中一种硬币单位是一分的。
2. 基于Random(0,1), 给出随机数生成器Random(a,b)的一个实现, 使得每次调用Random(a,b)将返回一个介于a 与b 之间的整数(包括a,b)，而且每个整数出现的机会相等，并给出该实现的复杂度分析。
其中Random (0,1)以等概率的方式输出0或者1。
3. 假设x 和 y 是n 位二进制数，并假设n 是3的幂，考虑下述分治算法计算x 与y 的乘积:将x ，y 分别分成3个部分a ，b ，c ，和d ，e,f,每部分包含n/3位，使得:
2/3/32/3/34/32/3
/322,222()2()2()2n n n n n n n n x a b c y d e f
xy ad ae bd af be cd bf ce cf
=++=++=++++++++
为了提高算法效率，我们设计6个中间值来完成上述计算， 123456,()(),()(),,?
r ad r a b d e r be
r a c d f r cf r ==++==++== 例如：当n 是2的幂时，可用如下方法提高xy 的效率
/2/2/2/22,22()22[()()]2n n n n n n x a b y c d
xy ac ad bc bd
ac a b c d ac bd bd
=+=+=+++=+++--+ a) 给出r 6的表达式，并给出如何用这些中间值来计算xy 。
b) 给出上述分治算法时间复杂度的递归表达式并用Master Theorem 求解。
4. 在动态表中，假设当某个表的装载因子降至1/3以下时，将其大小乘以2/3来进行收缩。
利用势函数 ()|2[][]|T num T size T Φ=-
来证明这种策略的TABLE-DELETE 操作的平摊代价由一个常数从上方限界。
5. 用分支定界法求解下面距离矩阵所给出的TSP 问题：
12257891056793412814315259∞⎡⎤⎢⎥∞⎢⎥⎢⎥∞⎢⎥∞⎢⎥⎢⎥∞⎣⎦
6. 如果一个序列首先单调递增，然后再单调递减，那么成这个序列是双调的，例如序列<1,4,6,8,3,-2>就是一个双调序列。
给定长度为n 的序列A ，请设计出高效的寻找A 中最长双调子序列的算法。
输出长度和序列，如果有多个任意输出一个即可。
(注：单调序列作为特例，也可以被认为是双调序列)。
首先：请保证算法的正确性，不正确的算法无法得到分数。
然后，时间复杂度为O(n^2)空间复杂度为O(n)的算法将得到全部分数，其他算法视情况给分。
7. 证明：哈密顿路径问题是NP 完全的。
（提示：从已知是NPC 的哈密顿回路问题归约，注意证明的严谨性）
哈密尔顿路径问题：已知图G=（V ，E ）,图G 中是否存在一条道路(始/终点任意)，到达 G 中所有的点一次且仅到一次。
