算法设计与分析习题
《算法设计与分析》习题
第一章算法引论
1、算法的定义？
答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲，算法：就是解决问题的方法或过程。
2、算法的特征？
答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性
3、算法的描述方法有几种？
答：自然语言、图形、伪代码、计算机程序设计语言
4、衡量算法的优劣从哪几个方面？
答：(1) 算法实现所耗费的时间（时间复杂度）；
(2) 算法实现所所耗费的存储空间（空间复杂度）；
(3) 算法应易于理解，易于编码，易于调试等等。
5、时间复杂度、空间复杂度定义？
答：指的是算法在运行过程中所需要的资源（时间、空间）多少。
6、时间复杂度计算：
{i=1；
while（i<=n）
i=i*2； }
答：语句①执行次数1次，
语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n;
算法执行时间： T(n)= 2log2n +1
时间复杂度：记为O(log2n) ；
7.递归算法的特点？
答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）
②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）
8、算法设计中常用的算法设计策略？
答：①蛮力法；②倒推法；③循环与递归；④分治法；
⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法
9、设计算法：
递归法：汉诺塔问题？兔子序列（上楼梯问题）？
整数划分问题？
蛮力法：百鸡百钱问题？
倒推法：穿越沙漠问题？
答：算法如下：
（1） 递归法
● 汉诺塔问题
void hanoi(int n, int a, int b, int c)
{if (n > 0)
{
hanoi(n-1, a, c, b);
move(a,b);
hanoi(n-1, c, b, a);
} }
● 兔子序列（fibonaci 数列 ）
递归实现：
Int F(int n)
{
if(n<=2) return 1;
else
return F(n-1)+ F(n-2);
}
● 上楼梯问题
Int F(int n)
{
if(n=1) return 1
if(n=2) return 2;
else
return F(n-1)+ F(n-2);
}
● 整数划分问题
问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+…
将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数
p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系：
递归算法：
Int q( int n, int m){
if(n<1||m<1) return 0;
If((n=1)||(m=1)) return 1;
If (n If(n=m) return q(n,m-1)+1; else return q(n,m-1)+q(n-m,m); } ???????>>=<==-+--+=11,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q （2）蛮力法：百鸡百钱问题 算法设计1： 设x，y，z分别为公鸡、母鸡、小鸡的数量。约束条件：x+y+z=100 且5*x+3*y+z/3=100 main( ) { int x,y,z; for(x=1;x<=20;x=x+1) for(y=1;y<=34;y=y+1) for(z=1;z<=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) { print(the cock number is",x)； print(the hen number is", y)； print(the chick number is "z);} } 算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低 算法设计2： 在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量 z就固定为100-x-y，无需再进行枚举了。此时约束条件只有一个： 5*x+3*y+z/3=100 main( ) { int x,y,z; for(x=1;x<=20;x=x+1) for(y=1;y<=33;y=y+1) { z=100-x-y; if(z mod 3=0 and 5*x+3*y+z/3=100) {print(the cock number is",x)； print(the hen number is", y)； print(the chick number is "z);} } } 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。 (3) 倒推法：穿越沙漠问题 desert（） { int dis，k，oil,k; // dis表示距终点的距离，k表示贮油点从后到前的序号 dis=500;k=1;oil=500; //初始化 while ( dis<1000) { print(“storepoint”,k,”distance”, 1000-dis,”oilquantity”,oil) //1000- dis则表示距起点的距离， k=k+1; //k表示储油点从后到前的序号 dis=dis+500/(2*k-1); oil= 500*k; } print(“storepoint”,k,”distance”,dis,”oilquantity”,oil)； } 第二章分治算法 1、分治算法基本思想是什么？适合用分治算法解决的问题，一般具有几个特征？分治算法基本步骤是什么？ 答：1)基本思想:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 2) 特征： 该问题的规模缩小到一定的程度就可以容易解决; 该问题可以分解为若干个规模较小的相同子问题，即该问题具有最优子结构性质； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 4)利用该问题分解出子问题解可以合并为该问题解; 3）基本步骤：分解、求小问题解、合并 2、改写二分查找算法：设a[1…n]是一个已经排好序的数组，改写二分查找算法: ?当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j； (即返回x的左、右2个元素) ?当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。 并计算其时间复杂度？ 答： ３、设计一个合并排序的算法？（分治法解）并计算其时间复杂度？(要求写出递推 公式，及其求解过程) 答： void MergeSort (int A[]，int low ，int high) { int middle; if (low { middle=(low+high)/2; //取中点 MergeSort(A,low,middle); MergeSort(A,middle+1,high); Merge(A,low,middle,high); //合并算法 } } void Merge(int A[]，int low ，int middle ，int high) //合并过程描述： { int i,j,k; int *B=new int[high-low+1]; i=low; j=middle+1; k=low; while(i<=middle&&j<=high) { //两个子序列非空 if(A[i]<=A[j]) B[k++]=A[i++]; else B[k++]=A[j++]; } while (i<=middle) B[k++]=A[i++]; //子序列A[low ，middle]非空，将A 复制到 B while (j<=high) B[k++]=A[j++]; /子序列A[middle+1， high]非空，将A 复制到 B for(i=low;i<=high;i++) A[i++]=B[i++]; //将合并后的序列复制回A } ? 合并排序算法运行时间T(n)的递归形式为： 分析该算法时间复杂度： 令T(n)为元素个数为n 时所需比较次数（时间）： 当n=１时， 时间复杂度记为O(1)。 当n>１时，T(n)=2 T(n/2) + O(n) =2 (2T(n/22)+O(n/2) ) + O(n) =22T(n/22) + 2 O(n) =23T(n/23) + 3O(n) =…… =2x T(n/2x ) + x*O(n) 分解到最后只有2个元素可以求解，n/2x ＝1， x=logn; 故 T(n)=n*T(1)+n*logn ，故时间复杂度记为：O （n * logn ） ４、金块问题（求最大最小元问题） 老板有一袋金块(共n 块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最 O(1)n=1T(n)=2T(n/2)+O(n) n>1??? 轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。 要求：１）设计一算法求解该问题？（分治法解） ２）计算其时间复杂度？(要求写出递推公式，及其求解过程) 答：递归求取最大和最小元素 maxmin （int i, int j ,float &fmax, float &fmin） { int mid; float lmax, lmin, rmax, rmin; if (i=j) {fmax= a[i]; fmin=a[i];} //只有1个元素 else if (i=j-1) //只有2个元素 if(a[i] else {fmax=a[i]; fmin=a[j];} else //多于2个元素 {mid=(i+j)/2; maxmin （i，mid，lmax，lmin）;//递归调用算法求最大最小 maxmin （mid+1，j，rmax，rmin）;//递归调用算法求最大最小 if(lmax>rmax) fmax=lmax; //合并取大 else fmax=rmax; if(lmin>rmin) fmin=rmin; //合并取小 else fmin=lmin; } 分析该算法时间复杂度： 令T(n)为元素个数为n时所需比较次数（时间）： 当n=2时，查找查找最大最小元只需要1次比较，T(2)=1；时间复杂度记为O(1)。 当n>2时， T(n)=2T(n/2) + 2 T(2) =4T(n/4) + 4 T(2) + 2 T(2) =8T(n/8) + 8 ＋ 4 ＋ 2 =…… =2x T(n/2x) + 2x +2x-1+…+8+4+2 分解到最后只有2个元素可以求解，n/2x＝2， T(n)= 2x *1 + 2x +2x-1… + 22 + 21 = 2x *1 +(2- 2x*2 )/(1-2） = 2x + 2x+1 - 2 =3n/2 - 2 故时间复杂度记为：O（n） ５、用分治思想设计一个有效的算法，可以进行两个n位大整数的乘法运算？并计算其时间复杂度？（要求写出递推公式，及其求解过程） 答： int mult( int x, int y, int n) //x, y为两个n位整数 { s=sign(x)*sign(y); //s为x* y的符号 x=abs(x); y=abs(y); int mul; if( n=1) { mul=s*x*y; return mul; } else // 计算XY = ac 2n + ((a-b)(d-c)+ac+bd) 2n/2 + bd { int a=x左边n/2位； // 移位操作，把X分为2块 int b=x右边n/2位； int c=y左边n/2位； //移位操作，把Y分为2块 int d=y右边n/2位； int m1= mult( a, c, n/2); // a, c还不够小继续分为2块,直到最后1×1位 int m2= mult( a-b, d-c, n/2); int m3= mult( b, d, n/2); mul=s*( m1*2n+(m1+m2+m3)*2n/2+m3 ); return mul; } } ６、设计一棋盘覆盖问题算法（分治法）？并计算其时间复杂度？（要求写出递推公式，及其求解过程） 在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 （该算法中可能用到的变量： tr ：棋盘中左上角方格所在行；tc ：棋盘中左上角方格所在列。 dr：残缺方块所在行；dl ：残缺方块所在列。 size:棋盘的行数或列数；用二维数组board[ ][ ]，模拟棋盘。）答：void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; //size:棋盘行数 int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格 board[tr + s - 1][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右下角 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖其余方格 // 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 board[tr + s - 1][tc + s] = t; // 用 t 号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖其余方格 // 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else { board[tr + s][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右上角 chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖其余方格 // 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else { board[tr + s][tc + s] = t; // 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s);} // 覆盖其余方格 } 第三章动态规划算法 １、动态规划算法基本思想？动态规划算法与分治算法异同点？适合用动态规划算法求解问题的基本要素？动态规划算法的基本步骤？ 答：1）基本思想：将待求解问题分解成若干个子问题；由于子问题有重叠，动态规划算法能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算. 2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。 不同： ?用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治算法实现一般用递归； ?动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环; 3）基本要素：具有最优子结构；子问题具有重叠性 4）步骤：1)分析最优解的性质，并刻划其结构特征。 2)递推地定义最优值。 3)以自底向上的方式计算出最优值. 4)根据计算最优值时得到的信息，构造问题的最优解. ２、序列X={X1，X2,…Xm }和 Y={Y1,Y2…Yn}的最长公共子序列为Z={Z1,Z2,…Zk} 用动态规划的方法求序列 X 和Y的最长公共子序列长度？ （要求按照动态规划写出动态规划求解问题的步骤分析①最优子结构②写出递归方程③算法描述） 注：C[ ｍ][ ｎ]记录序列X与Y的最长公共子序列的长度 答：①最优子结构 设序列X={ x1，x2，…x m } 与 序列Y={ y1，y2，…y n }的一个 最长公共子序列Z={ z1，z2，…z k } Ⅰ、若x m= y n, 则z k=x m= y n, 且{ z1，z2，…z k-1 }是序列X m-1与 序列Y n-1的最长公共自序列； Ⅱ、若x m≠y n, 且x m≠ z k, 则Z是X m-1与Y的最长公共子序列； Ⅲ、若x m≠y n, 且y n≠ z k, 则Z是X与Y n-1的最长公共子序列; 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。即，原问题最优解，包含子问题最优解； 因此，最长公共子序列问题具有最优子结构性质。 ②写出递归方程 ③循环实现，计算最优值C[ i][ j]，算法描述 Int lcsLength( x[ ], y[ ], b[ ][ ]) { int m=x.length-1; n=y.length-1; for(int i=1; i for(int i=1; i for (int i = 1; i <= m; i++) //x序列长为ｍ for (int j = 1; j <= n; j++) //ｙ序列长为n if (x[i]==y[j]) { C[i][j]=C[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { C[i][j]=C[i-1][j]; b[i][j]=2;} else { C[i][j]=C[i][j-1]; b[i][j]=3;} return C[m][n]; } ◆时间复杂度分析：该算法时间复杂度：O(m*n) ④构造最长公共子序列，算法描述： void LCS (char X[ i], Y[ j], int b[ ][ ]) { if (i ==0 || j==0) return; if (b[ i][ j]== 1) { LCS( X[ i-1], Y[ j-1], b); system.out.print( x[ i] ); } else if (b[ i][ j]== 2) LCS(X[i-1]，Y[ j]，b); else if (b[ i][ j]== 3) LCS(X[ i] ，Y[j-1], b); } ◆时间复杂度分析： 此算法每一次递归调用使得i或j减１，因此该算法时间复杂度为O(m+n) ３、长江游艇俱乐部在长江上设置了n个游艇出租站1,2…n. 游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。 游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1<=i 试设计一个算法，计算出游艇从出租站1到出租站n所需最少租金？ （见习题集第三章算法设计与计算题T2） 4、掌握动态规划方法求解０－１背包问题？ 答：①分析问题的最优解结构 设（y1,y2,…y n）所给0－1背包容量为M的解； 则，（y2,…y n）相应子问题背包容量为M－w1的解； （即原问题最优解，包含了子问题最优解） ②递归定义最优值 ③计算最优值m(i，j) void knapsack( int v[ ], int w[ ], int M, int m[ ] [ ] ) {int n=v.length; if ( M m[ n][ M]=0; else if (M>=w[ n]) { m[ n][ M]=v[ n]; M=M-w[ n]; } for( int i=n-1; i>=1; i--) // i { if (M m[ i] [M]=m[ i+1][ M]; else if (M>=w[ n]) { m[ i][ M]=math.max( m[ i+1][ M], m[ i+1][M-w[ i]+v[i]); M=M-w[ i]; } } } ◆该算法时间复杂度：O(c*n) c常数 ④构造最优解 void trackack( int m[ ] [ ], int w[ ], int M, int x[ ] ) {//x[ i]标记i是否放入背包 int n=w.length; for( int i=1; i { if (m[ i][ M]=m[ i+1][ M] ) x[ i]=0; else { x[ i]=1; M=M-w[ i]; } } x[ n]=(m[ n][ M]>0)? 1:0 ; //判断第n个物体是否放入背包 } ◆该算法时间复杂度：O(n) 第 4 章贪心算法 1、贪心算法基本思想？ 答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解 2、贪心算法的基本要素？ 答：贪心选择性；最优子结构 3、贪心算法与动态规划算法的异同? 答：1 ）相同点：对于要求解的问题都具有最优子结构； 2 ）不同点：算法的基本思想不同； 求解问题的类型不同； 例：普通背包问题贪心算法求解 0-1背包问题动态规划算法求解 4、设计普通背包装载问题的贪心算法? 并分析其时间复杂度？ 答： float greedy_knapsack ( float M, float w[ ], float p[ ], float x[ ] ) // M 背包载重 x[ ]背包问题最优解, w[ ]物品重量， P[ ]物品价值{ int n=w.length; //n物品的个数 float pp=0; //pp计算当前背包总价值 float mm＝M; //mm背包剩余载重 for( int i=1;i<=n; i++ ) { float ww[ i]= p[ i] / w[ i]； //计算物品单位价值ww[ ] x[ i]=0; } //初始化，所有物品没有放入背包Mergesort (w[ i ], ww[ i]，n ); //按单位价值将物品排序，便于贪心选择 for( int i=1; i<=n; i++ ) //贪心选择，总是选择价值最大放入背包{ if ( w[ i]<=mm ) //当前物品小于背包剩余载重 { x[ i]=1; mm=mm - w[ i]; pp=pp + p[ i]; } //整个放入背包 else { x[ i]=mm/w[ i]; pp=pp + x[ i]*p[ i]; break; } //i部分放入背包} return pp; } 该算法主要包括以下几部分： 计算物品单位价值时间，其时间复杂度O(n)； 按照物品单位价值排序时间，其时间复杂度为O(n*logn); (合并排序时间) 贪心选择时间，其时间复杂度为O(n)； 故该算法的时间复杂度为：O(n*logn+2n)；记为： O(n*logn) 5、设计找零问题的贪心算法? 并分析其时间复杂度？ 答：void greedy_zhaoling ( float GZ, int B[ ], int S[ ] ) //GZ应发工资 { B[ j]初始化排序；//为了贪心选择，依次选最大币种 for( j=1, j<=6;j++) { S[ j]=0； //初始化S[ j] A=GZ/B[ j]; //A表示对应j币种张数 S[ j]=A; //S[ j]存放对应j币种总张数 GZ=GZ-A*B[ j]; } //每求出一种面额所需的张数后，一定要把这部分金额减去： for(i=1;i<=6;i++) print( B[ i], “----”, S[ i]); //输出币种和对应张数 } 6、设计活动安排问题的贪心算法? 并分析其时间复杂度？ 答：伪代码： Int greedyselector(int s[ ], int f[ ], boolean a[ ]) {int n=s.length; //n活动的个数；a[ ]按活动结束时间递增排序；//便于贪心选择a[1]=true; //活动１被选中 int j=1; //j记录最近加入活动集合A的活动j int count=1; //count存储相容活动个数 for(int i=2; i<=n; i++)//贪心选择从活动j=2…n判是否可加入A { if( 活动i的开始时间，大于最近活动j的结束时间 ) {将活动i加入活动集合A； j=i; //活动i作为最近加入活动集合A的最近活动 count++; } else 活动i不加入活动集合A；} return count; } 程序设计语言： Int greedyselector(int s[ ], int f[ ], boolean a[ ]) { int n=s.length; //n活动的个数 Mergesort (a[ ],f[ ], n ); //按活动结束时间排序，便于贪心选择 a[1]=true; //活动１被选中 int j=1; //j记录最近依次加入活动集合A的活动j int count=1; //count存储相容活动个数 for(int i=2; i<=n; i++) //贪心选择从活动i=2…n判是否可加入A { if( s[ i]>=f[ j] ) { a[ i]=true; //将活动i加入活动集合A j=i; //活动i作为最近加入活动集合A的最近活动 count++; } else a[ i]=false; // s[ i] } return count; } 该算法主要包括２部分： 按照按活动结束时间对活动排序时间，其时间复杂度为：O(n*logn)； 贪心选择时间，其需要经过n-1次的比较（s[ i]>=f[ j]） 时间复杂度为：O(n-1); 故本算法的时间复杂度： O(n*logn＋n-1)； 记为： O(n*logn)。 7、掌握例dijkstra算法的求单源最短路径问题。算法设计？求解过程？答: void dijkstra (int v, float a[][], float dist[]) { //v表示源,a[i][j]表示边i到j的权值 //dist[i]记录源到顶点i的最短路径长度 //prev[i]记录顶点i的前一个点,可以找出最短路径 int n=dist.length; boolean s[ ]; //s[i]标记顶点i是否加入顶点集合s if( v<1 || v>n) return; //源点v不存在 for(int i=1;i<=n;i++) { dist[i]=a[v][i]; //初始化数组dist[i]、s[i] s[i]=false; if(dist[i]=max-value) //源到顶点i没有边 prev[i]=0; else prev[i]=v; } dist[v]=0; s[v]=true; //把源v加入到集合s中 for(int i=1; i int u=v; for(int j=1;j<=n;j++) //贪心选择，计算V-S中顶点的dist[ ]值，选择最小的那个顶点j if( (!s[j]) &&(dist[j] { u=j; temp=dist[j]; } s[u]=true; //源到顶点u的最短路径已经确定，u加入到s中 for(int j=2;j<=n;j++) //根据u重新计算dist[ ] if( (!s[j]) &&(a[u][j]< max-value) //u到j有边 float newdist=dist[u]+a[u][j]; if(newdist dist[j]=newdist; prev[j]=u; } } 该算法主体有两重循环，故该算法的时间复杂度记为O(n2) 8、P126图４－８求最小生成树，写出其prim算法？并给出其选边过程? 答： prim算法描述(伪代码) void prim(int n, float c[][])//c[][]存储边权值 { T=空集； //T表示最小生成树的边集合 S={ 1 }; //S表示最小生成树包含的顶点集合 while( S!=V ) {选择边（i，j），i∈S 且j ∈V-S；且权值c[i][j]最小； //贪心选择 T=T∪ {（i，j）}; S=S∪{ j }； } } prim算法描述(程序设计语言) Void prim (int n, float c[][]) {float lowcost[ ]; float closest[ ]; boolean s[ ]; s[1]=true; //初始化，顶点1加入生成树集合s for(int i=2;i<=n;i++) //初始化，计算与顶点1相邻顶点边权值{ lowcost[i]=c[1][i]; colsest[i]=1; s[i]=false; } for(int i=1;i { float min=float.max-value; int j=1; for( int k=2;k<=n; k++) //贪心选择,v-s中找使lowcost[]最小的顶点k if((lowcost[k] { min=lowcost[k]; j=k; } s[j]=true; //把找到的顶点j加入到生成树集合s中 for(int k=2;k<=n; k++) //根据刚加入的顶点修改lowcost, closest if((c[j][k] {lowcost[k]=c[j][k]; closest[k]=j;} } } 该算法主体有两重循环，故该算法的时间复杂度记为O(n2) Prim算法执行过程： 首先，找出V-S中使lowcost值最小的顶点j(距离s最近的顶点j); 然后，根据数组closest选取边(j,closest[j］)； 最后，将j添加到S中，并对closest和lowcost作必要的修改。 选边过程： 9、P126图４－８，利用kruskal算法求最小生成树，给出其选边过程？ 答：伪代码： void krustral(int n, float c[][])//c[][]存储边权值 { mergesort（float c[][], T[]）; //按边权值排序 T=空集； //T表示最小生成树的边集合 while( |T| {选择最小权值边（i，j）； //贪心选择 if(i∈T1&&j ∈T2) //边(i,j)一端i在T1分支,一端j在T２分支 { union(i,j); T=T∪{（i，j)} } else T=T∪{（i，j)}; } } 选边过程： 第５章回溯算法 1、回溯法基本思想？回溯法解题步骤？ 答：基本思想：在搜索尝试中找问题的解，当不满足条件就”回溯”返回，尝试别的路径。 解题步骤：(1)针对所给问题，定义问题的解空间； (2)并确定易于搜索的解空间结构(排列树，子集树); (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数，剪去无效的枝，避免无效搜索。 2、什么叫子集树？什么叫排列树？什么叫满m叉树？ 答：1）子集树：当所给问题是在n个元素的集合S中找出S满足某种性质的子集时，其相应的解空间树称作子集树。 2）排列树：当所给问题是在确定的n个元素满足某种性质的排列中搜索问题的解时，相应的解空间树被称作排列树。 3）满m叉树：当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合。这类问题的解空间树称为满m叉树。 3、利用回溯法，求解0－1背包问题，要求设计出相应算法？并分析其时间复杂度？ 答：算法描述（递归实现） double knaspack(double p[ ], double w[ ], double c) //c是背包载重 {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //深度优先搜索解空间 return bestp; } double backtrack( int i) //搜索解空间函数 {double n=p.length; if ( i>n ) // i表示深度（层），i>n搜索到叶子节点 { bestp=cp; return bestp; } //否则，进入左子树向下深度搜索 else if (cw+w[ i]<=c) //当前物品放入背包不超载 { cw=cw+w[ i]; cp=cp+p[ i]; c=c-w[i]; backtrack(i+1); } //继续向下深度搜索 else //超载，则回溯进入右子树 if ( bound(i+1)>bestp ) //通过限界函数知道右子树可能包含最优解 //即，当前价值＋剩余物品价值大于bestp，进入右子树 backtrack( i+1 ); } double bound(int i) // 限界函数计算当前价值与剩余价值和 { double cleft = c - cw; // 剩余容量 double b = cp; // 当前物品价值 while (i <= n && w[ i] <= cleft) // 装载剩下的物品 { cleft = cleft -w[ i]; b= b + p[i]; i++; } // w[ i]> cleft 跳出循环，背包装满,物品部分装入背包 if (i <= n) b += p[i]/w[i] * cleft; return b; // 当前物品价值与剩余物品价值之和 } 算法分析： 该算法计算上界函数bound时间复杂度为O(n); 在最坏的情况下，有2n个右孩子节点需要计算上界；故该算法的时间复杂度为O(n*2n) 4、利用回溯法，求解n后问题，要求设计出相应算法，并分析其时间复杂度？ 答：算法描述（递归实现） double nqueen(int nn) { int n=nn; int sum=0; // 放置皇后的方案数 int x[ n]; // x[ i]表示皇后i放在棋盘的第i行，第x[ i]列 for (int i=0;i<=n; i++;) x[ i]=0; // 初始化 backtrack(1); // 深度优先搜索解空间 return sum; } void backtrack ( int t) { if( t>n ) // 搜索到叶子节点，方案数＋1，t是层数 sum++; else for( int i=1; i<=n; i++) // for循环一一判断皇后所在列 { x[ t]=i; // 将第t个皇后放在t行(t不同)，i列 if( place(t) ) // 约束函数，判断是否有冲突 backtrack (t+1); // 放下一个皇后 } } void place( int k) // 约束函数 { for( int j=1;j if( (math.abs(k-j)=math.abs(x[ k]-x[ j])) || (x[ k]=x[ j]) ) //k与之前的皇后1…k-1不能在同一斜线或同一列 return false; else return true; } 算法分析： 对于n皇后问题的解空间共有n!个叶子节点，故排列树最多有n* n!个节点； 最坏的情况下每个节点都要用place函数判断是否可行，每一个节点判断时间为O(n)； 故该算法的时间复杂度记为O(n* n* n!) 第六章分支限界算法 1、分支限界算法的解题步骤？ 答：1）针对所给问题，定义问题的解空间; 2）确定易于搜索的解空间结构(排列树，子集树); 3）以广度优先方式搜索问题的解空间； 4)在搜索过程中用限界函数，剪去无效的枝，避免无效搜索。 2、常用的两种分支限界算法？并说明其思想？ 答：1）队列式（FIFO先进先出）分支限界算法 将活动结点表组织成一个队列，并按照队列先进先出原则取下一个结点作为扩展结点 基本思想： ①开始，根结点是唯一的活结点，根结点入队列； 从活结点队中取出根结点后，作为当前扩展结点。 ②对当前扩展结点，先从左到右地产生它的所有儿子(分支)，用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点队列中。 ③再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。 2）优先队列式分支限界算法 将活结点表组织成一个优先队列（堆），并按照优先队列中规定的结点优先级，选取优先级最高的结点作为当前扩展结点。 基本思想： ①根结点是唯一的活结点，根结点入堆； 从活结点队中取出根结点后，作为当前扩展结点。 ②对当前扩展结点，先从左到右地产生它的所有儿子节点； 用约束条件检查（限界），把所有满足约束函数的儿子结点加入活结点表中（堆），并给每个结点设置优先级。 ③再从活结点表(堆)中取出堆顶结点(堆中优先级最高结点)为当前扩展结点，……，直到活结点表(堆)为空。 3、分支限界算法与回溯法异同？ 答：相同点：都属于搜索算法；都需要在问题的解空间中搜索问题的解； 不同点： 1）求解目标不同： 回溯法求解目标是找出解空间树中满足约束条件所有解； 分支限界法求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同： 回溯法以深度优先的方式搜索解空间树； 分支限界法则以广度优先的方式搜索解空间树。 4、利用优先队列分支限界算法，设计0－1背包问题算法？ 答：队列式分支限界算法（无限界函数） double knaspack(double p[ ], double w[ ], double c) {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //分支限界法搜索解空间 return bestp; } double backtrack( int i) { while (true) //队列不空 { // 检查左儿子结点 if (ew + w[i] <= c) enQueue(ew + w[i], i); // 左儿子加入队列 //进入右孩子，右儿子结点总是可行的，无上界函数 enQueue(ew, i); // 右儿子加入队列 ew = ((Integer) queue.remove()).intValue();// 取队首下一扩展结点 if (ew == -1) // 同一层尾部标记ew = -1：同一层结点处理结束 { if (queue.isEmpty()) return bestw; //判断队列是否为空 else { queue.put(new Integer(-1)); } // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++; // 进入下一层 } } } 队列式分支限界法（带上界函数） double knaspack(double p[ ], double w[ ], double c) {double cw=0; //当前重量 double cp=0; //当前价值 double bestp=0; //当前最优装载价值 backtrack(1); //分支限界法搜索解空间 return bestp; } double backtrack( int i) { while (true) //队列不空 { // 检查左儿子结点 if (ew + w[i] <= c) enQueue(ew + w[i], i); // 左儿子加入队列 //进入右孩子，计算上界函数，检查当前扩展结点的右儿子结点 up = Bound(i+1); if (up >= bestp) //右子树可能含最优解 enQueue(ew, i); //右儿子结点加入队列 ew = ((Integer) queue.remove()).intValue(); // 取队首下一扩展结点 if (ew == -1) // 同一层尾部标记ew = -1：同一层结点处理结束 { if (queue.isEmpty()) return bestw; //判断队列是否为空else { queue.put(new Integer(-1)); } // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++ // 进入下一层 } } } double bound(int i) // 计算上界函数 {// 计算当前价值与剩余价值和 double cleft = c - cw; // 剩余容量 double b = cp; // 当前物品价值 while (i <= n && w[ i] <= cleft) // 剩余物品单位重量价值递减序装入物品 { cleft = cleft -w[ i]; b= b + p[i]; i++; } // w[ i]> cleft 跳出循环，物品部分装入背包 if (i <= n) b += p[i]/w[i] * cleft; return b; // 当前物品价值与剩余物品价值之和 } 时间复杂度分析：计算上界时间为O(n)；在最坏的情况下，有2n个右孩子节点需要计算上界；故该算法的时间复杂度为O(n*2n) 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 一。选择题 1、二分搜索算法就是利用( A )实现的算法。 Ａ、分治策略B、动态规划法C、贪心法 D、回溯法 2、下列不就是动态规划算法基本步骤的就是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 ３、最大效益优先就是( A )的一搜索方式。 Ａ、分支界限法Ｂ、动态规划法Ｃ、贪心法Ｄ、回溯法 4、在下列算法中有时找不到问题解的就是( B )。 Ａ、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5、回溯法解旅行售货员问题时的解空间树就是( B )。 A、子集树???Ｂ、排列树C、深度优先生成树?D、广度优先生成树 6.下列算法中通常以自底向上的方式求解最优解的就是( Ｂ)。 Ａ、备忘录法?B、动态规划法?C、贪心法????D、回溯法 7、衡量一个算法好坏的标准就是(C )。?A 运行速度快Ｂ占用空间少 C 时间复杂度低 D 代码短?８、以下不可以使用分治法求解的就是(D )。?Ａ棋盘覆盖问题Ｂ选择问题 C 归并排序 D 0/1背包问题?9、实现循环赛日程表利用的算法就是( A )。 A、分治策略?? B、动态规划法 C、贪心法??Ｄ、回溯法 10、下列随机算法中运行时有时候成功有时候失败的就是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11.下面不就是分支界限法搜索方式的就是( D )。 Ａ、广度优先?B、最小耗费优先C、最大效益优先D、深度优先 12、下列算法中通常以深度优先方式系统搜索问题解的就是( D )。 Ａ、备忘录法B、动态规划法??C、贪心法???D、回溯法 13、备忘录方法就是那种算法的变形。( B ) A、分治法? B、动态规划法? C、贪心法?? D、回溯法 1４、哈弗曼编码的贪心算法所需的计算时间为( B )。 A、Ｏ(n2n)?? B、O(nｌogｎ)? C、O(2ｎ) ??? D、Ｏ(n) 15.分支限界法解最大团问题时,活结点表的组织形式就是( B )。 A、最小堆???? B、最大堆?? C、栈???Ｄ、数组 １6.最长公共子序列算法利用的算法就是( B )。 A、分支界限法? B、动态规划法? C、贪心法 D、回溯法 17.实现棋盘覆盖算法利用的算法就是( A )。 Ａ、分治法??Ｂ、动态规划法C、贪心法??D、回溯法 18、下面就是贪心算法的基本要素的就是( C )。 A、重叠子问题?Ｂ、构造最优解??C、贪心选择性质??D、定义最优解 1９.回溯法的效率不依赖于下列哪些因素( D ) A、满足显约束的值的个数????Ｂ、计算约束函数的时间 C、计算限界函数的时间?? D、确定解空间的时间 ２０、下面哪种函数就是回溯法中为避免无效搜索采取的策略( B ) A.递归函数?B、剪枝函数? C。随机数函数???Ｄ、搜索函数 21、下面关于NＰ问题说法正确的就是(B )?A NＰ问题都就是不可能解决的问题?B P类问题包含在ＮＰ类问题中?C NP完全问题就是P类问题的子集 D ＮP类问题包含在P类问题中 22、蒙特卡罗算法就是( B )的一种。 Ａ、分支界限算法 B、概率算法C、贪心算法D、回溯算法 2３、下列哪一种算法不就是随机化算法( C ) A、蒙特卡罗算法 B、拉斯维加斯算法 C、动态规划算法 D、舍伍德算法 24、 ( D )就是贪心算法与动态规划算法的共同点。Ａ、重叠子问题B、构造最优解?C、贪心选择性质D、最优子结构性质２5、矩阵连乘问题的算法可由( B)设计实现。 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 算法设计与分析考试题及 答案 It was last revised on January 2, 2021 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算， 此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多 个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些 子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造 最优解； 2.流水作业调度问题的johnson算法的思想。 ①令N 1={i|a i =b i }；②将N 1 中作业按a i 的非减序排序得到N 1 ’，将N 2 中作业按b i 的非增序排序得到N 2’；③N 1 ’中作业接N 2 ’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i 和b i ，且 (a 1,a 2 ,a 3 ,a 4 )=(4,5,12,10)，(b 1 ,b 2 ,b 3 ,b 4 )=(8,2,15,9)求4个作业的最优调度方案，并计算最优 值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2 ’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。 源代码： #include E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进 第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n ; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间） 分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法 ). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法 )之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树 ). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ） 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1] 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai《计算机算法设计与分析》习题及答案
算法设计与分析考试题及答案
算法设计与分析复习题目及答案19874
算法设计与分析课后部分习题答案
算法设计与分析考试题及答案
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
OpenJudge算法设计与分析习题解答
算法设计与分析第2版 王红梅 胡明 习题答案
算法设计与分析试卷及答案
《算法设计与分析》复习题(汇编)
算法设计与分析课后习题
计算机算法设计与分析期末考试复习题
《算法设计与分析实用教程》习题参考解答
算法设计与分析试卷及答案
算法设计与分析复习题目及答案doc
算法设计与分析习题解答
算法设计与分析试题与答案
- 算法设计与分析试题
- 算法设计与分析课程期末试卷-A卷(自测 )
- 算法设计与分析试卷(A)及答案
- 5.《算法设计与分析》试题库
- 算法设计与分析考试题及答案
- 算法设计与分析考试题目及答案
- 算法设计与分析考试题及答案
- 算法设计与分析 期末试卷 A卷 完整含答案
- 算法设计与分析考试题目及复习资料
- 算法设计与分析期末试题考试版
- 算法设计与分析试卷(一)及答案.doc
- 算法设计与分析期末试题_考试版
- 算法设计与分析试卷及答案
- 算法设计与分析试卷及答案.doc
- 算法设计与分析考试题及答案
- 算法题--计算机算法设计与分析期末试题4套(含答案)
- 算法分析与设计试题
- 算法设计与分析考试题及答案
- 计算机算法设计与分析期末考试复习题
- 算法设计与分析考试题及答案-算法设计与优化答案