《算法与算法复杂性理论》考题

1、算法与算法复杂性理论试卷2010简答题：（30分，每题5分）证明：n log- （n logn） oii 1如果P!=NP ,那么所有NP完全问题都没有多项式时间解。判断该描述是否正确，并解释理由。简要描述有向图强连通分量的求解算法。一颗不满的二叉树能否与一种最优编码对应？说明理由。（不满的二叉树即存在某节点只有一个孩子）利用指示器随机变量来计算掷-次骰子总和的期望值。已知快速排序算法如下，其中Partitioa数的3-6行称为循环不变式，证明该循环不变式在算法的各个执行时期都是正确的。QuickSort(A,p, r)1if p 1, k=0证明贪心算法总可以产生一个最优解。请给出一组使贪心

2、算法不能产生最优解的硬币单位集合。所给集合应当 包括一分，比保证对任意n都有解。请给出一种O (nk)的算法，能够对任意k种不同单位的硬币集合进行找 换，假设其中一种硬币单位是一分的。基于Random(0,1),给出随机数生成器Random(a,b)的一个实现，使得每次调 用Random(a,b)将返回一个介于a与b之间的整数包括a,b)而且每个整数出 现的机会相等，并给出该实现的复杂度分析。其中Random (0,1以等概率的 方式输出0或者1。假设x和y是n位二进制数，并假设n是3的幂，考虑下述分治算法计算x 与y的乘积:将x，y分别分成3个部分a，b，c，和d，e,f,每部分包含n/3

3、位，使得：x a 2 2n/3 b2n/3 C,y d22n/3 e2n/3 fxy ad 24n/3 (ae bd)2n (af be cd )2 2 n /3(bf ce)2n/3 cfe),r be cf, r ?为了提高算法效率，我们设计6个中间值来完成上述计算，rad ,r (ab)(dr (a c)(df ),r例如：当n是2的幂时，可用如下方法提高xy的效率x a2n/2 b, y c2n/2 dxy ac 2n (adbc )2n/2 bdac 2n (a b)(c d) ac bd 2n/2bd给出r 6的表达式，并给出如何用这些中间值来计算xy。给出上述分治算法时间复杂度的

4、递归表达式并用Master Theorem求解。在动态表中，假设当某个表的装载因子降至1/3以下时，将其大小乘以2/3 来进行收缩。利用势函数(T )|2匚num T sizeT 来证明这种策略的TABLE-DELETE操作的平摊代价由一个常数从上方限界。用分支定界法求解下面距离矩阵所给出的TSP问题: TOC o 1-5 h z 12257891056793412814315259如果一个序列首先单调递增，然后再单调递减，那么成这个序列是双调的， 例如序列1,4,6,8,3,-2就是一个双调序列。给定长度为n的序列A，请设 计出高效的寻找A中最长双调子序列的算法。输出长度和序列，如果有多个 任意输出一个即可。（注：单调序列作为特例，也可以被认为是双调序列）。 首先：请保证算法的正确，性，不正确的算法无法得到分数。然后，时间复杂 度为O（n2）空间复杂度为O（n）的算法将得到全部分数，其他算法视情况给 分。证明：哈密顿路径问题是NP完全的。（提示：从已知是NPC的哈密顿回路问