算法分析与设计

《算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》学习中心：专业：学号：姓名：作业练习一一、名词解释1、递归算法2、程序二、简答题1、算法需要满足哪些性质？简述之。2、简要分析分治法能解决的问题具有的特征。3、简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。三、算法编写及算法应用分析题1、冒泡排序算法的基本运算如下：fori←1ton-1doforj←1ton-idoifa[j]

2、定的两棵二叉树T1和T2是否相同。4、给出一个分治算法来找出n个元素的序列中的第2大元素，并分析算法的时间复杂度。作业练习二一、名词解释1、MST性质2、子问题的重叠性质二、简答题1、简述动态规划算法求解的基本要素。2、备忘录方法和动态规划算法相比有何异同？简述之。3、贪心算法求解的问题主要具有哪些性质？简述之。三、算法编写及算法应用分析题1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。最大子段和问题：给定由n个整数（可能为负整数）组成的序列a1a2…an，求该序列形如Σi≤k≤ja

3、k的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0,max1≤i≤j≤nΣi≤k≤jak}。2、关于多段图问题。设G＝(V，E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi：，其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点t（称为汇），图中所有的边（u,v），，。求由s到t的最小成本路径。①给出使用动态规划算法求解多段图问题的基本思想。②使用上述方法求解如下多段图问题。3、最优二元归并问题：已知将两个分别包含a个和b个记录的已分类文件归并

4、在一起得到一个分类文件需作a+b次记录移动。现有n个已分类文件F1,F1,⋯,Fn，它们的记录个数分别为l1,l2,⋯,ln。现在考虑使用二元归并模式将这n个文件归并成一个分类文件，要求记录移动次数最少。设计一个贪心算法来求解一种最优的二元归并（即记录移动次数最少的二元归并）。4、带限期的作业调度问题：n个作业需要在一台机器上处理，每个作业可在单位时间内完成。每个作业i都有一个截止期限di>0(di为整数)，当且仅当作业i在它的截止期限之前被完成，获得pi>0的效益。一种可行的调度方案为n个作业的一个子集J，

5、其中J中的每个作业都能在各自的截止期限内完成。该可行调度方案的效益是J中作业的效益之和。试设计贪心算法求效益最大的可行调度方案（即最优调度方案）。作业练习三一、名词解释1、多机调度问题2、优先队列式分支限界法二、简答题1、简述回溯法的基本思想。2、简要分析分支限界法与回溯法的异同。3、常见的分支限界法有哪些？简述之。三、算法编写及算法应用分析题1、分派问题一般陈述如下：给n个人分派n件工作，把工作j分派给第i个人的代价是COST(i,j)（非负实数）。要求设计一个回溯算法，在给每个人分派一件不同工作的前提下使

6、得总代价最小。按照回溯法求解问题的基本步骤，请你完成几个任务：①给出解的一般形式，写出解空间。②以n=4为例画出表示解空间的状态空间树。并指出树中哪些结点是解结点？③提出一个在深度优先搜索状态空间树时用于剪枝的剪枝函数（用文字描述）。2、设计一个回溯算法来求解k-着色问题：给定无向图G=,要求使用k种颜色来给图中每个结点着色（每个结点使用k种颜色之一），使得没有两个相邻的结点颜色相同。①给出解向量的形式，并画出当n=3,k=3时的搜索树。②给出剪枝操作。③最坏情况下你的算法在搜索树上会生成多少个结点

7、？分析算法的时间复杂度。3、对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。4、设计一个求解下列最大完全子图问题的回溯算法。只要求叙述清楚算法的主要要素，并指出算法的最坏时间复杂度。最大完全子图问题：给定无向图G，求出G中顶点个数最多的完全子图。