一、填空题（20 分）
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 算法的思想。
3. 若n=4,在机器M1和M2上加工作业i所需的时间分别为日和b i,
且(a i,a2,a3,a4)=(4,5,12,10) , (b i,b2,b3,b4)=(8,2,15,9) 求 4 个作业
的最优调度方案，并计算最优值。
4. 使用回溯法解0/1 背包问题：n=3，C=9，V={6,10,3} ，
W={3,4,4}, 其解空间有长度为3 的0-1 向量组成，要求用一棵完全二叉树表示其解空间(从根出发，左 1 右0) ，并画出其解空间树，计算其最优值及最优解。
5. 设S={X i,准…，X n}是严格递增的有序集，利用二叉树的结点
来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,(1)在二叉搜索树的内结点中找到X=X i ,其概率为b i。( 2)在二叉搜索树的叶结点中确定X€( X , X+1),其概率为
a i。在表示S的二叉搜索树T中，设存储元素X的结点深度为C ；叶结点(X , X+1)的结点深度为d i，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]= {X , X+i，?…，X}最优值为m[i][j],
W[i][j]= a i-1 +b i+ ? ? ? +b+a，贝S m[i][j](1<=i<=j<=n) 递归关系表达式为什么？
6. 描述0-1 背包问题。
三、简答题 ( 30分)
1?流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为a i 和b i ，请写出流水作业调度问题的johnson 法则中对
a i 和
b i 的排序算法。(函数名可写为sort(s,n) )
2. 最优二叉搜索树问题的动态规划算法(设函数名binarysearchtree)) 答案：
一、填空
1．确定性有穷性可行性0 个或多个输入一个或多个输出
2. 时间复杂性空间复杂性时间复杂度高低
3. 该问题具有最优子结构性质
4. {BABCD}或{CABCD或{CADCD
5. 一个(最优)解
6. 子问题子问题子问题
7. 回溯法
8. o(n*2 n) o(min{nc,2 n})
9. 最优子结构重叠子问题
10. 动态规划法
二、综合题
1. ①问题具有最优子结构性质；②构造最优值的递归关系表达式；
③最优值的算法描述；④构造最优解；
2. ①令N={i|a i=b}；②将N中作业按a的非减序排
序得到N I'将N2中作业按b的非增序排序得到N2'③N'中作业接N '中作业就构成了满足Johnson法则的最优调度。
3. 步骤为：N1={1，3}，N2={2，4}；
N1'={1，3}，N2'={4，2}；
最优值为：38
4. 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),
(1,1,0),(1,1,1)} 。
解空间树为：
n n
5. 二叉树T 的平均路长Pa bi*(1 Ci) +'? aj*dj
i =1 j=0
?m[i][j]=W[i][j]+mi n{m[i][k]+m[k+1][j]} (1<=i<=j<=n, m[i][i-1]=0)
m[i][j]=0 (i>j)
6. 已知一个背包的容量为C,有n件物品，物品i的重量为W,价值
为V，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
三、简答题
void sort(flowjope s[],i nt n)
1.
int i,k,j,l;
for(i=1;i<=n-1;i++)// ---- 选择排序
{
k=i;
while(k<=n&&s[k].tag!=0) k++;
if(k>n) break;//——没有a i,跳出
else
{
for(j=k+1;j<=n;j++)
if(s[j].tag==0)
if(s[k].a>s[j].a) k=j;
swap(s[i].index,s[k].index);
swap(s[i].tag,s[k].tag);
}
}
l=i;// ---- 记下当前第一个b i 的下标
for(i=l;i<=n-1;i++)
{
k=i;
for(j=k+1;j<=n;j++)
if(s[k].b swap(s[i].index,s[k].index); // ---- 只移动index 和tag swap(s[i].tag,s[k].tag); } 2. void binarysearchtree(int a[],int b[],int n,int **m,int **s,int **w) { int i,j,k,t,l; for(i=1;i<=n+1;i++) { w[i][i-1]=a[i-1]; m[i][i-1]=0; } for(l=0;l<=n-1;l++)// --- l 是下标j-i 的差 for(i=1;i<=n-l;i++) { j=i+l; w[i][j]=w[i][j-1]+a[j]+b[j]; m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j]; s[i][j]=i; for(k=i+1;k<=j;k++) t=m[i][k-1]+m[k+1][j]+w[i][j]; if(t { m[i][j]=t; s[i][j]=k; } } } } 一、 填空题(本题 15分，每小题1分) 1、 算法就是一组有穷的 ______ ，它们规定了解决某一特定类型问题的 _________ 。 2、 在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。 3个基 本计算模型是 _______ 、 ______ 、 _____ 。 3、 算法的复杂性是 ______ 的度量，是评价算法优劣的重要依据。 4、 计算机的资源最重要的是 _____ 和 _____ 资源。因而，算法的复杂性有 _________ 和 _____ 之分。 5、 f(n)= 6 皱+n 2, f(n)的渐进性态 f(n)= 0( ________ ) 6、 贪心算法总是做出在当前看来 _________ 的选择。也就是说贪心算法并不从整体最优考 虑，它所做出的选择只是在某种意义上的 _________ 。 7、 许多可以用贪心算法求解的问题一般具有 2个重要的性质： _________ 性质和 ______ 性 质。 二、 简答题(本题 25分，每小题5分) 1、 简单描述分治法的基本思想。 2、 简述动态规划方法所运用的最优化原理。 3、 何谓最优子结构性质？ 4、 简单描述回溯法基本思想。 5、 何谓P 、NP NPC'可题 三、 算法填空(本题 20分，每小题5分) 1、n 后问题回溯算法 (1) 用二维数组A[N][N]存储皇后位置，若第i 行第j 列放有皇后，则A[i][j] 为非0值，否 则值为0。 5 } 2、数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向 右走，一起走到底层，要求找出一条路径，使路径上的值最大。 自底向上递归计算 for(c=0; 1 ;c++) if( t[r+1][c]>t[r+1][c+1]) (2)分别用一维数组 M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子, 有则值为1,否则值为0。 for(j=0;j ) /* { A[i][j]=i+1; 2 - if(i==N-1) else 3 /* 安全检查*/ 放皇后*/ 输出结果； ___ ; ; /* 试探下一行*/ ; /* 去皇后*/ for(r= n-2;r>=0;r--) // 1 3、Hanoi 算法Hano i( n, a,b,c) if (n==1) else {丄 3 ________ , Hanoi(n-1,b, a, c); } 4、Dijkstra 算法求单源最短路径 d[u]:s 到u的距离p[u]: 记录前一节点信息 In it-s in gle-source(G,s) for each vertex v € V[G] oo ； do { d[v]= oo ; 1 } d[s]=0 Relax(u,v,w) if d[v]>d[u]+w(u,v) the n { d[v]=d[u]+w[u,v]; 2 } dijkstr a(G, w,s) 1. In it-s in gle-source(G,s) 2. S=① 3. Q=V[G] 4. while Q<> ① do u=min(Q) S=S U {u} for each vertex 3 do 4 四、算法理解题（本题10分）根据优先 队列式分支限界法，求下图中从v1点到 v9点的单源最短路径，请画出求得最优解 的解空间树。要求中间被舍弃的结点用X 标记，获得中间解的结点用单圆圈O框 起，最优解用双圆圈◎框起。 五、算法理解题（本题5分）设有n=2k 个运动员要进行循环赛， 现设计一个满足以下要求的比赛日程表： ①每个选手必须与其他n-1名选手比赛各一次; ②每个选手一天至多只能赛一次； ③循环赛要在最短时间内完成。 （1）如果n=2k，循环赛最少需要进行几天； （2）当n=23=8时，请画出循环赛日程表。 六、算法设计题（本题15分） 分别用贪心算法、动态规划法、回溯法设计0-1 背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。 七、算法设计题（本题10 分） 通过键盘输入一个高精度的正整数n（n的有效位数w 240），去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案，使 得剩下的数字组成的新数最小。 【样例输入】 178543 S=4 【样例输出】 13 一、填空题（本题15分,每小题 1 分） 1．规则一系列运算 2. 随机存取机RAM（Random Access Machine）；随机存取存储程序机RASP（Random Access Stored Program Machine）；图灵机（Turing Machine） 3. 算法效率 4. 时间、空间、时间复杂度、空间复杂度 5．2n 6．最好局部最优选择 7. 贪心选择最优子结构 二、简答题（本题25分,每小题 5 分） 6、分治法的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题,这些子问题互相 独立且与原问题相同；对这k 个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k 个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。 7、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题,需要依次作出n 个决策D1, D2,…，Dn,如若这个决策序列是最优的，对于任何一个整数k, 1 < k < n,不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前 状态，即以后的决策Dk+1, Dk+2,…，Dn也是最优的。 8、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索, 解为叶子 结点。搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到上层父结点,继续下一步深度优先搜索过程。在回溯法中,并不是先构造出整棵状态空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造。 10、P（Polynomial 问题）：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性 问题。 NPC(NP Complete)问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。 三、算法填空(本题20分，每小题5分) 1、n后问题回溯算法 (1) !M[j]&&!L[i+j] && !R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0 (5) M[j]=L[i+j]=R[i-j+N]=0 2、数塔问题。 (1)c<=r ⑵ t[r][c]+=t[r+1][c] (3)t[r][c]+=t[r+1][c+1] 3、Hanoi 算法 (1)move(a,c) (2)Hanoi(n-1, a, c , b) (3)Move(a,c) 4、( 1)p[v]=NIL (2)p[v]=u (3)v € adj[u] (4)Relax(u,v,w) 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 27 8 5 6 4 3 2 18 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 四、算法理解题(本题10分) 五、(1) 8天(2分)； (2)当n=23=8时，循环赛日程表(3分)。 六、算法设计题(本题15分) 8 7 6 5 4 3 2 1 (1)贪心算法 O ( nlog (n )) 首先计算每种物品单位重量的价值 Vi/Wi ，然后，依贪心选择策略，将尽可能多的 单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品 总重量未 超过 C ,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策 略一直地进行下去，直到背包装满为止。 具体算法可描述如下： void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort( n,v,w); int i; for (i=1;i<=n ;i++) x[i]=0; float c=M; for (i=1;i<=n ;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } (2)动态规划法 0( nc) m(i , j)是背包容量为j ,可选择物品为i , i+1 ,…，n 时0-1背包问题的最优值。由 背包问题的最优子结构性质，可以建立计算 m(i , j)的递归式如下。 max{m(i +1, j), m(i +1, j -wj m(i 1,j) ( 3)回溯法 O(2n ) cw:当前重量 cp:当前价值 bestp ：当前最优值 0-1 m(i, j)二 j -W i 0 _ j ：： w m(n, j) V n 0 j -w n 0 乞 j ：： void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=mi n(w[ n]-1,c); for (j=0;j<=jMax;j++) m[ n][j]=0; for (j=w [n ];j<=c;j++) m[ n][j]=v [n ]; for (i=n-1;i>1;i--) { int jMax=mi n(w[i]-1,c); for (j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for (j=w[i];j<=c;j++)/*m( n,j)=v[n] j>=w[ n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } /*m( n,j)=0 0= /*m( n,j)=v[ n] j>=w[ n]*/ /*m(i,j)=m(i+1,j) 0= void backtrack( int i) // 回溯法i 初值1 { if(i > n) // 到达叶结点 { bestp = cp; return; } if(cw + w[i] <= c) // 搜索左子树 { cw += w[i]; cp += p[i]; backtrack(i+1); cw -= w[i]; cp -= p[i]; } if(Bound(i+1)>bestp) //搜索右子树 backtrack(i+1); } 七、算法设计题（本题10 分）为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一 个使剩下的数最 小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s 次，剩下的数字串便是问题的解了。 具体算法如下： 输入s, n; while ( s > 0 ) { i=1; // 从串首开始找 while (i < length(n)) && (n[i] delete(n,i,1); //删除字符串n的第i个字符 s--; } while (length(n)>1)&& (n[1]= ‘0') delete(n,1,1); //删去串首可能产生的无用零输出n; 算法设计与分析考试题 及答案 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. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< 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算法的思想。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 习题 1 1.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707— 1783） 提出并解决了该问题。七桥问题是这样描述的：北区 一个人是否能在一次步行中穿越哥尼斯堡（现 东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区 的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草南区 图。请将该问题的数据模型抽象出来，并判断图七桥问题 此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1，一次步行 2，经过七座桥，且每次只经历过一次 3，回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个 奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到 r=0 m=n n=r r=m-n 3输出 m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代 码和 C++描述。 编写程序，求 n 至少为多大时， n 个“1”组成的整数能被2013 整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n 至少为 :"< 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(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、二分搜索算法是利用（ 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 ）。 HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型: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、二分搜索算法是利用（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 ）是贪心算法与动态规划算法的共同点。 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 华南农业大学期末考试试卷（A卷） 2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log2n C．2n2 D．3nlog3n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌 的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法 对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6. 有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下 说法不正确？ A ．让水桶大的人先打水，可以使得每个人排队时间之和最小 B ．让水桶小的人先打水，可以使得每个人排队时间之和最小 C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水 D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分 别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A ．问题规模相同，问题性质相同 B ．问题规模相同，问题性质不同 C ．问题规模不同，问题性质相同 D ．问题规模不同，问题性质不同 9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图 B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n! B ．2n C ．2n+1 -1 D ．∑=n i i n 1 !/! 答案：DACAD CACCB 第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 （3 ）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.（1）当1n ≥时，225825n n n -+≤，所以，可选5c =，01n =。 对于0n n ≥，22 ()5825f n n n n =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n n n n n -+≥-+≥，所以，可选4c =，08n =。对于0n n ≥， 22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。 （3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可选21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥， 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 一、填空题（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 Ex.1(p20)若将y ← uniform(0, 1) 改为 y ← x, 则上述的算法估计的值是什么？ 解：若将y ←uniform(0, 1) 改为 y ←x，此时有 ，则k++，即 ，此时k++，由于此时x ← uniform(0, 1)，所以k/n=，则此时4k/n=2。所以上述算法估计的值为2。 Ex.2(p23) 在机器上用 估计π值，给出不同的n值及精度。 解：由ppt上p21可知，的大小 ，其中k为落入圆内的数目，n为总数，且π=，即需要计算4k/n。我们先令x ← uniform(0, 1)，y ← uniform(0, 1)。 计算的值，如果小于等于1，那么此时k++。最后计算4k/n的值即可估计此时的π值。代码的主要部分为： 执行结果为： 结果分析：随着N的取值不断地增加，得到的π值也就越来越精确。 Ex.3(p23) 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。 解：的值为y=，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道= k(b-a)d/n。其中k是落在函数y=，x=a，x=b以及y=0所包围区间内的个数。 代码的主要部分为： 运行结果为： 结果分析： 随着N的取值不断地增加，得到的积分值越来越精确。 Ex4(p24). 设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorMiss算法返回的值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| < ε] ≥ 1 –δ 上述的意义告诉我们：Prob[|h-I| ≥ε] ≤δ, 即：当n ≥ I(1-I)/ ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 () 解此问题时可用切比雪夫不等式，将I看作是数学期望。 证明：由切比雪夫不等式可知： P( | X - E(X) | < ε ) ≥ 1 - D(X) / ε2 由题目知，E(X)=I。且根据题意，我们可知，在HotorMiss算法中，若随机选取n个点，其中k个点在积分范围内，则 。且k的分布为二项分布B(n，I)（在积分范围内或者不在 积分范围内），则 。又因为k=x*n，所以D(X)=I(1-I)/n。再将E(X)和D(X)带入切比雪夫不等式中即可得到 Ex5(p36). 用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。 解：由题知，集合的大小，通过计算新生成的集合中元素的个数来估计原集合的大小，代码的主体部分如下：算法设计与分析考试题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
算法设计与分析习题答案1-6章
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
算法设计与分析习题答案1-6章.docx
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
算法设计与分析课程设计(完整版)
算法设计与分析试卷及答案
计算机算法设计与分析习题和答案解析
算法设计与分析期末试题答案解析
2009.1算法设计与分析报告课程期末试卷-A卷(自测 )
算法设计与分析C++语言描述(陈慧南版)课后答案
算法设计与分析试卷及答案.doc
算法设计与分析试题与答案
算法设计与分析
相关主题
文本预览