15.082模拟期中考试 模拟闭卷期中考试 学生允许使用两页纸，只能在一面上写。 这次模拟期中考试比真正的期中考试长大约20分钟。 注释：重点是以下方面： 1.理解算法和能再现关键步骤 2.理解运行时间分析的关键步骤 3.理解算法理论方面和能舒服地使用这些理论方面 4.能够把问题建模为最短路径或最大流或最小切割问题 分数合计只有90分。我删除了关于预流推进的10分问题，因为这不在 考试覆盖范围之内
15.082 模拟期中考试 模拟闭卷期中考试 学生允许使用两页纸，只能在一面上写。 这次模拟期中考试比真正的期中考试长大约 20 分钟。 注释: 重点是以下方面： 1. 理解算法和能再现关键步骤 2. 理解运行时间分析的关键步骤 3. 理解算法理论方面和能舒服地使用这些理论方面 4. 能够把问题建模为最短路径或最大流或最小切割问题 分数合计只有 90 分。我删除了关于预流推进的10分问题，因为这不在 考试覆盖范围之内
1.(10分)请为如下网络提供一广度优先搜索树和一深度优先搜索树。 (搜索算法保存了前驱，且这些前驱形成了树) 6 ⑤ 2.(10分)表示在下面描述的流的流分解。（照常，任何在流分解中的路 径应该从供应结点指向需求结点。) 5 2 3 2 2 3 7 ⑤ 3.(10分)通过拓扑地排列结点标号顺序确定以下图是无圈的，否则判定 一个有向圈。（您需要把图拷贝到您的蓝皮书上。） a c
1. (10 分) 请为如下网络提供一广度优先搜索树和一深度优先搜索树。 (搜索算法保存了前驱，且这些前驱形成了树.) 2. (10 分) 表示在下面描述的流的流分解。(照常，任何在流分解中的路 径应该从供应结点指向需求结点。) 3. (10分) 通过拓扑地排列结点标号顺序确定以下图是无圈的，否则判定 一个有向圈。(您需要把图拷贝到您的蓝皮书上。)
4.(10分)这是R-堆的某次迭代的桶。算法又被称为发现最小(find-min) 运算的部分。当发现最小计算结束的时候，也就是当结点2从桶中 删除且变成永久性的后，桶的状态是什么？（桶的范围是什么？在 这些桶中的结点是什么？) node 1 2 3 4 5 6 d(node) 0 69 79 73 122 2-3 4-7 8-15 16-31 32-63 64-127 5.6 5.(10分，每部分2.5分)。在以下的例子中，您将被提供函数f和函数g。您应 该说明是否f(n)=O(gn)。 a.f(n)=10n;g(n)=n -n. b.fn)=n如果n是奇数，0如果n是偶数：g(n)=n如果n是偶数，0如 果n是奇数。 1000 c.f(n)=50n+7 (n) d.f(n)=(log n);g(n)=n 6.(10分)令fn,m,k)=nk+knm.令g(n,m)=min{fn,m,k):k>0} 说明g(n,m)=⊙(nm),也就是g(n,m)=O(nm),且nm=O(g(n,m) 提示：不要使用微分判定g(n,m)。(相信我们，微分将会太浪费时间。)宁可， 令k*(n,m)是k的唯一值，且有nk=knm。令g'(n,m)=fn,m,k*(n,m)。然 后说明g(n,m)≤g'n,m)≤2gn,m) 注释：有时候可能开发一算法，其运行时间依赖于参数k。这个问题说明不依 赖于微分但仅通过设置项相等可以判定参数k的最佳选择
4. (10分) 这是R-堆的某次迭代的桶。算法又被称为发现最小（find-min） 运算的部分。当发现最小计算结束的时候，也就是当结点 2 从桶中 删除且变成永久性的后，桶的状态是什么？ (桶的范围是什么？在 这些桶中的结点是什么？) 5. (10分, 每部分 2.5 分)。 在以下的例子中，您将被提供函数 f 和函数 g 。您应 该说明是否f(n) = O(g(n))。 a. f(n) = 10n; g(n) = n 2 – n. b. f(n) = n 如果 n 是奇数， 0 如果 n 是偶数；g(n) = n 如果 n 是偶数，0 如 果 n 是奇数。 c. f(n) = 50n + 2 1000 ; g(n) = n-1; d. f(n) = (log n) 100 ; g(n) = n .01 ; 6. (10 分) 令 f(n,m,k) = n 3 /k + knm. 令 g(n,m) = min { f(n,m,k) : k > 0 }. 说明 g(n,m) = Θ( n 2 m .5 )，也就是g(n,m) = O( n 2 m .5 )， 且 n 2 m .5 = O(g(n,m))。 提示：不要使用微分判定g(n,m)。 (相信我们，微分将会太浪费时间。) 宁可， 令 k*(n,m) 是 k 的唯一值，且有 n 3 /k = knm。令g’(n,m) = f(n,m,k*(n,m))。然 后说明g(n,m) ≤ g’(n,m) ≤ 2 g(n,m)。 注释：有时候可能开发一算法，其运行时间依赖于参数 k 。这个问题说明不依 赖于微分但仅通过设置项相等可以判定参数 k 的最佳选择
7.(10分)文档处理程序TX使用最优化例程把段落分解成几行，以便当行左和 右调整的时候，段落的外观将会最美观。假设段落包含个单词，且每个单词分配 一序列号。令c.表示行的美观性，如果它开始于词i,且结束于词j-1。TeX使用 公式计算每个c,。给出c's说明为了最大化所有行的总美观性为最短路径问题， 如何公式化分解段落到几条文本行的问题。确保解释最短路径和最美观段落的联系。 8.(10分，每部分5分) a.假设在从源到漏的最大流是mlogn,.且所有的容量是整数。使用Ford-Fulkerson.增广 路径算法寻找最大流需要用多长时间？简短证明您的回答。 b.假设，在a部分中，从源到漏的最大流是mlogn,且所有的容量是整数。使用最 短增广路径算法用多长时间发现最大流？简短证明您的回答 9.(10分)假设在网络G中的最小s-t切割有2000容量和20条弧。假设对G中 的每条弧增加10个单位的容量，创建变换网络G。对于变换网络来说，以 下哪个是真的： 1 G的最小切割的容量恰好是2200。 G’的最小切割的容量至少是2200，且可能更多。 ii. G的最小切割的容量至多是2200，且可能更少
7. (10分) 文档处理程序 TeX 使用最优化例程把段落分解成几行，以便当行左 和 右调整的时候，段落的外观将会最美观。假设段落包含 n 个单词，且每个单词分配 一序列号。令c ij 表示行的美观性，如果它开始于词 i ，且结束于词j-1。 TeX 使用 公式计算每个c ij 。 给出 c ij ’s 说明为了最大化所有行的总美观性为最短路径问题， 如何公式化分解段落到几条文本行的问题。确保解释最短路径和最美观段落的联系。 8. (10 分, 每部分 5 分) a.假设在从源到漏的最大流是mlogn，且所有的容量是整数。使用Ford-Fulkerson增广 路径算法寻找最大流需要用多长时间？简短证明您的回答。 b.假设，在 a 部分中，从源到漏的最大流是 mlogn，且所有的容量是整数。使用最 短增广路径算法用多长时间发现最大流？简短证明您的回答 9. (10 分) 假设在网络 G 中的最小 s-t 切割有 2000 容量和20 条弧。假设对G中 的每条弧增加 10 个单位的容量，创建变换网络G'。 对于变换网络来说，以 下哪个是真的： i. G’ 的最小切割的容量恰好是2200。 ii. G’ 的最小切割的容量至少是2200，且可能更多。 iii. G’ 的最小切割的容量至多是2200，且可能更少