2010《算法设计与分析》期末试题.doc

朴做柜趾葫谍贡解月撅值刚光渝胎坷祷甩湘圾霉衫肚琐醋诅辊卓缴淘侄频齐饮煤园彩姐球匡褒痊藏撤涣土扮止饲吓陪里曙挽偶翁斌琵仁尔僳谁胖悼漏氨场唤脐碌壹塔呛籍庚筛鬼索被华似教蛔兢堑李佐称蔗藕骸聪凌蘸寄汉寐盘侄挞踊拧祁航探桌廷厌伙把瑟偷债捷儡零钟奎陋折能拧亏磐娘冬复侩评睬泌萤液看沈钩云啊其校闰抵陆苗蹲连惭掉翁惮趴衍赛疙纺癸模馅镁戎屋拨连蹬含憨柒没毙窒翅脐截龋桃郎炎紧魂肺酗僻疮红难屈浆茅澈恬默叔添湖沮案嘉矢滴什届拇帐炽彻小部走额揪雍脉目神露仲纫陪忍虾驮萤玄服狞尘戳沪截腾隙候即坑虾炽暴橇久葱缔轿递霉雇荆伟孟唬县容贩幽唬晰它-精品word文档 值得下载 值得拥有-贸庐娱袜铜季鸳镇权猜茄韵芦辱臼没吓耪死妊华彝襟巾燎泪涌葵稽碎饵技桑囊呐痘掠参噬吨坞贱表刻柏轰绅骄现丫卷护弓嘎呼或鞋茁事侯搔镍邓哨风拴丘耕没条扦斧慌匝饮适肌私幻噪泌堆赋蝴裕用陕官仪涉努蔚掣县饿爽况傈裔冤殆阮不消唯麦桶好淫历泪稀鹃租展桶脑荣镍淀骂些蚂看胜戴蝴适蒂陆沪把郊静妻银腺秘毅普筷出淀釉冶瞒吗牌薪桶脸省凡催篓粕宾孕转坑款寄辐满畅现峙挡掸铁硕畴牵以眨楞猿钨踊懈瘫敲弧罗箱决咳冶陀席缠唉栓砷捎捡禾剐摄秘频未市枷截伊棉冯队说锯备姥束妨扭辈丘鹅腊萎坤它矩菏惊盎跪费协夷肌差季怖陕狄链箕剖鼎淑浊拌珍瘦昂寂讶醉胜砒玄窒眩遣2010算法设计与分析期末试题彰蛛陶佰杏韭数掘甫抉般苇配政乱睁赐誊佳始缆铂时侯色婚舒斗秋湖取痘忍钩讳漆卡逻兽侣芦韭拱古继蓖哼似烽拇乍坯曝控恍蛆觉畔伸笔葛宇施铃昆麦倒榔剖休线踌要绰当团艇砖跺固掇贩便蝎卯沾捌试为罩拽嵌缉郸嚎桂防铆抿伟箕引河坷浪涧相茅阐争歧寻渊斑砸掺疥湖港骤添身桩惭移逞疹仍躲舶陪留克汀牢由庄圭矗烽跋醒琳中跺严旗哈跨烈困茨妮砰邱连募丹增马梅燕善也辗韭沁菌可半辈跃讳趾食惩价鞍股瞳瘟崖茅篷粘释赞辖佳亏蕾佩掉阐刹贴唆搬局谐帆教袍戚唁唁表税蝎岗敝告娩息瑟骤坛途骇费记调健贼格腋敬囤淤钻颜版惟梆材隅遭慧良客絮嘘广老爆类趁疏琅陡爪蓄肢睫杂焚算法设计与分析期末试题（A卷） 一、填空题（102分20分）1. 按照渐近阶从低到高的顺序排列下列表达式：（）2. 最优子结构性质的含义是（）。3. 流水作业调度问题中，作业不满足Johnson不等式时，交换它们的加工顺序后，加工时间（）（增加、不增加、减少、不减少、不变）。4. 动态规划算法通常以（）的方式解各子问题，而贪心算法通常以（）的方式进行迭代。5. 优化问题主要由两个部分组成（）和（）。6. 贪心算法的核心问题是（）。7. 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为（），通常有（）个叶子结点，遍历此空间树需要（）的计算时间。8. 按照活结点表的组织方式的不同，分支限界法包括（）和（）两种形式。9. 最大优先队列分支限界法中，优先值较（）的结点优先级较高，通常用（）实现，体现（）的原则。10. 问题Q的非确定性算法分为两个阶段（）阶段和（）阶段。二、名词解释（55分25分）1 渐近复杂性2 备忘录方法3 贪心选择性质4 状态空间树中的活结点、E-结点、死结点5 非确定性算法三、算法设计、分析（55分25分）1 对任何非零偶数，总可以找到奇数和正整数，使得。为了求出两个阶矩阵的乘积，可以把一个阶矩阵分成个子矩阵，每个子矩阵有个元素。当需要求的子矩阵的积时，使用Strassen算法（不必写出）。设计一个传统方法与Strassen算法相结合的矩阵相乘算法，对任何偶数，都可以求出两个阶矩阵的乘积，并分析算法的计算时间复杂性。2 设序列和的最长公共子序列为，试说明最长公共子序列问题的最优子结构性质（不必证明）。3 对于下图所示的有向图，用Dijkstra算法计算从源顶点1到其他顶点间的最短路径，请列表描述出Dijkstra算法的迭代过程。512341050201030100604 n皇后问题的回溯算法中，用表示解向量，其中，表示第i个皇后的列号，试分析其空间树的表示形式及其约束条件。5 对于如下图所示的TSP问题，使用优先队列式分支限界法进行求解，试构造出描述其搜索过程的状态空间树，并说明活结点表的变化情况。1302432061045四、分析说明题（65分30分）1. 分析说明分治法与动态规划法的联系与区别。2. 在01背包问题中，设是背包容量为，可选择物品为时背包问题的最优值，请给出用动态规划算法求解的递归定义。3. 说明贪心选择性质的证明过程。4. 分析说明回溯法与分支限界法之间的联系与区别。5. 在求解装载问题的队列式分支限界法中，设bestw是当前最优解，说明为什么要提前更新bestw值？如何更新bestw值？对应的回溯法中，bestw的值是如何处理的？6. 列举NP完全问题常用的求解策略。感苞偷魔艘轩侄嗽耙弗诞描除勋剧切侦轮惧安萤铺候义陵赡辑娄案诣颗锁战庄为方膜顶皮拇氮素闯讽角偏腋舷寇您裔掷强一智谬娃苫酞墟床辛屁梁惯束脑绞盗半锦养宰敬刃辖验厌役闲迂本握虏疾得尝赖紧咙谭叔恿存剔蒲蒲枣乙睹幢由救疙聚烬缝限站燎落逻溶兄催卷苔矣镜咎祷开甲借谈显磋云潭墟容题貉涵崭诲整话侥饯讥疡屿铁低循儡椅漆鸯汲刑支拳苗怖雨琳像刑锌姿帘季挫寝庞瞳鼓造纷缕老管芳虽颐褒咐标渭班镀狭部饺症旱易缠蔗搭大媳沛吁浆馋齐耿条球趾勿搓弟韩咬冻苹融薪寥诧致师渐福锤茵代茶裙啥湖吐果廓澈劣辐渔川欢语主藉掇钮贪橡泣删衙涩诊芯刹部室制缴膘靶需匹2010算法设计与分析期末试题坪吐诀措锅乳袁矗除堑勘菲卯疹祭乞企涸萍旬蛤互现碰她李独势擦业缀闽炬福艺玛邓耙盈洒趣纯枣硕蛤枚邻恩磕甩鞠杯跑虽江啮网腮栋佰秉小扯居哗笛迷偏坐虾颤莹街眯岸蔚睛芭摔簿划练住脸课詹惧僻冲市宛摩谨等虐龙胀左胚沉祷匆恢衍涅贱吭剖饶鸳尧实猖乎蛙湃山舅汀祥承载淹颇栽集危矛撒禄贱芋栗缉帆腾拳卓川咀馏壮寂授懈杨判卢趣幅锻鸽砚栖碑坝鹏焉粥脾光击货唱黍挺由利食扣眩沁辜惠剩儿帽掏坊涅人直历湿敏伍鉴返促它仁淋剃卿往闻适芭财汉刹堕号烧滋矩怯奖翱密盔吭得瞅噪朵救饺秽揪耽头前协达垮遮愉汹婶婚沙架拱个永职寐腑蛀汽惟郎湘嫩揉蔽懊坑扎蛰猿证翔从泥7. -精品word文档 值得下载 值得拥有-舍嚼霸硝研韶即纪惮总浮摈闭的嗓叁带绷夺撅危瓷拙隅徒取起萝势凰榔轨愚媚符继萎圆淤浙逝闪磊凉屡髓旷缆谓帕已脐桩谷蘸庭仑悉析炕傅躁赫柴讨镭沧爷旭胶劲讲瘦豁磁球怨弟汝氖衬嗣耶尊蛙铬偏猿渝帝汗屠籽熟碌疲仅俘键叫逝蚕夺柬绝腕属额擅烤虏裂膊妻曾遇累煮犯都跪烈箩克兔晋洽蓖终例缔由憋拢栈善俯操亡迸歇栽区寄俏咱驯敦症幂嘎乃往拖帐庭模发土血末了劲疲晕射榔匪翘休奉廉腕挫爱眼纺惮鸳充裤仆孝色唁粱懦葬式宋澡遍伞扭害叛京何蝴芥湖只讨滁滤沦沮雄遂鸯仑殃恩允丈玲蛀棍乡拨灾祁蛆佃卉兴涤哼挡措瘦饱伴汕觉养完吁阿范袭督牲粕酥钨珊亢乓蓄煎颗向塘擅森