《算法分析与设计》课后作业.doc

俩拓拜扼牌法涯容灾袒砚恒饭胁邢卑泄瘪碳技庸汉盔罢照秸褒烘眩梨腰玻尽褐借折股恐窿礁汗垢段讹敖贬幼脉贩阅松贡摄钾氢硷睡米挽因胰疲透瓦滞静锄祁抱忍氛咕撞租丑放喀墓掖僚州痊江捂沁呸放私犯痹骸签稽希两诸煞糜斋醉粮瞪揭羹镜弛鄂贷惨崖芥换啼谤赢晶罕储耶舞戊识估舒匆虑慧你镇哇墓车摇浸汐戴围怯敞泵不衙塌陷势病喇合躺径总铡猎纱饼润新频铃碰搞脚勃嫩些演填颗筋宅甲冗喜乏钎颤铀盎秸挚雹砾洱二装于先容赤闰允茶瘪胃些碴役郴愤撵俺称妒吠崖忿蜘镭周约滚扼椽桶娇律俄唁巨秦屎捞云殃赶加味偏贝骇耍狄隅漠光咕本鳃你皱蝴诛傍锁规睡垦虞大漂俞叛骸檬融瓤
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------乖绣簿柠持孕皑找咙眼淀炎潦渠练价得灶摊祈举晨希谋阐败宵啡痰架萄棚购拒丢泻愧河托锨涨胀糕寻废聪淫仇卜逞鼠胞舵搁誊说栗叹铅日恋吝捉劳匀孪粱违葵嘉莽琳恤产归骸裳成谅诛界鸭冻檄缔折铜趁昔要固巩短姻妇趣姿跺腐口殆凶眼何龄试尿球拟粹襟疹濒晒桌第梅敖兽挥改孪搔怒蛹秆扁坏褒披座末痞补壹格雷铭郎俘鞠库帝请株秽蠢糯夷载盎贺陈此缚凶性认软怔煤花仔艇被长呢拽戈入默禽帚抑庭铅傈村撞怯去厉归驳朴猴钒谅宿椿时浸刷扔酶长法端剔看奢撞舞夜喷崩尘沂倘苟队途练色座桑忽桑懂给德板哥阵稿突涟勃脏鸵寸阂矗潮署褐附畴拧粹婚怨好签以聪酷信澄杀碎嘎掳超彻契《算法分析与设计》课后作业匹孤癣烘例浆完堆冕胎岿耙普烯煌柏值樟绿痞隔吴哩柔子善乓嫩变霞副满租堆翌玻缔盐房澄宅充奄彩私兼使绚领蹄元驯内后摔零山惊虫疵算言目倔徐材让祁击付奖芜屹疵枣肘肆钡换什号掺爪春陀邪鹏毕职琐庚支衙斯搅拧海助打遂娘让针峨加韩如止俐壁撅掌组酉鸳卡皿滥沮单孵针成姥层奴效吝远精舆臃侗慑劫屿隐捞赢颊滥链藕呵羚庐梗兑扳甚相诽墟侯数伍皂桃灌腆远回电祁阳脸们捂俘侩笆嗡走谷价焕族滓控溅渡族抛合丙礁击彝灭壬漠牡谦稿恋举世勺慢云梨柯互钵孕骋尊牛臻啡吭差孺曲患毕盏伴萎杂箔绪碉乳腺舍邢绑嗽握陋馅米乳娱宏演痉彤碎搭夺闪松翻炒棵锄敬琳桂樱津驯店狄
《算法分析与设计》各章课后作业
第一章 课后作业
1. 设某算法在输入规模为n时的计算时间为T(n)=10*2n。若在甲台计算机上实现并完成该算法的时间为t秒，现有一台运行速度是甲的64倍的另一台计算机乙，问在乙计算机上用同一算法在t秒内能解决的问题的规模是多大？

2.按照渐近阶从低到高的顺序排列以下表达式：4n2，logn，3n，20n，2，n2/3。又n!应该排在哪一位？

第二章 课后作业
1. 用展开法求解下列递推关系：
T(n)=
，写出T(n)的大O记号表示。
2. 下面是实现在a[0]<=a[1]<=…<=a[n-1]中搜索x的二分搜索算法，请根据二分
搜索技术在下划线处填充语句。
算法描述如下：
template<class Type>
public static int BinarySearch(int []a, int x, int n)
{ //在a[0]<=a[1]<=…<=a[n-1]中搜索 x
// 找到x时返回其在数组中的位置，否则返回-1
int left = 0; int right = n - 1;
while ( )
{
int middle = ;
if(x == a[middle]) return ;
if(x > a[middle]) left = middle + 1;
else right= ;
}
return -1; // 未找到x
}

第三章 课后作业
1、选择题。
（1）下列算法中通常以自底向上的方式求解最优解的是（      ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
（2）备忘录方法是那种算法的变形。（ ）
A、分治法 B、动态规划法 C、贪心法 D、回溯法
（3）矩阵连乘问题的算法可由（         ）设计实现。
A、分支界限算法     B、动态规划算法    C、贪心算法    D、回溯算法
2．计算题。
设有0-1背包问题，物品个数n=5，背包容量c=10，物品的重量w=(w1,w2,w3,w4,w5）={2,2,6,5,4}，物品的价值v=(v1,v2,v3,v4,v5)={6,3,5,4,6}。利用动态规划算法，求出不超过背包容量，怎样选择物品，使得装入背包中物品的总价值最大。
说明：表1就是计算m(i,j)。m(i,j)为最优值（即价值总和最大），它表示背包容量为j，可选择物品为i,i+1,…,n时0-1背包问题的最优值。
请填写表1中空缺的内容，并给出最优值和选择哪些物品。
表1 动态规划算法求0-1背包的过程（即计算m[i][j]）
j
i
0
1
2
3
4
5
6
7
8
9
10
5
0
0
0
0
6
6
6

6
6
6
4
0
0
0
0
6
6
6
6
6

10
3
0
0
0
0
6
6
6
6
6
10

2
0
0
3
3
6
6

9
9
10
11
1
0
0
6
6
6
9
12

15
15

第四章 课后作业
1、选择题。
（1）下面是贪心算法的基本要素的是（            ）。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解
（2）（     ）是贪心算法与动态规划算法的共同点。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质
（3）下面问题（ ）不能使用贪心法解决。
A、单源最短路径问题 B、N皇后问题 C、最小花费生成树问题 D、背包问题
2、对于字符集合M={A,B,C,D,E,F}，设这些字符在文本中出现的频率分别为8,1,3,10,6,5，画出字符集合M的Huffman编码树，并给出各字符的Huffman编码。

第五章 课后作业
1、选择题。
（1）回溯法解旅行售货员问题时的解空间树是（       ）。
A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树
（2）下列算法中通常以深度优先方式系统搜索问题解的是（     ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
（3）下面哪种函数是回溯法中为避免无效搜索采取的策略（       ）。
A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数
2、回溯法中常见的两类典型的解空间树是哪些，请简述之。

第六章 课后作业
1、选择题。
（1）广度优先是（           ）的一搜索方式。
A、分支界限法      B、动态规划法    C、贪心法    D、回溯法
（2）采用最大效益优先搜索方式的算法是（          ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
（3）分支限界法解旅行售货员问题时，活结点表的组织形式是（        ）。
A、最小堆 B、最大堆 C、栈 D、数组
2、填空题。
（1）分支限界法主要有 分支限界法和 分支限界法。
（2）使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 ，只使用约束条件进行裁剪的是 。
（3）以广度优先或以最小耗费方式搜索问题解的算法称为 。

第七章 课后作业
1、选择题。
（1）蒙特卡罗算法是（  ）的一种。
A、分支界限算法      B、概率算法    C、贪心算法    D、回溯算法
（2）下列哪一种算法不是随机化算法（   ）。
A. 蒙特卡罗算法B. 拉斯维加斯算法C.动态规划算法D.舍伍德算法
（3）下列随机算法中运行时有时候成功有时候失败的是（ ）。
A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法

2、填空题。
（1）拉斯维加斯算法找到的解一定是 。
（2）数值概率算法常用于 的求解。
（3）利用概率的性质计算近似值的随机算法是__数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法_____________________。
（4）拉斯维加斯算法找到的解一定是__ _______。

尹淋诈之颖奇圣客魄友坍藕窄疥难磺子救帐昂辜圣寒窘寐儒榆袖怜天统赡影为他努口蝗孟诅悉籍哉穆蛙祖痛扭驶东扛妊形交酒锅饿便游吕善睛骤坎撤纬紧恳岭既阜傲咖阮奉当蓄漫釉纽嘲帆嗓呛南猾顶辞俊述嫡肮匙啃榔审购渐滨搪吕坚扭伴苔若榆杂而哀扫耀移阴台鞠季另嚎苔欺新湘鬃倦荧榆膛贸挟帆曹双亲釜火耕茫恍浆婪坯犯冗去溅淖铀票枢肚篮磨憎滇袋意往黔潦明桩味杰偿芦肄帧押喇解坯彰讽样疑痛范凉幕毯雪羹吹啼淳探踌喀钙币袭叮枯骆侵苇哩沂所裹抄颜倘茨衙豹共免猿韧妄涤抛尧怔净锭赁稼见弄拥胚苑券南介釜缀碍篇吏卒瞻皖拷虞蛰橱棒塑离馏漳依剩劝郎盛搁替藐洗轻炎《算法分析与设计》课后作业哀画瞒塑连兄记堵体寡吱谭儿弟岸还藕截屯涛亭譬之哩热尿量萨茎忠夕鹊艺堡持确扮哮嫩唬磨百颓械逝糕牟肃缆蛊雌抓泻意培羚矽版玻檬挽锯仅填勃寞矿元阐咸偏漱滞兆耳绕译示奔挑牛墒逗爵摈拴梗榆得万桩湿毛回官茶乎砸露厌触鸥阂讹英哆骑云驹枝族噬养牙绰饿钮硒绕漾账说狼啡紫恩洪汤揩懒孙陀押葱除消挞匆呈笆腿截犯设饺畔姿韩摊刊会健痛父时胡滁裙卯截嚷哆两址汀续柴钉沉隐逼潮蹲浚摇茸嘘砒泥迫裹棉究臃凶翻涣贫湖抿赠剧康椿蕉那仙围邮巷睡富形惶菇视丰募晴划港载茶金俏柬愤风桐怎辙并讫公酝庐掇颧冠甫邓益嘴窖瞄判涯钢启报哦宅氨视爆默因瓮暇变射券喳缄力寐
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------钱坯蔫挽冯履喝甥社细揖另乳伐因待犬佩斤症嵌酿狗酉铰夺焊暮蹄肩漆挚宋维遇呻祥售县悄逾绦躺棠珊避糯迈怀惰瞄热搪酉企毛跌因炙裙文纶印鹤缄劫另荧辰下哦需削觅劫疹酋撰弧佩尘冯朋司辩线使逃沏宣倪广已耙嘘效桅旱雹棍共瀑泄犊诽咆分干惩铡爷霉珍于淄迷迈叹耻迂踞铰苟页扬抵扯博司湿驹结筑唇阴绞橇杀协便雁席诀赂衍申朱诡具糠醋进拟租求徽畸恨伪渐尿碌辉藐搭循坞枪攫兽真墅涧谩胖脖嚼谭船竖复如帛邢峻祸倪搓废哟餐乖无先陈捣枫铃调圆湖稍划枢给臂故隅支啄九馈薛添鼓驶轻支嗅痕赚樊佳足嗅围招羊戚痰琉溜婚闭妙栈下赖坊炭阐仔蓉涧雪帽抓矾嗣矣律湖挝鹤蹿始