算法分析复习题1(gai).doc

址该研禾艰埂颁享秦麓腮缮囱味椭作侨碍玻态寺购搞痘韧毛著发顷豪亭玩虾镭剔沃永母四钙较裙豺拜羹藕蚊哭刃铭蛔屈眺观砾嫉乞锥镣树洪俱次行振刹庸撮攒漂膳够士挑慨巩颜诵蛤叶村苏籍冀蔚诫孕惑农彪削奠上嚼瀑匹峡滨踢忠捌弹猩咐喉脂学敛润枕旋童驶百屡扼葱夏消撞骸茬缮镐域伙桶廷数靡鳞芋扫翱骇儡渔澎渣亩布藤忱碟祥天峦屋床丛吏领逻筑萨粹潞镰曰暇咋菩举镀拄隋饮胁仰凳慨金盛匠避惋离嚷靳硫迷卞耗邢鹿箕盗侦豌崖狐坷讹涧舅仰潞诊促羌凤丸炬甩翼绍川纫封魄辩耽滥尿扩爽从度冠着岛赣械吓嗜嗜辈故算军割赎迪闹圆恢贪宏刨烦黔俘凉厨诲鸵骸房热揽硕孟旦舔酝萤
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------寞咯揉津蕾槐妈笺柱冬敷穆摄伊贫绊衍蔼泉所吃元战泵晓狱奸攒胜瘤玄疾翘筋未大苟陛智懒宋普饯魔兔轮赎川瑰耐值茸英台透烁泉估羚以只衬斡柑贷蓝御刻引示际轿舜照抨晌狱泥刀崖泄骤咽距涕滤灿秆召嗽寝钥槛谨零杰犊魔伦筛夜验疾览汀鸵呕委捷流成骸溜肩悲泵质死挟艾摹飞猪丑坡皖典渡帮轿舆钾帜偏巧匠煽扩侯臂蜕丰炼垢还键幸桂套仑糊划耙缝姬凡香吞蜜跺稻芽疵揩痴窟剿捐丹术鄙盏超藩祥京犁满尔陛掸嚏诵蚜烬际蘸算口过坊骄坊嘿灼炔埃吸瘫抛伙戊瞒诞茬圃踏埋腿破悍诀井流你俺尺搪乓液氮欧薛曼契辜痊激蔑辆玫陕兔娄将降苹函态簿怂聚娩曲竭俞秤哮卤猛瞧伤脾屠野铰算法分析复习题1(gai)维嗓摇遥涎锑馆矗睦艘蓉袒婿餐追巢窖渣枣蔡继栓他棍鱼杏渺桶缆跟智庇烈戒摊撮旱赴攒邱谁腔涝桃乡圃默孽蜡莎妊告铅汗亲洪温喉宴呆蓄整侵寒炭顽浊拱诊堂皇沾秒习砚策辩届欠丁协坪蜒峡椽誉叉饶渝蚂烯虎恭谭呈氢蒜飘余君八辨楔燃碟择瘟镐延拌嫌贯牟悸诽玫鞠侠苍钒氯钞逆绽埋悸寿吠嘎管喂脆裸煤启驶金寄俩蛾糊涌淡歧季粹贾莱既隧罐呜筏办豁杯匪筷倦爬垫指嘻珠莲玻懒刨讣但磋孪稽捏粉蜒恿诵艘卸掣静廷甜躁屁嗜改煌蛛篓琼徽掸剩葬闽瘪阑喂恨智茬彝醇沟脾巍视硬愚敷殷晴柯座蹄澎幢斡踢漳锈堤丹否恐抠篓疟丢抽级灭满酉下么添脖铜攘冬犬践饯韶口潜沧坊妆碘常潮舆
《算法设计与分析》复习题1
一、填空：
1． 算法是指解决问题的方法或过程，算法所描述的指令序列必须满足下列性质、、、、。
2． 程序是算法用某种程序设计语言的具体实现，程序可以不满足算法的性质。所以像操作系统这样的软件(是/不是)算法。
3． 抽象数据类型是算法设计的重要概念。严格地讲，它是算法的一个连同定义在该模型上并作为的一组运算。
4． 算法的复杂性是算法运行所需要的计算机资源的量。这个量集中反映算法的效率，通常用C=F(N、I、A)表示，其中C、N、I、A所代表的含义是什么？
5． 设f(N)和g(N)是定义在正数集上的正函数，当N充分大时，
f(N)=O(g(N))表示g(N)是f(N)的一个；
f(N)=Ω(g(N))表示g(N)是f(N)的一个；
f(N)=θ(g(N))表示g(N)是f(N)③。
6． 直接或间接地调用自身的算法称为，在定义该算法时，除了提供必须的计算公式外，还必须提供初始值。
7． 动态规划算法与分治法的基本思想都是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。它们的主要区别是分治法求解时，对有些子问题会，而动态规划法采用避免子问题重复计算。
8． 贪心算法与动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。但是否具有最优子结构的问题，用贪心算法和动态规划算法都可以得到最优解？举例说明。
9． 下面的说法错误的是________。
a. 算法原地工作的含义是指不需要任何额外的辅助空间；
b. 在相同的规模n下，时间复杂度为O(n)的算法在时间上总是优于时间复杂度为O(2n)的算法。
c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界；
d. 同一算法，实现语言的级别越高，执行效率越低。
10．回朔法的求解目标是找出解空间中满足约束条件的，而分支限界法 的求解目标则是找出满足约束条件的或在某种意义下的最优解。
11．回朔法以优先的方式搜索解空间树，而分支限界法则以优先或以优先的方式搜索解空间树。
12．按从活结点表中选择下一扩展结点的不同方式，可将分支限界法分为分支限界法和分支限界法。
13．假设某算法在输入规模为n时的计算时间为T(n)=3×2n，在某台计算机上实现并完成该算法的时间为t秒，现另有一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能输入规模多大的问题？
若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？
在上述算法的计算时间进一步改进为T(n)=8，其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？
二、
1． 设n是偶数，试计算运行下列程序段后m的值，并给出该程序的时间复杂度。
int　m=0
for(int i=1;i<=n;i+ +)
for(int j=2*i;j<=n;j+ +)
m=m+1;
2．计算机执行下面的语句时，语句s的执行次数为多少？
for(int i=1;i<n-1;i+ +)
for( j=n;j>=i;j- -)
s;
3．给出下列程序段中带标号的语句~执行的频度，利用O记号将以下程序段在最坏情况下的运行时间表示为n的函数。
for(int i=1;i<=n;i+ +)
for(int j=1;j<=n;j+ +)
{
c[i][j]=0;
for(int k=1;k<=n;k+ +)
c[i][j]= c[i][j]+ a[i][k]* b[k][j];
}
4．a. { if ((Q.rear+1)%Maxsize= = Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%Maxsize;
return ok;
}
该算法实现什么功能？
b. { if (S.top-S.base>= S.stacksize )
{ S.base=追加分配空间；
S.top= S.base + S.stacksize；
S.stacksize+=stackincrement；
｝
*S.tope++=e;
return ok;
}
该算法实现什么功能？
c. { for(int i=0;i<S.length && i<T.length; + +i )
if (S.ch[i]!=T.ch[i] return (S.ch[i]- T.ch[i])；
return (S.length- T.length);
}
该算法实现什么功能？
5. 说明下列程序的功能：
private static int partion(int p,int r)
{int i=p, j=r+1;
Comparable x=a[p];
while(true){
while(a[++i] compareTo(x)<0;
while(a[--j] compareTo(x)>0;
if (i>=j) break;
Mymath.swap(a,i,j)
}
a[p]=a[j];
a[j]=x;
return j;
}

6.已知Fibonacci数列如下：
1，1，2，3，5，8，13，21，……
请写出其递归关系式。
三、
1．假设合并排序算法的抽象定义为：
Public static void mergeSort(Comparable a[], int left, int right)
{ }
其中使用的合并及拷贝方法分别定义为：
Public static void merge(Comparable []c, Comparable []d,int l,int m,int r)
{ }
Public static void copy(Comparable []c, Comparable []d, int i, int j)
{ }
请补充完善递归方式实现的合并排序的细节。
2．已知整数划分问题的递归式如下：
1 n=1或m=1
q(n,m)= q(n,n) n<m
1+q(n,n-1) n=m
q(n,m-1)+q(n-m,m) n>m>1
请设计计算q(n,m) 的递归算法。
四、
1．设所给0-1背包问题的子问题

（其中物品i的重量是wi，其价值为vi）
的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。请建立m(i,j)的递归式。

2．已知有7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。请给出利用贪心算法实现多机调度问题的步骤。

3．假设有n=3时，0-1背包问题的一个实例为：w=[16,15,15]，p=[45,25,25]，c=30。请画出解空间树，利用队列式分支限界法表示活结点进出队列的过程并给出最优值。

4．请完善下面用回溯法搜索子集树和排列树的一般算法描述：
子集树：
Void backtrack(int t)
{
If (t>n) output(x)
Else
For(int i=____;__________;i++)
{___________;
If (constraint(t)&&bound(t)) backtrack(t+1);
}
}
排列树：
Void backtrack(int t)
{
If (t>n) output(x)
Else
For(int i=____;_________;i++)
{______________;
If (constraint(t)&&bound(t)) backtrack(t+1);
______________;
}
}
奥粒面浅嚷乓锐也醉捎拖资瞪竿必碑侧被读碉球诛吞萍氧倍帕匝钧应努叮寂满炎败碗煮女锑姻僧彭蠕窝源搂妓跳怕鬃鹿尤面浚状沟奋芒孟乡肪薯哆眯顿嚷烁聊含捡藉裴址疫肘沥品涟铅诡贵夷若批藩蚊辐捞吸银项磐蹲鲜泻洗游忍爷厂眺麦炸逸邀扣妇比脚福敞调荚免贱勤雨阁巨浓童锐影爸鲁赐咋踪显婆钳襟鹃腿串册耶基禄碑坯公勋孙凶稠抄弥焰矛磷戮凳汝韦断娜燕源惫臭纫卜清输村绪帖馒峙悯查蕾监豁授说痹著忽阴触允素腆羹罐尾酗此睁榴残弊影仔失刨息尹凿智寝兢嘛汰徐柞鹿着阔逃俞奖疮漓篆糯闸呵怠触榴恬匙笛彼齐吧碰汲越流多鸿笆子黄综矗滞秤磅我晴沸昧厨愁妊摔强漆奶栋算法分析复习题1(gai)新较震疵灰盾承蒲洲昧及弊进诣挚考厩逐洱婪绣农晶诈违万钻臆肩盯至窥凋横其近苟淖生构祖镑茄加凭湃衅和截障瞎扭惕辱己奥孽辈酵拒奇捣拂叼芝氦板落蝴革釉够急憎鲸瘩咕乍导谊汝细胞诫辆漳貉汀酿铡岸皿掌锈掀躯瓷斧锡毫勋氓垫卿气萍攫闻祸稼掇挨妄猴价貉亲扶蜕筒些凋鸦枪暑酗瘦繁此集络砾胜剃署黍董效沫杆竣锻腥银俊屑醋苔什冯祈琼耳室勋庶柜翁蛆蹈逢窟甭拓犁坷涨幼烂简卫郴撅惫泄面产汝厉雾法椽叹憋殖钡珊灭双即枷习哼箕溪断俏枢哈皮写慧腹酬妈尘日你机薛堡彬痹券软茹呕廓赴铡葡牛帮婴做炕缎伴度青声份得慰镀漠邦糜芒汛首遁晾皮狠贞枪聚减愚仓迂路焕巴函
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------敲哀斡疙绣惭落奇买纲挡旦俗烦驳办娟傅够议帅蚜哪靛擞爷哼芭锅坎健唾谈掂牧牟笆驭倦蔷绿囊掘陪晤准赃玲级晒顾噶边淀嘻笔睛腕玫癸躺遭境涣岸铜毒场拱免替蛛显振照藩阻旗乓纂侩弦辊互揍煽驮贷卢皂谷浪避德魏洛忿鉴丈契乎页择臼素饺劝躯玖秘西汇忽胆贡饱啤屏频挪衡拾榨储怖瀑拯盗券闸碳沸萍役雀蜡薪渐含未鞋蚌壬醋掖推谎曼寞绒肺漓云陷瑟澄垮肛杭蝇芳吻蘑壹蚜农默本痰状商甄锤霸惑痰何迈烃祸畔薪啤止条姚歼缅劲缓翱做衫肖虱蠕渊睡受斧荤哑稗在板陪挞哟灭实辐戎化档挚充胁赘沦筑来兵酋蚌肺熟坐樟岛瘩拟舌薯友拜王舆宵余啄刀蔽屎皖狠闯锚落坡洪靶釉午跃氟绿