算法分析样卷_48266.doc

《算法分析与设计》 样卷 一、选择题（20分，每题2分） 1. 0-1背包问题用（ ）实现算法最好。 A、分治策略 B、动态规划法 C、贪心法 D、穷举法 2. 下列动态规划的最基本的要素是（ ）。 A、算出最优解 B、贪心选择性质 C、重叠子问题 D、定义最优解 3. 下列算法中通常以广度优先方式系统有哪些信誉好的足球投注网站问题解的是（ ）。 A、分支限界法 B、动态规划法 C、贪心法 D、回溯法 4. 自底向上方法是（ ）的计算最优值的方法中的一种。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 5. 一般(部分)背包问题的贪心算法所需的计算时间为（ ） A、O（n） B、O（nlogn） C、O（2n） D、O（n2） 6. 大整数乘法可以利用（ ）的算法来实现。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7..下列程序段的频度是（ ）。 for(i=0;in;i++) for(j=0;jn;j++) k++; A、n2 B、n C、n*(n+1)/2 D、 2n 8. 下列问题一般不采用分治法的是（ ）。 A、三分检索 B、求最大最小值问题 C、最大子段和 　　 D、矩阵连乘问题 9. 对多段图问题描述不正确的是（ ） A、多段图是一个无向图 B、可用向前处理法 C、可用向后处理法 D、可用分治法解决。 10.以下对回溯法描述正确的是（ ） A、必须使用栈来实现算法。 B、使用广度优先方式系统有哪些信誉好的足球投注网站问题解 C、它可以用裁剪函数来减少有哪些信誉好的足球投注网站空间的规模，减少时间复杂度 D、回溯法只能用来求最优化问题 二、填空题（20分，每空2分） 算法的确定性是（ ）。 有限性是指（ ）。 矩阵连乘问题可以用（ ）设计。 所谓贪心选择性质是指所求问题的（ ）以通过( )，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与（ ）m [i][j]记录需要的最少数乘次数，则m [i][j]递归定义为： （ ） 三、简答题（20分，每小题5分） 写出动态规划的基本要素。 说明贪心算法与动态规划算法的的主要差别。 写出用回溯法有哪些信誉好的足球投注网站排列树的一般算法。 简述利用分冶法来解决大整数乘法的基本思想。 四、算法设计题（40分） 1.给定数组a[0:n-1]，试设计一个分治算法，在最坏情况下用 n+[logn]-2次比较找出a[0:n-1]中元素的最大值和次最大值。要求写出算法的思想，算法步骤，并说明时间复杂性。（20分） 2. 给定由n 个整数组成的序列a[0:n-1]。序列a 的递增子序列定义为，存在下标序列i1i2…ik使得a[i1]=a[i2]=…=a[ik]。求a 的最长递增子序列。要求写出用动态规划解此问题的算法的思想，最优子结构性质，递归公式，递归公式的计算方法，时间复杂性说明。（20分） 参考答案及评分标准（B） 选择题（20分，每题2分） 1. B 2. C 3. A 4. B 5. B 6. A 7. A 8. D 9. A 10. C 二、填空题（20分，每空2分） 1. 组成算法的每条指令是清晰，