2019年-算法设计与分析-考试题拟1

【算法设计与分析考试题拟1】 一、判断题 1. 正确。在背包问题中，当数值为长整型时，动态规划算法能在多项式时间内解决，因为问题的规模不会因为数值的大小而增加。 2. 正确。NP问题指的是能在非确定性多项式时间内验证解的问题，至今尚未找到对所有NP问题的多项式时间求解算法。 3. 正确。线性规划可以通过单纯形法等方法在多项式时间内求解，但整数规划，特别是其中的0-1整数规划，是NP-hard问题，难以在多项式时间内解决。 4. 错误。找到哈密尔顿圈是NP-complete问题，而判定是否存在哈密尔顿圈仅是NP问题，两者难度不同。 5. 正确。网络的最大流等于其最小割集的容量，这是最大流-最小割定理。 6. 错误。找不到S到T的满流路径并不意味着已找到最大流，可能还有提高流的空间。 7. 正确。反例只能证明算法无法达到某个近似比率，但不能证明它具有特定的近似比率。 8. 错误。若A问题有多项式算法，不能推出所有NP问题都有多项式算法，A可能是NPC问题。 9. 正确。询问一个数是否为合数是NP问题，而判断素数问题可通过多项式时间算法解决（如AKS素数检验）。 10. 错误。判断哈密尔顿圈的存在性是NP问题，但其否定不是显然的NP问题，可能属于P。 二、计算题和简答题 1. 有奇数个顶点的二分图不存在哈密尔顿圈，因为哈密尔顿圈必须包含图中所有顶点，且每个顶点只能访问一次。在二分图中，如果存在哈密尔顿圈，那么必然有奇数个顶点在圈中，这违反了二分图的性质。 2. 添加s和t节点的方法可以确保每对(s_i, t_i)之间至少有一个路径，通过最大流算法求s到t的最大流即为所求。 3. 可满足问题（SAT）的真赋值取决于具体命题，需查看命题逻辑表达式。 4. 需要具体有向图来计算最长路径。 5. 权重最大独立集问题，可通过贪心或回溯算法解决。 6. 递归关系式的解通常涉及归纳和数学归纳法。 三、渐进增长率排序：先分析函数复杂度，然后根据大O符号的定义进行排序。 四、定价算法求解带权重的点覆盖问题的2-近似证明：通过分析算法过程，展示每次删除的节点至少能减少两倍的权重，从而得出结论。 五、证明独立集问题是NP完全的：可以构造3-SAT问题的图模型，证明3-SAT是NPC，然后转换回独立集问题。 六、求最小割，需要逐步减小割集的容量并更新割，直至找到最小割。 七、图二着色问题属于P，因为可以用回溯或染色算法在多项式时间内找到解决方案。 以上是针对考试题的解析，涵盖了动态规划、图论、NP问题、算法近似率等相关知识点。