还剩10页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
计算机算法设计与分析练习题1.最大子段和问题给定整数序列,求该序列形如的子段和的最大值
1.一个简单算法如下intMaxsumintnintaintbestiintbestj{intsum=0;forinti=1;i=n;i++{intsuma=0;forintj=i;j=n;j++{suma+=a[j];ifsumasum{sum=suma;besti=i;bestj=j;}}}returnsum;}试分析该算法的时间复杂性
2.试用分治算法解最大子段和问题,并分析算法的时间复杂性
3.试说明最大子段和问题具有最优子结构性质,并设计一个动态规划算法解最大子段和问题分析算法的时间复杂度二.设是个互不相同的元素,每个元素有一个正实数权值,且满足个元素的带权的中位数是满足下面不等式的元素
11.证明的(不带权的)中位数是带权()的带权中位数(不带权的中位数是指按照大小排在中间位置的数,如果有两个,则取小者)
2.说明如何通过排序,在最坏情况下用时间求出个元素的带权中位数
3.说明如何利用一个线性时间选择算法,在最坏情况下用时间求出个元素的带权中位数
4.邮局位置问题是已知个点以及与它们相联系的权,要求确定一点(未必是输入的点),使和式达到最小,其中表示与之间的距离试论证带权的中位数是一维邮局问题的最优解,此时三.设是准备存放到长为L的磁带上的n个程序,程序需要的带长为设,要求选取一个能放在带上的程序的最大子集合(即其中含有最多个数的程序)构造的一种贪心策略是按的非降次序将程序计入集合
1.证明这一策略总能找到最大子集,使得
2.设是使用上述贪心算法得到的子集合,磁带的利用率可以小到何种程度?
3.试说明1中提到的设计策略不一定得到使取最大值的子集合4.电路布线问题在一块电路板的上、下两段分别有个接线柱,如下图根据电路设计,要求用导线将上端接线柱与下端接线柱相连,导线称为电路板上的第条连线对于任何连线相交的充分必要条件是在制作电路板时,要求将这条连线分布到若干个绝缘层上,使得在同一层上的连线不相交电路布线问题就是要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线该问题等价于确定布线集的最大不相交子集如果记,的最大不相交子集为,试证明电路布线问题具有最优子结构性质构造一个动态规划算法解电路布线问题(写出算法的基本步骤即可),并说明你的算法的时间复杂度5.给定件物品和一个背包,物品的重量是,体积是,价值是;背包的容量为,容积为一件物品只能整个放进背包中或不放进背包中,也不允许重复放入试设计一个求解此问题的算法,并计算其时间复杂度6.设计一个时间的算法,找出个数组成的序列的最长单调递增子序列7.字符出现的频率恰好是前8个Fibonacci数,它们的Huffman编码是什么?将结果推广到个字符的频率恰好是前个Fibonacci数的情形Fibonacci数的定义为8.(双机调度问题)用两台处理机A和B处理个作业设第个作业交给机器A处理时所需要的时间是,若由机器B来处理,则所需要的时间是现在要求每个作业只能由一台机器处理,每台机器都不能同时处理两个作业设计一个动态规划算法,使得这两台机器处理完这个作业的时间最短(从任何一台机器开工到最后一台机器停工的总的时间)以下面的例子说明你的算法9.考虑下面特殊的整数线性规划问题试设计一个解此问题的动态规划算法,并分析算法的时间复杂度10.考虑下列问题i.在一个由元素组成的表中,出现次数最多的元素称为众数试写出一个求众数的算法,并分析其时间复杂性ii.主元素问题数组中的元素称为该数组的主元素,如果该数组中有多于一半的元素等于,即主元素问题是确定已知数组中是否存在主元素设计一个线性时间算法求解主元素问题11.分派问题一般陈述为给个人分派件工作,把工作分派给第个人的成本为设计一个回溯算法,在给每个人分派一件不同工作的情况下,使得总成本最小12.已知一个无向连通图用它的邻接矩阵表示,试设计一个回溯算法HamiltonCycle,判定该图是否有Hanmilton圈,如果有将所有不同的Hanmilton圈都打印出来13.设和,使用求定和子集问题的回溯算法找出中所有和数为的子集,并画出所生成的部分状态空间树14.画出优先队列式算法对于下列0/1背包问题实例所生成的部分状态空间树15.栈式分枝限界法将活结点表以后进先出LIFO的方式存储于一个栈中试设计一个解0/1背包问题的栈式分枝限界算法,并说明栈式分枝限界算法与回溯法的区别部分问题提示问题一.
1.3个for循环,时间复杂度为;
2.将序列分成两部分和,此时有三种可能情况1的最大子段和与的最大子段和相同;2的最大子段和与的最大子段和相同;3的最大子段和为,其中;注意到上述三种情况,就可以设计出求最大子段和问题的分治算法该算法的时间复杂度函数满足如下递推关系式其中是一个固定正整数直接推得可得时间复杂度为3.若记,所求的最大子段和为注意到可以证明最大子段和问题具有最优子结构性质,并且设计出求解该问题的动态规划算法该算法的时间复杂度为问题二
3.对线性选择算法进行改进首先同线性选择算法一样找到划分子程序(Partition)所用的“标竿”(即用来作为标尺的数,比该数大的数向后移,比该数小的向前移,通过交换完成),在Partition程序中加一句计算比的元素的权和;在线性选择算法的递归过程中,将判断改为,这样就构造出线性时间的求带权中位数算法4.因为1维的邮局问题,所有的点都可以表示在一个实数轴上,假设的坐标为,不妨假定(不然,可以令),此时可以认为是的权注意到其中,代表点的坐标于是1如果是带权中位数,则2直接推导可知,从而证明断言问题四.记,对于固定的,分两种情况讨论(画图)情况1,,此时;情况2,,此时;对于有,由此,可以说明电路布线问题具有最优子结构性质,并设计出求该问题的动态规划算法其时间复杂度为问题五.设计动态规划算法时,注意淹没规则,因为此时不仅有容量约束还有容积约束设和是两个点偶,当而且时,称点耦淹没点耦其它部分同0/1背包问题的动态规划算法设计回溯算法和分枝限界算法时,同时注意到两个约束即可其余略问题六.用记序列中最长单调递增子序列的长度,为序列中所有长度为的单调递增子序列中最后元素最小的子序列的最后元素则根据此递推关系式,可以设计一个求最长单调递增子序列的动态规划算法,该算法时间复杂度为问题八假定个作业的集合为则双机处理作业问题相当于确定的子集,使得中的作业在机器A上处理、其余作业在机器B上处理的安排是最省时的安排此时所用时间为,即最优安排所用时间应为若记,则有如下递推关系
4.1令表示机器A需等待时间,且机器B需等待时间情况下安排作业集合在两台机器A、B上处理所需的最短时间,则对于任意作业,
4.2个作业的双机处理问题满足
4.
34.2说明双机调度问题具有最优子结构性质,可以采用动态规划算法在
4.3中,如果,则作业安排在机器A上处理,否则安排在机器B上处理若用表示第件作业在机器A上处理,表示第件作业在机器B上处理,则不等式就决定了的取值根据以上分析不难给出双机调度问题的动态规划算法注此种方法能否推广求解多机调度问题,比如求解3机调度问题?问题九将每件物品用两个和它完全一样的物品来替代,构造一个具有件物品的0/1背包问题为写出数学模型,可以把用于表示物品装包情况的变量用两个变量表示其被装入背包的可能情况表示物品没有被装进背包;则表示两件物品有一件装进背包,而则表示两件物品都被装进了背包因而注这种将整数规划问题转化成0/1规划问题求解方法使得问题的规模增加过大,你能否设计一个较好的方法,使问题规模的增大小些?第二部分分析比较1.试比较复杂性函数的渐进性态与函数的区别和联系2.假定复杂性函数都是定义在正整数集合上的正函数,那么关于渐进上界符号,如下运算性质那些成立、那些不成立成立则给出证明、不成立则举出反例1;2;3;4其中是一个正的常数;
5.3.何谓递归算法?就阶矩阵相乘分别设计递归算法和迭代算法,并比较两个算法的时间和空间复杂度4.归并排序和快速排序各自都强调了那方面的进程?5.试分析求最有生成树的Prim算法和Kruskal算法的时间复杂性,看它们在何种情况下表现各自的优越性6.贪心算法和动态规划算法有什么共同点和区别?7.试比较回溯法与分枝限界算法,分别谈谈这两个算法比较适合的问题?8.确定性图灵机模型与非确定性图灵机模型的主要区别在那里?确定性图灵机模型下算法的时间复杂度和空间复杂度指的是什么?9.什么是多项式时间算法?什么是NP类问题?10.已经知道如何通过已知的NPC问题去证明另一个NP-问题也是NPC问题的方法,能否给出一个通过已知的P-问题证明另一个判定问题是P-问题?11.NP-困难问题与NPC问题是一类问题吗?就旅行商最优问题和旅行商判定问题谈你的看法12.下列问题那些是P-问题、那些是NPC-问题?那些是NP-困难问题?1最优生成树的判定问题;例给定一个赋权(权为正整数)连通图,一个正整数问是否存在的生成树,其权值不超过?2二维匹配问题例给定一个二部图,问是否存在的完备匹配,即存在的子集满足中任何两条边没有公共顶点,而且的端点集为?3二元可满足性问题例给定逻辑语句,其子句定义在布尔变量上,而且每个子句的均由两个文字构成,问是否存在布尔变量的一个真值分配,使得语句取真值?4三元可满足性问题3SAT3-Satisfiability例给定布尔变量的一个有限集合及定义于其上的逻辑语句,其中,,问是否存在的一个真赋值,使得为真?5图的独立集问题例对于给定的无向图和正整数问是否包含一个-独立集,即是否存在一个子集,使得中的任何两个顶点在图中都不相邻提示考虑独立集和团的关系如果是图的团,则是的补图的独立集;反之亦然6二部图的独立集问题例给定一个二部图二部图,正整数问是否含有一个不小于的独立集?7团问题(CLIQUE)例给定一个无向图和一个正整数问是否包含一个团?即是否存在,且对任意,有8顶点覆盖问题VERTEX-COVER例给定无向图和一个正整数问是否有覆盖,即是否存在,使得对任意,有9定和子集问题DSS例给定非负整数集合S,正整数M问是否存在子集使得10精确覆盖问题XC例已知有限集合的子集族问是否包含一个精确覆盖,即是否存在,使得中元素互不相交,且11划分问题PARTS例已知一个有限集合,及对每个赋予的权值问是否存在一个子集,使得120/1背包判定问题KPS例给定一个有限集合,对于每个,对应一个值和另一个值另外给定一个约束值和目标问是否存在的一个子集,使得,而且130/1背包最优问题14旅行商判定问题例待访问城市的集合,每对城市之间的距离,以及一个界问在存在一个总长不超过的、通过所有城市的旅行路线吗?15旅行商最优问题16有向图的有向Hamilton圈问题例给定有向图问G是否有一个有向Hamilton圈,即长度为,而且恰好经过每个顶点一次,然后回到起始顶点17无向图的Hamilton圈问题例给定无向图问G是否有一个Hamilton圈,即长度为,而且恰好经过每个顶点一次,然后回到起始顶点的圈提示将有向图的(有向)Hamilton圈问题实例变换成无向图的Hamilton问题实例把已知有向图的每个顶点换成欲构造的无向图的三个顶点,并将顶点与顶点分别相连如果在有向图中有从顶点到顶点的有向边(弧),则在无向图中将顶点与顶点连接一条边18区间排序问题(Sequencingwithinintervals)例给定任务的有限集合,对于每个任务,相应有一个开始时间和终止时间以及工作时间,其中,问是否存在任务集的一个可行时间排序表,即是否存在函数,满足下面两个条件
(1)对每个,有且;
(2)若,则或19三元精确覆盖问题X3C例给定有限集合X|X|=3q以及X的三元子集族C问C含有X的一个精确覆盖吗?即是否存在一个子族,使得X的每个元素恰好只出现的一个三元子集中20Steiner树判定问题例给定图,对其每条边都有相应的权,另外有G的顶点子集,某个界问是否存在G的一颗子树,使,而且?1012654389710126543897。