《算法原理》(2013秋)试题库

《算法原理》（2013秋）试题库
(注：按学号排序，答案仅供参考，可能有误 )
简答题
1 孙炜程动态规划和贪心算法的异同贪心算法和动态规划算法都要求问题具有最有子结构性质，这是两类算法的一个共同点动态规划算法通常以自底向上方法解各个子问题，而贪心算法则通常以自顶向下方法进行，以迭方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。 2 吕源皓问题：请叙述动态规划算法与贪心算法的异同，并说明什么是最优子结构。
答：相同点：两者都需要问题具有最优子结构性质。不同点：贪心算法的每一步贪心决策都无法改变，每一步的最优解一定包含上一步的最优解。动态规划算法的全局最优解中一定包含某一个局部最优解，但不一定包含前一个局部最优解。最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。动态规划保存递归时的结果，因而不会在同样的问题时花费时间。 3 李敏请清楚的二分图。答案：二分图又称作二部图，是图论中的一种特殊模型。设 G=(V,E)是一个无向图，如果顶点 V 可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i in A,j in B)，则称图 G 为一个二分图。
4 问题：任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。那么一个问题可以使用动态规划算法需要满足什么条件。答案：1、最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 2、无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。 3、子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。
5 凌云昊问：在无向图的深度优先搜索中，边被分为哪几类？请根据 edge（u，v）给出定义答： type edge(u,v) tree [u [v ]v ]u back [v [u ]u ]v forward [u [v ]v ]u cross [v ]v [u ]u 6 徐赟佳给定一个无向图 G（V,E），给出一个算法，在 O（V）时间内找出是否有一条回路，时间独立于|E|
：用 DFS，如果有回边，就有回路。
7 陈志超以比较为基础的排序算法的时间下界是多少？基数排序的时间复杂度是什么？这个下界适用于基数排序吗？为什么？答案：基于比较的排序算法的时间下界为 Ω(nlogn)。基数排序的时间复杂度为 θ(kn)，其中 k 为元素的位数，n 为元素个数。这个下界不适用于基数排序，因为基数排序是各位数之间的比较，并不是基于元素之间比较的排序，所以该下界不适用。 8 吴强强 What's the time complexity of f (n) where f (n) = 2f (n/2) + n*n(for n >= 2; f (1) = 1) __________(express the solution using the Θ notation) Θ(n^2)
9 姚岚分而治之和动态规划均是基于递归技术的算法。请分别列举出一种采用上述思想的经典算法，并比较两种思想的差别。分而治之：快速排序动态规划：Floyd 算法
分而治之思想是自顶向下把问题实例划分成若干无重叠子实例，递归得到子实例的后组合。动态规划：自底向上，有重叠子问题。
10 段景耀题目：请简述计算最小耗费生成树的 Kruskal 算法。答案：
1.设 G=(V,E)，对 G 的边以非降序权重排列； 2.对于排序表中的每条边，如果放入 T 中不会形成回路的话，则将他加入 T 中，否则将它丢弃。 11 乔梁请简述有向深度图中边的种类分别有哪些，并举例说明。答：4 类，树边（tree edge）回边（back edge）前向边（forward edge）横跨边（cross edge），举例只要 '即可。

下一页