1.分治法
1.1：快速排序算法采用的设计方法是____。
A. 动态规划法 (Dynamic Programming)
B. 分治法 (Divide and Conquer)
C. 回溯法 (Backtracking)
D. 分枝定界法 (Branch and Bound)
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是____，该算法采用的设计方法是____。
1.2：A.归并算法 B.插入算法 C.选择算法 D.冒泡算法
1.3：A.分治法 B.贪心法 C.动态规划法 D.回溯法
2.动态规划法
2.1：采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是____
A.当前所出的决策不会影响后面的决策
B.原问题的最优解包含其子问题的最优解
C.问题可以找到最优解，但利用贪心法不能找到最优解
D.每次决策必须是当前看来最优决策才可以找到最优解
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用( )策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串＜1，0，0，1，0，1，0，1，＞和＜0，1，0，1，1，0，1，1，＞的最长公共子序列的长度为( )。
2.2：A．分治 B．贪心 C．动态规划 D．分支一限界
2.3：A 3 B 4 C 5 D 6
某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n（Sij，i=1或2，j= 1，2，...，n），两条装配线对应的工位完成同样的加工工作，但是所需要的时间可能不同（aij，i=1或2，j = 1，2，...，n）。汽车底盘开始到进入两条装配线的时间 (e1，e2) 以及装配后到结束的时间(X1X2)也可能不相同。从一个工位加工后流到下一个工位需要迁移时间(tij，i=1或2，j =2，...n）。现在要以最快的时间完成一辆汽车的装配，求最优的装配路线。
分析该问题，发现问题具有最优子结构。以 L1为例，除了第一个工位之外，经过第j个工位的最短时间包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，如式(1)。装配后到结束的最短时间包含离开L1的最短时间或者离开L2的最短时间如式（2）。
由于在求解经过L1和L2的第j个工位的最短时间均包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，该问题具有重复子问题的性质，故采用迭代方法求解。
该问题采用的算法设计策略是（ ），算法的时间复杂度为（ ）
以下是一个装配调度实例，其最短的装配时间为（ ），装配路线为（ ）
2.4：A.分治 B.动态规划 C.贪心 D.回溯
2.5：A. O(lgn) B. O(n) C. O(n2) D. O(nlgn)
2.6：A.21 B.23 C.20 D.26
2.7：
A.S11-->S12-->S13
B.S11-->S22-->S13
C.S21-->S12-->S23
D.S21-->S22-->S23
【试题分析：动态规划算法与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解决这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。本题中的时间复杂度为O(n)。
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术即为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
求最短的装配时间与装配路线只需要将选项按照公式代入计算（将图上每条路径上的所有数字相加）可得最短路线为S11->S22->S13，时间为21。】
两个矩阵Am×n和Bn×p相乘，用基本的方法进行，则需要的乘法次数为m×n×p 多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M{i+i)，…，Mj多个矩阵连乘的最优顺序，即所需要的乘法次数最少。最少乘法次数用m[i，j]表示，其递归式定义为：
其中i、j和k为矩阵下标，矩阵序列中Mi的维度为(Pi-i.)×Pi采用自底向上的方法:实现该算法来确定n个矩阵相乘的顺序，其时间复杂度为( )。若四个矩阵M1. M2、M3.，M4相乘的维度序列为2、6、3、10.3，采用上述算法求解，则乘法次数为( )。
2.8：
A.O(N2)
B.O(N2Lgn)
C.O(N3)
D.O(n3lgn)
2.9：
A 156
B 144
C 180
D 360
【试题分析：
方法一：矩阵链乘法。
一个给定的矩阵序列A1A2...An计算连乘乘积，有不同的结合方法，并且在结合时，矩阵的相对位置不能改变，只能相邻结合。根据矩阵乘法的公式，10×100和100×5的矩阵相乘需要做10×100×5次标量乘法。那么对于维数分别为10×100、100×5、5×50的矩阵A、B、C，用(A×B)×C来计算需要10×100×5 + 10×5×500 =7500次标量乘法；而A×(B×C)则需要100×5×50+10×100×50=75000次标量乘法。
方法二：
四个矩阵分别为2×6、6×3、3×10、10×3，先计算M1×M2和M3×M4，计算次数分别为2×6×3=36、3×10×3=90。然后结果相乘，计算次数为2×3×3=18。】
3.贪心法
3.1：贪婪法是一种____的算法。
A.不求最优,只求满意 B.只求最优 C.求取全部可行解 D.求取全部最优解
在下列算法设计方法中，____在求解为题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决____问题
3.2：A.分治法 B.贪心法 C.动态规划法 D.回溯法
3.3：A.排序 B.检索 C.完全背包 D.0/1背包
3.4：哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉 20%至90%。
在数据压缩编码的应用中，哈夫曼（Huffman）算法可以用来构造具有最优前缀码的二叉树，这是一种采用了____的算法。
A. 贪心 B. 分治 C. 递推 D. 回溯
3.5：利用贪心法求解0/1背包问题时，______能够确保获得最优解。
供选择的答案：
A.优先选取重量最小的物品
B.优先选取效益最大的物品
C.优先选取单位重量效益最大的物品
D.没有任何准则
在一条笔直公路的一边有许多房子，现要安装消防栓，每个消防栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上的点）。
该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为（ ）；对应的时间复杂度为（ ）。
假设公路起点A的坐标为0，消防栓的覆盖范围（半径）为20米，10栋房子的坐标为（10，20，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法的叙述中，正确的是（ ）。
3.6：A. 分治 B. 动态规划 C. 贪心 D. 回溯
3.7：A. O(lgn) B. O(n) C. O(nlgn) D. O(n2)
3.8：A. 4 B. 5 C. 6 D. 7
3.9：
A. 肯定可以求得问题的一个最优解
B. 可以求得问题的所有最优解
C. 对有些实例，可能得不到最优解
D. 只能得到近似最优解
4.综合
现需要申请一些场地举办一批活动，每个活动有开始时间和结束时间。在同一个场地，如果一个活动结束之前，另一个活动开始，即两个活动冲突。若活动A从1时间开始，5时间结束，活动B从5时间开始，8时间结束，则活动A和B不冲突。现要计算n个活动需要的最少场地数。
求解该问题的基本思路如下（假设需要场地数为m，活动数为n，场地集合为P1，P2,…,Pm），初始条件Pi均无活动安排：
（1）采用快速排序算法对n个活动的开始时间从小到大排序，得到活动a1，a2，…，an。对每个活动ai，i从1到n，重复步骤（2）、（3）和（4）；
（2）从p1开始，判断ai与P1的最后一个活动是否冲突，若冲突，考虑下一个场地p2，…；
（3）一旦发现ai与某个pj的最后一个活动不冲突，则将ai安排到Pj，考虑下一个活动；
（4）若ai与所有已安排活动的pj的最后一个活动均冲突，则将ai安排到一个新的场地，考虑下一个活动；
（5）将n减去没有安排活动的场地数即可得到所用的最少场地数。
算法首先采用了快速排序算法进行排序，其算法设计策略是（ ）；后面步骤采用的算法设计策略是（ ）。整个算法的时间复杂度是（ ）。下表给出了n=11的活动集合，根据上述算法，得到最少的场地数为（ ）。
4.1：A.分治 B.动态规划 C.贪心 D.回溯
4.2：A.分治 B.动态规划 C.贪心 D.回溯
4.3：A.Θ(lgn) B.Θ(n) C.Θ(nlgn) D.Θ(n2)
4.4：A.4 B.5 C.6 D.7
【试题分析：快速排序由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分虽地行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。
贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
整个算法的时间复杂度是O(nlogn)。
场地上可以安排活动1、8、11为一个场地：活动2、6、9一个场地；活动3为一个场地；活动4、7为一个场地；活动5、10为一个场地，共5个场地。 】
求解两个长度为n的序列X和Y的一个最长公共子序列（如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（ ）。经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为C[i,j]，如下式所示。
采用自底向上的方法实现该算法，则时间复杂度为（ ）。
4.5：
A.O(n²)
B.O(n²lgn)
C.O(n³)
D.O(n2n)
4.6：
A.O(n²)
B.O(n²lgn)
C.O(n³)
D.O(n2n)
