哇,我们都是热爱算法的好孩子。

一、判断题

  1. 一个正确的算法,对于每个合法输入,都会在有限的时间内输出一个满足要求的结果。

    正确

  2. NP 完全问题比其他所有 NP 问题都要难。

    错误?所有 NP 问题均能转化为 NPC 问题,准确说应该是 NPC 问题至少也会和其他 NP 问题一样难,可能更难(NPC是NP的子集)

  3. 回溯法用深度优先法或广度优先法搜索状态空间树。

    错误。仅 DFS

  4. 在动态规划中,各个阶段所确定的策略就构成一个策略序列,通常称为一个决策。

    正确

  5. 𝑃类和𝑁𝑃类问题的关系用𝑃 ⊂ 𝑁𝑃来表示是错误的。

    错误。P类是NP类的子集(P类问题的多项式算法作为certificate checking algorithm不需要接受certificate)

  6. 若近似算法 A 求解某极小化问题一实例的解为$s_a$,且已知该问题的最优解为$s_a/3$ ,则该近似算法的性能比为 3。

    错误。性能比是精度的上确界

  7. 通常来说,算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。

    正确。好像确实是这样.

  8. 若 P2 多项式时间转化为(polynomial transforms to) P1,则 P2 至少与 P1 一样难。

    错误。P2 至少不会比 P1 更难( P2 可能会比 P1 简单)

  9. 快速排序算法的平均时间复杂度是O(𝑛 log 𝑛),使用随机化快速排序算法可以将平均时间复杂度降得更低。

    错误。并不能,随机快排和普通快排平均情况性能一样(最坏复杂度也一样),而且比较排序的复杂度有下界。

  10. 基于比较的寻找数组A[1, … , 𝑛]中最大元素的问题下界是Ω(𝑛/3)。

    错误。这么神奇的吗,输入就已经n了。

  11. O(𝑓(𝑛)) +O(𝑔(𝑛)) =O(min{𝑓(𝑛),𝑔(𝑛)})

    错误。应该是max, 比如$f(n)=n^3$, $g(n)=n$, 加起来应该是$n^3$

  12. 若𝑓(𝑛) =Ω(𝑔(𝑛)) ,𝑔(𝑛) =Ω(h(𝑛)) ,则𝑓(𝑛) =Ω(h(𝑛))

    正确。没毛病

  13. 若𝑓(𝑛) =O(𝑔(𝑛) ,则𝑔(𝑛) =Ω(𝑓(𝑛))

    正确。当然了

  14. 贪婪技术所做的每一步选择所产生的部分解,不一定是可行性的。

    错误。一定得是可行的。贪心的每一步: 可行的(满足问题约束),局部最优(当前状态可选项中选择局部最优选项),不可取消(选择后无法撤销回退)

  15. LasVegas算法只要给出解就是正确的。

    正确。这是Las Vegas算法的定义

  16. 一个完全多项式近似方案是一个近似方案 $ \{A_{\epsilon}\} $ ,其中每一个算法 $A_{\epsilon}$ 在输入实例𝐼的规模的多项式时间内运行。

    错误。定义里有,FPAS是I规模和$\frac{1}{\epsilon}$两者多项式时间内运行。

二、问答题

  1. 二叉查找树属于 减治 变治策略的三个变种中的哪一个的应用?什么情况下二叉查找树表现 出最差的效率?此时的查找和插入算法的复杂性如何?

    改变表现。 插入元素存在顺序,引起二叉查找树退化为长链。最坏、平均均为 O(n)

  2. 何谓为多项式算法?如何将一 Monte Carlo 算法转化为 Las Vegas 算法?

    时间复杂度是问题规模n的多项式表达式。利用Monte Carlo算法得到一个结果后对该结果进行正确性验证,正确则算法返回结果,否则没有结果。

  3. 构造 AVL 树和 2-3 数的主要目的是什么?它们各自有什么样的查找和插入的效率?

    维持树的平衡性,使得问题规模为n时,树高度h大约为log(n),降低排序树的最坏查找、插入、删除的时间复杂度。查找,插入均为O(log(n))。

  4. 写出 0/1 背包问题的一个多项式等价(Polynomial Equivalent)的判定问题,并说明为什么它们是多项式等价的。

    01背包问题P0:给定集合N={0, 1, 2, …},每个元素的重量w和价值v。求V,其中$S\subseteq N$,$\sum_{i\in S}{w(i)} \le W$, 且 $ \sum_{i{\in}S} = V $
    等价判定问题P:给定集合N={0, 1, 2, …},每个元素的重量w和价值v。问是否存在N的子集S,使得子集中所有元素重量和小于等于W,价值和大于等于V。
    对于问题P,以及输入N, w, v, W, V:构造问题P0,输入为N, w, v, W,求出P0的最大价值和V0,与问题P的输入V进行比较即可判定是否存在,即 P 规约到 P0 。
    对于问题P0,以及输入N, w, v, W。在0和所有元素的价值总和Vmax之间进行二分,每次构造问题P,输入为N, w, v, W, Vi。即可求得P0的解。即 P0 规约到 P。

  5. 下面问题是否属于 NP 问题?为什么?
    问题表述:给定图𝐺 = (𝑁, 𝐴)中的两个点𝑝、𝑞,整数𝑐和𝑡,图𝐺中每条边的长度𝑐_ij及便
    利这条边的时间𝑡_ij,问图𝐺中是否存在一条由𝑝到𝑞的路径,使得其长度大于𝑐,且遍历时间 小于𝑡?

    把集合划分问题多项式transform到该问题。对于一个n个元素的集合,每个元素的值为s(i)。设所有元素的和为2K。
    构造一个层次图,图中p到q必须依次经过n-1个点:p1, …, pn-1,p到p1,p1到p2,…, pn-2到pn-1,pn-1到q,各有2条边,一条的长度为s(i),时间为s(i),另一条时间为0,长度为0。并设定c=K-1,t=K+1。

三、分治题

  1. 写出一个求解下列问题的分治算法,推导其时间复杂性并与蛮力法相比较。 给定互不相等的n个数的一个序列𝑎!,𝑎!,…,𝑎!,若其中某两个数𝑎!和𝑎!的关系为:𝑎! >𝑎! 且𝑖 < 𝑗,则称𝑎!和𝑎!是逆序的。要求计算该序列中的逆序个数,即具有逆序关系的元素 对的总数目。

    归并排序,在合并两个数组的时候进行计数。总逆序数对数等于左半边+右半边+左右之间构成的。(离散化+树状数组也行,不过这里是分治了)
    T(n) = 2T(n/2) + O(n)。由 master theorem ,T(n) = O(nlog(n))

  2. A[1, … , 𝑛]为一个整数序列,A中的整数𝑎如果在A中出现次数多余 𝑛/2 ,那么𝑎称为多数 元素。例如,在序列1,3,2,3,3,4,3中 3 是多数元素,因为出现了 4 次,大于 7/2 。求 A 的多数元素问题的蛮力算法复杂性如何?设计一个具有变治思想的算法,提高蛮力算法 的效率,写出伪代码并分析其事件复杂性。

    先排序,然后线性扫描。复杂度O(nlogn) + O(n) = O(nlogn)

四、动态规划题

基本都是比较简单的二维dp。

五、分支限界

  • 用分支定界法求解以下问题: 某部门欲建立联通分布于五个区的共 50 个站点的有线通讯网络,每两个站点之间的线路敷设费用由对成矩阵 C 给出,任意两站点之间敷设线路需建设的地井数目由对称矩 阵U给出。
    设计一线路敷设总费用为最小的无环网络,使得徐建设的总地井数目不超过 UMAX, 且需跨区敷设的线路总数目不超过 DMAX(个站点所属的区由向量 D 给出)。
    • 说明你是如何构造搜索树的。(要求是二叉搜索树)
    • 说明算法遍历搜索树的原则。(何时以及如何前进、分支、回溯、剪枝等等)
    • 你设计的分支定界算法的“界”是什么,他为什么是正确的和有效的?
    • 写出伪代码。

二叉搜索树还是蛮蛋疼的,一般也就只能是某边是否选之类得了。
doge