《算法设计与分析》实验与复习题
第一章 引 论
习题1 写一个通用方法用于判定给定数组是否已排好序。 算法实例：
Algorithm compare(a,n) 、
Begin J=1;
While (j While (j If j=n then return true else return false end if End if … end 习题1 写一个算法交换两个变量的值不使用第三个变量。 算法实例： x=x+y; y=x-y; x=x-y; 习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件 (n2-mn-m2)2=1 且使n2+m2达到最大的m、 n。 ？ 算法实例： m:=k; flag:=0; repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) ] if n=0 then m:=m-1 until (flag=1) or (m=0); 第二章 基础知识 \ 习题2-1 求下列函数的渐进表达式： 3n2+10n; n2/10+2n; 21+1/n; logn3; 10 log3n 。 解答： 3n2+10n=O（n2）， n2/10+2n=O（2n）， 21+1/n=O（1）， logn3=O（log n），10 log3n=O（n）。 习题2-2 说明O(1)和 O(2)的区别。 & 习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!， 4n2,logn,3n,20n,2,n2/3。 解答：照渐进阶从低到高的顺序为：n!、 习题2-4 3n、 4n、n、20n、logn、2 223（1） 假设某算法在输入规模为n时的计算时间为T(n)?3?2n。在某台计算机 上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题 （2） 若上述算法的计算时间改进为T(n)?n2，其余条件不变，则在新机器上用 t秒时间能解输入规模多大的问题 （3） 若上述算法的计算时间进一步改进为T(n)?8,其余条件不变，那么在新机 器上用t秒时间能解输入规模多大的问题 , 解答： （1） 设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有 t?3?2n?3?2n1/64，解得n1?n?6。 （2） n12?64n2??n1?8n。 （3） 由于T(n)?常数，因此算法可解任意规模的问题。 习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题 、 解答： n??100n。 n?2?100n2??n??10n。 n?3?100n3??3100n?4.64n。 n?!?100n!??n??n?log100?n?6.64。 习题2-6对于下列各组函数f(n)和g(n)，f(n)??(g(n))或f(n)??(g(n))，并简述理由。 < （1）f(n)?logn2;g(n)?logn?5。 （2）f(n)?logn2;g(n)?n。 （3）f(n)?n;g(n)?log2n。 （4）f(n)?nlogn?n;g(n)?logn。 （5）f(n)?10;g(n)?log10。 （6）f(n)?log2n;g(n)?logn。 （7）f(n)?2n;g(n)?100n2。 （8）f(n)?2n;g(n)?3n。 ? 解答： （1）logn2??(logn?5)。 确定f(n)?O(g(n))或 2（2）logn?O(n)。 （3）n??(logn)。 （4）nlogn?n??(logn)。 （5）10??(log10)。 （6）logn??(logn)。 （7）2??(100n)。 / 22n2 nn（8）2?O(3)。 习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为?(f(n))，则该算法在最坏情况下所需的计算时间为?(f(n))。 证明： Tavg(N)??I?DN?P(I)T(N,I)?P(I)maxT(N,I?)I??DNI?DNI?DN ?T(N,I*)?P(I)?T(N,I*)?Tmax(N)因此，Tmax(N)??(Tavg(N))??(?(f(n)))??(f(n))。 ￥ 习题2-7 求解下列递归方程: s0=0 sn=2sn-1+2n -1 解答： 步骤: 1应用零化子化为齐次方程， 2解此齐次方程的特征方程， 3由特征根构造一般解， 4再由初始条件确定待定系数，得到解为： * sn?(n?1)2n?1 习题2-8 求解下列递归方程: h0?2??h1?8 ??h?4h?4hn?1n?2?n解 hn=2n+1(n+1) , 第三章 递归与分治策略 习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。 public static int binarySearch1(int []a,int x,int n) { int left=0; int right =n-1; while (left<=right) { ? int middle = ( left + right )/2; if ( x == a[middle]) return middle; if ( x> a[middle]) left = middle; else right = middle; return -1; } public static int binarySearch2(int []a, int x, int n) ！ { int left = 0; int right = n-1; while ( left < right-1 ) { int middle = ( left + right )/2; if ( x < a[middle]) right = middle; else left = middle; } if (x == a[left]) return left; — else return -1 }
算法设计与分析考试复习题(北京邮电大学-北京地区适用)
