杭州电子科技大学研究生考试卷 （ A ）卷 考试课程 学 院 考生姓名 算法设计与分析 计算机学院 考试日期 专 业 学 号 （完 整） 2014年 月 日 ： —— ： 任课教师姓 名 成 绩 张彦斌 三、 试设计一种快速排序算法，（编程语言不限，可使用伪代码，要求写出函数名称、参数及输出)(10’) 四、 考虑下面的整数线性规划问题 maxcixii1naixibi1x为非负整数，1ini一、 按照渐近阶从低到高的顺序排列以下表达式并简单说明理由：(10’) 4n2, logn, 3n, 20n, 2, n2/3, n! 二、在分治法中，通常将一个规模为n的问题分成k个规模为n/m的子问题来求解。分治法算法的复杂度也通常可以用以下递归方程表示： n T(n)=KT(n/m)+f(n) n>1。这个递归方程的计算比较复杂，递归树提供了一个简单直观的近似求解方法。请利用递归树方法求解以下递归方程： （15’） T(n)=2T(n/2)+O(n) n>1. 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。（15） 第 2 页 共 2 页 五、 设C={0,1,...,n-1}是n个字符的集合。求解关于C的任何最优前缀码可以表示为多少位的编码序列，并证明之。（15’） 六、 试设计一个解最大团问题的迭代回溯法。（10’） 七、 回溯法搜索子集树和排列树的算法框架描述。（伪代码）（10’） 八、 栈式分支界限法将活结点表以后进先出（LIFO）的方式存储于一个栈中。试设计一个解0-1背包问题的栈式分支界限法。（15’） 第 2 页 共 2 页 本文来源：https://www.wddqw.com/doc/da3da71f846a561252d380eb6294dd88d1d23d41.html