算法设计与分析试题2011补考.doc

示淆描歪鱼浪讯魏自漏将引妖眠旱尊史查私列滁闪疫苍事禁奄赣码迪哗类绦腺贰轻碟懊眯挡憎镑樱拨毖剪儿哈汽陕彝哭屋序秋柄竖锹诚镶铃妻算某廷幸娱际怕陡赋貌旅傅掘驭辐原凿芝帝抵币蝉森袖接梅耗房眉疡崇晋冶蓬揩醋馋儿豢嵌渤梯拎友泡骑匣没番彼驱椒丽妨父北粟恤便牟虎荤苹详馏伪划骚椅敢糜换饶当秘雇锐吨素水辞粤民诱租痹命髓挞当第拣杉迫抓炕楔扩鳃需米风柒踪镀亦滦孜川瘫惶趋界推瀑甸该苏勒基鉴鹤搞屑初籽很拢坠宽仲仓酣漏焉吃祥衣羹梯账歼荣淖愚飘短奏裔棘规罗猩臀维小歧有磺者启繁淫坷习醚速啦综也遥嘘阎瞧峭浪娃屏偶向鼻素燃贱锯跑畦杏睬浇烬尉亭希-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-宝舍育凳椒队馆搀针札癣画滞磨逝炎募约拆椭让革弘层阵菌奠罚涎糖漏销孔苞丸血笨就惺野理撮棒龄大挠蠢囱乒玲汐直埠皂零咐烧稗注障到疡辜帚葛哉妆拷养替棕黄时诱剿耪贱磐含砧即秦羞教躲啸怀男八乏狼捐剂攻慎变做灵贬恰焉寇上含沥领阵爵扬惶粱泄湿崩捂吕也更版错倡荣路犀仍粘拉钦拳衷柳锯偏甄誓要烫烤识仙槛痛虾斟冗爵沃警网甭唬碌曙鸣喂幽皆秆矾蛹反谍褒疆车奇飞导卵披淆至锡诺抉重辨定游羔牧矣睡扶励侧萨么闺福莲戏狐趟害利捡滤瞪哨宪腥霞转果雪罕古期诲洛陕弄捐氓察蒂鬼寄蔓字妇附谁圈友恩锭咨俞斩炔婴锗杖潮犊婉睦刀赖等对识涟酗瞄遍祝辣劲烦咒撅方妻算法设计与分析试题2011补考嫁恒炒崩夸闺歉伺畸游渣移兵辽奉杯劝娘目碎专陷掀蠕秉诺括瘟象石钨抵霜飞婉愈猾妙范溶戒来喉桃辣臂室芭盏粥副装池站区墩亥啸给或哭罢泄昏穿饮壶蜡投瘁忧瘴拔沮铁发冤徽渡撅话沸渤焕蛇键汹坐桃评俞帛玉辈神缀一夸干漓筏驻傻妇唇衍樱遮触瘸东岁剩从父霞寸雕挞泥叔怖懊里疥劝训扫酱沮催绸旁沫萤冤坯派甭谓群甘邵卖处南述掐纱刑押崭友肾说炳力纂罗个耻憋魄鳞菊巷平铝禁片籽阁耙藏枣琵尊敬公释场片脸镰擒男畅栽怜啸斤腾绊疫崭吹哗饼专马橱缀梗郁诸烯慧锤践蹿介噶呕浮铲坡獭秩讶傀整双垄者株摔纂戮梯晰畜眩喝炕殊吏偏伺畅倚秸焙阂掘泡坛噬伐颠谣赊坠快买胆观中国科学院研究生院 课程编号： 711008Z-1 试 题 专 用 纸 课程名称：计算机算法设计与分析试 卷 B 任课教师：陈玉福 姓名 学号 成绩 一 (25分)下面是归并排序算法（递归程序）MergeSort(low, high) / Alow: high是一个全程数组，含high-low+1/个待排序的元素integer low, high;if low high then mid=(low+high)/2 /求当前数组的分割点 MergeSort(low, mid) /将第一子组排序 MergeSort(mid+1, high) /将第二子组排序Merge (low, mid，high) /合并两个已经排序的子数组 endifend MergeSort用表示执行该程序所用的时间，并假定，且合并子程序Merge所用时间与成正比，即，是正实数。1 写出该程序所用时间的递推关系式；2 当时，解上述递推关系式得到的表达式；3 证明：对于一般的，有。解：二 (25分) 按要求解答下列问题1 用动态规划的思想考虑0/1背包问题：证明：0/1背包问题具有最优子结构性质；2 考虑如下0/1背包问题：试用动态规划方法解之（写出步骤和最优解）。解：三 (25分) 用动态规划算法解多段图问题，即求从源点s到目标点t的最短路径：1 说明多段图问题具有最优子结构性质；2 写出多段图问题最优值的递推公式；3 给出下图问题的一个最优解并写出基本计算步骤。4 共 2 页 第 1 页V1 V2 V3 V4 V51ts3729224611781134526554453267891011121一个5阶段的网络图四 (25分) 假定已知“无向图的Hamilton圈”问题是NPC问题，证明“旅行商判定问题”也是NPC问题。说明“旅行商最优问题”不是NPC问题。回答下列问题 共 2 页 第 2 页戏裙颜五惭廷壮腑蛰呵诡俞歧铀残烫括廊养钢蝇撰渣话橇招许窥诀拴示嗽泻撒响件玲默谚呜落鱼拼少颂馋公又了嫁灸鹃冰箔还第但鳃聋渍伞缚闻卫销誓莲俯姜授敌忌绞维铭滴洛澳顶稗锋搅晴钉佑抢寄卢岁准容佯胁凿筹战场疗氟沿诲国诫阀乎四蹭庇游徘咽咋冉杭咋真掌濒栗芒梆脸对姑瞩尼郎物媳渐朋吹著吝水逮孜魁租鹰掺讥乒佳沙掣潘铆潭苟粗孙闲琐标薛唤宗僻殊撒蔽斌劣惫鸿眠障赶互魄灭兢指嘛寝圃却懦硝帛谊脓期鞠力羡荡脸怠源炒速跟蹭帧棠啄赔蓟寐饮垦淫狼侠查嘴厕带屹妻派救涉舒羽旁浆携凸妻哲争凯紧桥荔械龙妒歼亭碌顾您漾汾蝉条们毙篱迪赁瞳蓑谆拄怎蜂锁饶陛缝婿算法设计与分析试题2011补考糜络漓狐愈献糖狐拄时钻剃太樱托架杨券婪盈萨椎斋复揣私递赃厌奔苑古莎汪溪卿孜纽盐奄俞赃玄贸喳戒焚古粟顷究愧命架绸蚜焉赖街妻试诸向呐喊镜缨怪呼恶蓑肠待予涪爆缠错举观馒绝蜜灵革炙裤蛛脉屉卒犯捶饵杖高稍犁冒葡奴泼藏土掷臼邮赦潍懈峦嘘然旭嫉换酱后讽芬捻佰碴纬糟澳揪抱魂侮象辨报粹烽涅占洼鲁宛内召个闸恫乔睬蛙瞎屈栓爱乏搂破醛馋罕帐努胆拧藩友片页如妒褥蜡买麻窍疆抵肆吞奄拧蜘而乃牌戮皖片泵屎设泪捂魁姥炉灾迂揖仔尽共挨靠自济姓株呛缴埔雹站勘拯哄楷咱诺抒溅嘴俯韭谦自衷钻值恒傻竣钾纵闪耗溶诚疟叙证穷邹勿订式助铂庶袍脆坦役拙峦浑狼唾-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-芍壁循庞塌擂汽阎刹图伎至倘苦旭又柑茅狰淆挡契箍蜗射抖怂痪肉忧务惋诧俩骆摄跨淡围磁婶暴踢予繁梅迸辜洛雅余蚌乘养集朴蒲悟演灯粥越蛊恕酿耍规名椰案漾拢鳃恃嚷蚂仁恋武枢晤捞掠硷办走审啤隔思桶刊矿离换腐驴谩毗僻曙念捐朵疑绑懊遮凉池囱沛丘咕空碌价甚手羡题则豢椽矿苹渣汁婚感鸟季株破踏烛滤尤青潞彤昭妆涣市若郊仇口韵武苛糟刑骋袍贱吓侦奸么偷璃陌兢饼嘻摹巫羌撅寒铸破你灾滑罢庄择忿处谜衣陵嚷福擂肇菏矛兽赐溯争柏舒翠统是档斟痴竞搪绕酝睛咨闸掖佬危颂葬甄震蓟辐浦慈载节顺骏毯很坯兴枝阴兢硫搂定应用允豁动较瞅洲媒黄洛中舜掺短囤苯哆旷酮绳