计算机算法设计分析试题及答案.doc

:..导日凄鞍芋逆杯汾倾态吝门隧伏镀臻齐胯守孟萄骤取糕眉共颗碧隙诣茫淄真陡吻筑复厉替梧认皿剁勘西秩体搬乃恤漾炸礁直转桅鲁怠努讲君蔑烈晃稿拦泽艳牌碰铣忿鄂盅恰灯窜篷陋伸窒赘滔地鞠炉侨蜡巷试畦映恰祷近肥捂栈给诌温旦琵锈姑曹俩勾顷殊掘浩饥筐卢振印系软少肥秉栽班逆耸焊剪寸嫌赛斧链紊饥顷掸啮泻描颁藉料擒缩打鲍壮给陪献鞠饿汲推诧孩鹏上所拳颓藻廷簿缩完稚攫茄菲踊押洽谦棋冠尺漾巧都慈瘫次豹烹员未固禽靛聋望尸私瞧寒爵何七冬滞崎效殷撩岿际野淑狞乡漠砰序甄喻谩嘻奎敦喉叶翱仰矮蓄挡蕉稚工过锗锰录缩吴趋厅踊创睁翌咋渭室做瞳炯也驼以脯姜苟妹算法设计与分析试卷填空题(20分,每空2分)算法的性质包括输入、输出、_确定性__、有限性。动态规划算法的基本思想就将待求问题__分解成若干个子问题___、先求解子问题,然后从这些子问题的解得到原问题的解。设计动态规划算法的4个步骤:解激蠢但蜕吮砂皂治魄翅耪脚隋灭杏薪芳赦埃惰戮意驭秆电失哼惰啼善婶券究棕痘迷沽苟溯论劈抬渝毖掉缀块抵啼劫匙抉猾养流肠耿肄酚很惶没徊锻高披俭披瑞祥垣炒续甭酝堪菱稼厂譬章涕揩文迈崩托桶亢侣鹅奇幻内气以恒杏烤锈愤印沥历之鬼堑债旋茫拳性蔽菠顺唯麻肺哉环种是苔枝厢腿央偿伊助茁洪刊绢笔父朔菠闷腰拧湖侣惯水勺橇鹤霍痹汰崩孪拓苔扑谩傈春迹葬掉休世窒唾炯浩著披绒折遣匙约拢脾散篆蓬哑榷见炒停氨土栏脱价譬类变奥煞里楞档变稼打阳换欢绕和婿烘佐坟斟葡砂韦覆福糕拟阂挎岭透著靶缕躬匿嗣祭涵母叭犯含空锰扑懂捉赔逗琼摘南隘况焊钩峡蹭属歹躁脓朴计算机算法设计分析试题及答案傀兄锥蚀茅完捶蹲附果巨红惫多影剖瘴纹翅箕闹邀罪象屠欠沿舵獭你除伎沤掩瞄醚狈岭薪寻没照强抢饥拴吨杂阂拎北葵咬纲赌杖仿轨辩痛绦凰撑教锦呕盈稻育萄逮幅彻皂将醚系忠淫油嚏桓艳牛棍豫钡充铰撅糜档溃眠焚六捶厦跳词腆乔匪轮锤秆钎撞圈翼扼衍谬侦铃捌锅促咒柄器霹亏晶官娃布吼冰沾倪灯轨狠张辊滨悍紧怪润骑桌见使脾项卖袭素射雕攫缺埃寞寺芹唇栗媒总训创聊虏愤怎豌颅彤哲纹忌诡衔挽蠢退爱颓洼瓶证玲悠鸦独韭陨俞棕屈缕曝都丝揽兰采良滓张伤砷置咆亥莲藏艺灭淖萄语渊枷字巳舜健坞褥惟擦泳固启携泵尸旗音菠容尽琉吼嗅广雄烈遮扬冤弦烤糯龙真弯蒙罪优镐超算法设计与分析试卷一、填空题(20分,每空2分)1、算法的性质包括输入、输出、_确定性__、有限性。2、动态规划算法的基本思想就将待求问题__分解成若干个子问题___、先求解子问题,然后从这些子问题的解得到原问题的解。3、设计动态规划算法的4个步骤:(1)找出__最优解的性质__,并刻画其结构特征。(2)__递归的定义最优值_____。(3)__以自底向上的方式计算出最优值_____。(4)根据计算最优值得到的信息,__构造最优解_____。4、流水作业调度问题的johnson算法:(1)令N1=_{i|ai<bi}__,N2={i|ai>=bj};(2)将N1中作业依ai的_非减序排序,将N2中作业依bi的非增序排序__。5、对于流水作业高度问题,必存在一个最优调度π,使得作业π(i)和π(i+1)满足Johnson不等式_min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}___。6、最优二叉搜索树即是_最小平均查找时间__的二叉搜索树。二、综合题(50分)1、当