l算法设计与分析AK.docVIP

网络学院算法试题A及答案 一．填空题：（前四小题每题3分，第5小题4分，共16分） 1. 算法的特性有_0至多个输入， 至少一个输出， 指令无歧义性， 指令条数有限且每条指令执行时间有限 . 2．程序性能是指_运行一个程序所需的内存大小和时间多少_. 性能评估主要包含两方面, 即性能分析_与 性能测量__, 前者采用_分析__的方法，后者采用__测量_的方法。 3. 估算程序运行时间的方法有_操作计数法 _和_程序的执行步数__. 4．递归函数的两大基本要素是_递归方程 和 边界条件_ . 5．在回溯法中，一个问题的解空间是指一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间. 二．简答题：（每题6分，共24分） 什么是实例特征？ 答：所谓实例特征是指决定问题规模的那些因素. 如，输入和输出的数量或相关数的大小，如对 n 个元素进行排序、n′n矩阵的加法等，都可以 n 作为实例特征. 2．什么是最优子结构性质?答：所谓最优子结构性质，即为一个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 3．什么是贪心选择性质？ 答：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到. 这是贪心算法可行的第一个基本要素. 4.对下述的顺序有哪些信誉好的足球投注网站函数，假定以被查数组的长度 n为实例特征，分析其空间复杂性 int SequentialSearch(int a[],const int x, int n) { // 在 a[0:n-1]中有哪些信誉好的足球投注网站x，若找到则回所在的位置，否则返回-1 int i; for(i=0; in a[i]!=x; i++); if (i==n) return –1; return i; } 解答：在上述函数中，假定采用被查数组的长度 n 作为实例特征。数组中每个元素需要 2 个字节，实参x 需要2 个字节，传值形式参数 n 需要2 个字节，局部变量 i 需要2 个字节，整数常量 –1 需要2 个字节，所需要的总的数据空间为 10 个字节，其独立于 n, 所以 S顺序查找(n)=0. 这里我们并没有巴数组a 所需的空间计算进来，因为该数组所需的空间已在定义实际参数(对应于 a) 的函数中分配，不能再加到函数 SequentialSearch 所需的空间上去。 三．计算和编程题：（每小题15分,共60分） 1．考虑金钱兑换问题：有一个货币系统，它有n种硬币，它们的面值为v1,v2,…,vn，其中 v1=1. 我们想这样来兑换价值为y的钱，要让硬币的数目最少。更形式地，我们要让下面的量 在约束条件 下最小. 其中x1, x2, …, xn是非负整数. 1) 用贪心算法求解该问题； 2) 如果硬币的面值有1分，5分，7分和11分，给出反例说明用贪心算法并不总是有效的。 1) 贪心伪代码为： Greedy_exchange(int v[], int y, int num[], int n) { int i=0, for i=0 to n do num[i]=0; Sort(v); // 从大到小排序 while y0 do { num[i]=y/v[i]; y=y%num[i++]； } return num; } ?N且n1)个硬币，已知其中有一个是假币且假币较真币轻. 请设计分治算法求解该问题.并给出其复杂度分析. Feit_money(low, high) // 假定伪币较真币轻 { float mid; if high-low=1 then if A[low]A[high] then return A[low]; else if A[low]A[high] return A[high]; else mid=(low+high)/2; if (high-low+1)%2==0 then sum1=sum(low, mid); sum2=sum(mid+1, high); else sum1=sum(low, mid-1); sum2=sum(mid+1, high); end if if sum1=sum2 then return A[mid]; else if sum1sum2 then (high-low+1)%2==0? Feit_money