算法考试题-重点.docxVIP

一、选择题（每题 2 分，10 题，共 20 分） 1、关于记号 O 正确的定义是（ ）。 A、O(g(n)) = {f(n) |对任意正数 c 存在 n0 使得对所有n≥n0 有 0≤f(n)cg(n)} B、O(g(n)) = {f(n) |对任意正数 c 存在 n0 使得对所有n≥n0 有 0≤cg(n) f(n)} C、O(g(n)) = {f(n) |存在正数 c 和 n0 使得对所有n≥n0 有 0≤f(n)≤cg(n)} D、O(g(n)) = {f(n) |存在正数 c 和 n0 使得对所有n≥n0 有 0≤cg(n) ≤f(n)} 2、以下算法思想中，有可能得到的解为不正确解的是（ ）。 A、动态规划 B、贪心 C、蒙特卡罗 D、拉斯维加斯 分析： 蒙特卡罗（Monte Carlo）算法：蒙特卡罗（Monte Carlo）算法用于求问题的准确解。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。 拉斯维加斯（Las Vegas）算法：拉斯维加斯（Las Vegas）算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。 二、填空题（每空 2 分，15 空，共 30 分） 1、算法是由若干条指令组成的有穷序列，且要满足有输入、有输出、确定性 、有效性和有限性性质。算法的效率一般可以从时间复杂度、空间复杂度两个方面衡量。 2、假设算法A 理论上的时间复杂度T(n)=3n，现在有两台同类型计算机M1和M2，M2的计算速度是M1的a倍。若在M1和M2上分别测试算法A，则在相同时间内，M1和M2能够求解的问题规模n1和n2的关系为n1 : n2 = 1 : a。若算法B理论上的时间复杂度为T(n)=n2， 若在M1和M2上分别测试算法B，则M1和M2求解相同规模问题所耗费的时间t1和t2的关系为t1:t2 = 1:√a。在此处键入公式。 3、在随机化算法中，能够平滑不同输入实例之间差异的算法是 舍伍德 算法。 分析： 使用Sherwood处理后的算法能够平滑不同输入实例的执行时间。 sherwood是一种概率算法思想，使得算法的复杂度不依赖于实例，而是依赖于概率。 4、采用分治法解决问题时，算法时间复杂度分析典型的递推方程为 ?T (n) ??O(1) ? ?aT (n / b) ?f (n) n ?1 n ?1  ，对于某一问题，若 f(n) = O(1)且 a = 1，则求解该问题 的时间复杂度为 O(logn) ；若f(n)=O(x)且a=x,by，则求解该问题的时间复杂度为 O(n2) ；若f(n) = O(n)，则求解该问题的时间复杂度为 n ；若已知f(n)=O(x)，且a,b均大于1，若希望将算法时间复杂度降低为不超线性情况，则a和b应满足的条件为： a=b。 三、算法设计与分析题（3 题，每题 10 分，共 30 分） 1、已知一箱苹果有 n 个，重量分别为 w1, w2, … , wn，若要求计算这 n 个苹果的最小重量差 i jmin h ? i j 1?i?n 1?j?n ，请为该问题设计一个有效算法，并对所设计的算法进行时间复杂性分析。 要求：（1）给出算法基本思想描述。 给出算法的伪代码描述。 对所设计算法进行时间复杂性分析。需要给出步骤和结果，包括：确定问题规模参数，算法基本操作，影响基本操作执行次数因素等。 说明：不要求代码实现 （1）基本思想： 自顶向下分析，diff[i]记录0~i的最小数对之差，max[i]记录0~i的最大数，则状态递归方程为： diff[i+1]=Math.min(max[i]-array[i+1]，diff[i] ) （2） float getMinDiff(a) float getMinDiff(a) 输入：苹果数组 a[1-n] 返回：最小重量差 minDiff sort(a)//按苹果重量非递减排序minDiff ← MAXDIFF for i←1 to n-1 min ← a[i] – a[i-1] if min minDiff minDiff ← min （3） 在不考虑排序情况下： 问题规模参数为输入数组中元素个数； 算法基本操作为 min ← a[i] – a[i-1]； 影响基本操作执行次数的因素只取决于问题规模 n； 基本操作执行次数为 n-1 次；时间复杂度为 O(n)。 排序可以在 O(nlogn)时间复杂度下完成，因此算法时间复杂度为取决于排序时间复杂度，为 O(nlogn)。 2、给定 n 种物品和一个背包。物品 i 的重量为 wi，体积为 bi，其价值为 vi，背包容量为 c，容积为 d。应如何选择装入背包的物品，使得装入背包中物