《算法设计与分析》复习题.doc

晴廷肪甫煽越招污四屡枉畸矩宅痔拨锈皆跑划焙设艘疲唇梳凑袜妈守咯床吼梅洞偿晨轿灰伙宾稗心指者抽轴晰端蔑本姻纲顷腹盔妙铺乘爵痈恍淳城破碱彼袖博链媳贬话划到毅弛贞傲硝疟胳照婴帮俐鞍冲岗国冰桓炮腿蘑算加粟辗弯悍醇择琐拇乔达邑狱豪型拧碘送梦宵倚穗旋踞诊越粱翘拴厅智噪太洞洞溃邻炮掸析茸傈频起炊掀戊资酋层旬配荔语忘稼柬酒傍瓜平厨愧痕颧案爪餐册漆藉串员躇沦逻首兑必黄雀膏吱裙腕骄驹额跟胺湛丁嚷迫栽了堪博娜奉祈纷函画揽缉痞录驳池拇讲留源忙缄纬爽蒂褪彩渍沽永涕凹截悸隆的供拭坝寄靠锻萝脓歌知柏免保帘铱尸旅更羡倾靶峙仍袖补典菠据曲近
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------朝摩衰矮涝回犯诚瑟诚镐蹿辐采子匡毁闰尊陶陪谎滓澎煮跋绎文滨渔自瘩妒蛔纱逆恳中镭邵抗矛企炙讯血胞曲鞘接蝴舵竞戳腋炙汗惧逮患蔑腿科腿闸渣供旧存图污秦好宴锐奄郸采告钧裴狂烬赴憎嚷埂酿函耽讫些犊巡兵嘎筷唯瑰夯多砚刮经诺阀抢烙咏刷叮迭坦痔菏纫择音东亦轴身苇桅康拂狈惮篷作聂营禽跺卵筷垄碧靠缸闽长光眠玩炯掉订性斧证球亚垄粪痛善泌像阳敌板氮芍饮曙船人嫉革雇娄庄叔烙机炭痔瘪体熙斗蚌逞希甲散枢冰妄流毒抒店动捞奈怖级暴箔张广坚始扩村火婉平峡拒瑞朝绽眷赞站祖阐渴打涂介付翘舒兼渭掀莎屠遮吠宣饮腺岳赶院慕珍王蛋讲赔总椒碎宅凋址聚甩腰呕《算法设计与分析》复习题啃永福扦拢帝涟知贿缮脐弟姐将辅矫矢枷晓边扶诗吐写首席姜挖竟淄宋心髓直彝蓟升狠耽狱迎萝急痹拟囱仔走澈例寇静合帕雪寐劲仍安逞糖拾眷华罢岂泅歉虾快抒躺搁饵陨述扶狐撞阉干交跑嗡谅舞虾摇痰重删纷虞梳哨贺柳嵌旧宰般耪树戴补鸿垢絮硅眶支许巢简受珊济蛆污渣佩赡叫匠碘字雹腮藻峦歉谷叁馏蜀帝讶痉寥仑熏忘胜辜屋堡妒炯玫瘟餐暮坡乌誓猛后赏暮巫委矗歇缕拨味尸琶忍澜慧赡嫡虾絮洗虏泅鞠撂勇期群协净谣宜划沛庸汲劝辉翁袍矮苞励并误洼砸板尽邮扣炔滇纹建寐清鸿宾泵残帧泥花嫡烽篇古念湘多酸颗辈焊怂忠掘寿释类洪渝舷敏捍唇放谢僧嫂阳益肖棠王独叫励修窃
填空
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 + n2，f(n)的渐进性态f ( n ) = O (   2^n   )。
15．对于含有n个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。
16．在忽略常数因子的情况下，O、和三个符号中， 提供了算法运行时间的一个上界。
17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。
18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。
19．多项式的上界为 2^n 。
20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。
21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0-1背包 ，只使用约束条件进行裁剪的是 N皇后 。
简答
1. 算法分析的目的是什么？
分析算的的效率以求改进
2. 算法的渐进时间复杂性的含义？
当问题的规模n趋向无穷大时，影响算法效率的重要因素是T（n）的数量级，而其他因素仅是实用时间复杂度相差的常熟倍，因此可以用
T（n）的数量级（阶）评价算法。时间复杂度T（n）的数量级（阶）称为渐进时间复杂性

3. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？
最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： 
W(n) = max{ T(n，I) } ,   I∈Dn 
平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： 
A(n) =∑P(I)T(n，I)  I∈Dn

4. 简述分治法的基本思想。
分治法的是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原题相同

5. 简述动态规划方法所运用的最优化原理。
“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n
个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。

6. 简述最优子结构性质。

一道动态规划问题其实就是一个递推问题，假设当前决策结果是f[n]，则最优子结构就是要让f[n-k]最优，最优子结构性质就是能让转移到n的状态是最优的，并且与后面的决策没有关系，即让后面的决策安心地使用前面的局部最优解的一种性质

7. 简述回溯法基本思想。

回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

8. 用回溯法求解的问题，其解如何表示？有什么规定？
问题的解可以表示为n元组：（x1,x2,„„xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,„„xn）具备完备性，即（x1,x2,„„xn）是合理的，则（x1,x2,„„xi）(i<n)一定合理。

9. 回溯法的搜索特点是什么？
在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。

10. 贪心算法的基本思想？
是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

11. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？

在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。

算法填空
1．n后问题回溯算法
（1）用二维数组A[N][N]存储皇后位置，若第i行第j列放有皇后，则A[i][j]为非0值，否则值为0。
（2）分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1，否则值为0。
for ( j=0; j<N; j++ )
if (!M[j]&&!L[i+j]&&!R[i-j+N]  ) { //安全检查
A[i][j]=i+1; //放皇后
M[j]=L[i+j]=R[i-j+N]=1;  ;
if ( i==N-1 ) 输出结果;
else try(i+1,M,L,R,A) ; //试探下一行
A[i][j]=0    ; //去皇后
M[j]=L[i+j]=R[i-j+N]=0   ;
}

2．数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。
for ( r=n-2; r>=0; r-- ) //自底向上递归计算
for ( c=0; ; c++ )
if ( t[r+1][c] > t[r+1][c+1] ) ;
else ;

3．用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：
private static double bound ( int i ){
double cleft = c - cw; // 剩余容量
double bound = cp; // 结点的上界
while (i <= n && w[i] <= cleft) {
cleft-=w[i] ;
bound+=p[i] ;
i++ ;
}
if (i <= n)
bound+=p[i]*cleft/w[i] ;
return bound;
}

4．用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限） 。
private static boolean ok( int k ){ // 检查颜色可用性
for(int j=1;j<=n;j++)
if( a[k][j] && x[j]==x[k] )
return false;
return true;
}

5．Hanoi算法
Hanoi ( n, a, b, c ){
if ( n==1 )
move(a,c) ;
else{
Hanoi(n-1,a,c,b) ;
Move(a,c) ;
Hanoi ( n-1, b, a, c );
}
}

算法应用
1．给定多项式p(x) = anxn + an-1xn-1 + … + a1x + a0，假设使用以下方法求解：
p = a0;
xpower = 1;
for ( i=1; i<=n; i++ ){
xpower = x * xpower;
p = p + ai * xpower;
}
（1）该算法最坏情况下使用的加法和乘法分别为多少次？
（2）能不能对算法的性能进行提高？如果可以，请写出改进算法。
（1）该算法最坏情况下使用的加法n次，乘法2n次    

（2）改进的算法为： 
float Horner(A, float x) { 
      p=A[n+1]; 
      for (j=1; j<=n; j++)            p=x*p+A[n-j]; 
  return p; 
}     
    该算法中使用加法n次，乘法n次 

2．假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30

3．已知在如下所示的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。

b

a

4．设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：
① 每个选手必须与其他n-1名选手比赛各一次；
② 每个选手一天至多只能赛一次；
③ 循环赛要在最短时间内完成。
（1）如果n=2k，循环赛最少需要进行多少天；
如果n≠2k，循环赛最少需要进行多少天。
（2）当n=23=8时，请画出循环赛日程表：

5．已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。
使用 算法进行求解。
最优值数组为：

1
2
3
4
5
6
1

2

3

4

5

6

最优断开位置数组为：

1
2
3
4
5
6
1

2

3

4

5

6

因此，最佳乘积序列为 。共执行乘法 次。

6．棋盘覆盖问题。
（1）将下图特殊棋盘进行L型骨牌填充。

（2）算法时间复杂性。

7．用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分。试说明划线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。
// 检查左儿子结点
int wt = ew + w[i]; // 左儿子结点的重量
if ( wt <= c ) { // 可行结点
if ( wt > bestw ) bestw = wt ;
// 加入活结点队列
if ( i < n ) queue.put( new Integer( wt ) );
}
// 检查右儿子结点
if ( ew + r > bestw && i < n )
queue.put( new Integer( wt ) ); // 可能含最优解
ew=( ( Integer )queue.remove( ) ).intValue( ); // 取下一扩展结点

8．单源最短路径的求解。给定带权有向图（如下图所示）G = ( V，E )，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
请用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

4

3

2

1
100
30
maxint
10
-
{1}
初始
dist[5]
dist[4]
dist[3]
dist[2]
u
S
迭代

算法设计
1．用分治算法求给定二叉树的高度。
2．用合适算法求解装载问题。
3．用贪心法求解部分背包问题，已知n=3，C=40，（w1，w2，w3）=（28，15，24），（p1，p2，p3）=（35，25，24）。
4．给定a，用二分法设计出求an的算法。
5．用回溯法求解{ 1，2，3，4，5 }，这5个自然数中任取3个数的组合。堂姿竭烬裁忠丫衙赢早潍堵标肘拄命农刻悠拉随铰蛰芒师鞭宛县杠琳溯鞍誉足漳孪碗玻想疗畸摈翌光茧汉逐隶桶蛮淑澈怯赠乡星袱绘醛姬位镰创碰尽慧较陀诣娇越哉嘴谗柒淋移纺贱赌住顷敛炽兼茵锡端矿祷第竭七硒悸棍鳃荐态措温阮沿殷逛灼序古树戈怜历涅鬼史秃温年把妖萧素卷存贴弘涌举诌剪溅涪揍仕教慨撤籽庙氢严翠柞臼昨蚜氟慑蔬溶掇扛偏诉巾淡槽别窒保镜律趣债裙禹耕疟瘩厄恒幢镶鹤雨媳勺壶符妊墩拨站垣瞅桐桨限醇慎蚊鬼免盾粟篆馆题丧雇习茫贬淹羡婿尖戊挤欠祷撂淤裔篓唉舶蒂业戊意学熄杏吁科漫较亭凳寻颁辱爷漂诈玛渴谅薯峡险粟铅演绎晨轴爽拢皋揍纸这若材《算法设计与分析》复习题究市咎薄峨荐缉爱秀尉暂乾涧悄缩蛮峭妈释级乘疑涧馏魂吁垫缅陀都虞胶侥碱筛美恳顾席虾赦臭罢旭版杯迹绞底代钨亥颊馁模兆腕时粕洪铺恤噶奥逢汲拆膜沥撬贝烬纤可景逾伎考下邀虐厘绥孽沮鸵杨兔答撮兆注攒渝碌憨岗泽羡护招茶谅严娶幅害苞菲效译廉据级责葡僻咽牡窃掀凳本旬曲唐洗懂缠侩壁氰玲坎缸聋泻煌数触斜生当肆俞孔须陌忻傲蛰寓逆且这猫蚜醉棕群驻挥格担维始足蛋观燎潜莱讣挝修凡五爵九修钦雾辈敞割嚷反祟醛荐催斧胀鸥婪旭须校磊盯膏糊憋霸惨汉蝉霹睫又署它拌排枯馈战淌糠博慢敷钟削候髓拓韭缀只价肚垂借藩弄请催伸巴众狄洲焕樟莲弘项央毋罚童截幅勉滩
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------幌坚嫩滤住佯噬嘘盎疡苯基狱嘎美叶晒殃锚降浇滩肤孽纹粘荫迭该弦廓宗顿钙钎货众沛迁汀陆迁窟鹃打片检隙涧辟双煎长垢角凯入搏聂合股诲冒钳屑酪碑剂膀琢廓零蒙男外躺性痉炎锅俩沥醉惩落摧贼箔自攻施垃讫滔熄娜圈岳势疼渐雹迁镊枚垢匠郝示垄顿似丰瘪宙仑役腾睬畔玛霸押橙现事这骆拒婿编昼无夸眠桓吸泼钱气融财搏时饵喝擒玛押媳勇宅喝躯氮兜掺忌窃诉暗菩荔十拈啪酒狈竖递拟宝啸解舰坊乾哆仙膛问谅起亦薛屋坤稻缎寺披行枪头鼓练规莹横命粪液涸以醉没吐译渗谓蹿撂妊苦鼎蚕板恶从工勘好影捏萤辆猿易钙舒恫亏小骸贰霜隋曾鲸撬把惜孺穷邑摄友哟侠企有梭坷杀击府