计算机算法设计与分析练习题

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

1、计算机算法设计与分析练习题一．最大子段和问题：给定整数序列，求该序列形如的子段和的最大值：1.一个简单算法如下：intMaxsum(intn,inta,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intsuma=0;for(intj=i;j<=n;j++){suma+=a[j];if(suma>sum){sum=suma;besti=i;bestj=j;}}}returnsum;}试分析该算法的时间复杂性。2.试用分治算法解最大子段和问题，并分析算法的时间复杂性。3.试说明最大子段和问题具有最优子

2、结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。二．设是个互不相同的元素，每个元素有一个正实数权值，且满足。个元素的带权的中位数是满足下面不等式的元素：(1)1).证明的（不带权的）中位数是带权（）的带权中位数（不带权的中位数是指按照大小排在中间位置的数，如果有两个，则取小者）。2).说明如何通过排序，在最坏情况下用时间求出个元素的带权中位数。3).说明如何利用一个线性时间选择算法，在最坏情况下用时间求出个元素的带权中位数。4).邮局位置问题是：已知个点以及与它们相联系的权，要求确定一点（未必是输入的点），使和式达到最小，其中表示

3、与之间的距离。试论证带权的中位数是一维邮局问题的最优解，此时。三．设是准备存放到长为L的磁带上的n个程序，程序需要的带长为。设，要求选取一个能放在带上的程序的最大子集合（即其中含有最多个数的程序）。构造的一种贪心策略是按的非降次序将程序计入集合。1).证明这一策略总能找到最大子集，使得。2).设是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？3).试说明1)中提到的设计策略不一定得到使取最大值的子集合。四．电路布线问题：在一块电路板的上、下两段分别有个接线柱，如下图。根据电路设计，要求用导线将上端接线柱与下端接线柱相连，1012654389

4、710126543897导线称为电路板上的第条连线。对于任何连线相交的充分必要条件是。在制作电路板时，要求将这条连线分布到若干个绝缘层上，使得在同一层上的连线不相交。电路布线问题就是要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题等价于确定布线集的最大不相交子集。如果记，的最大不相交子集为，试证明电路布线问题具有最优子结构性质。构造一个动态规划算法解电路布线问题（写出算法的基本步骤即可），并说明你的算法的时间复杂度。四．给定件物品和一个背包，物品的重量是，体积是，价值是；背包的容量为，容积为。一件物品只能整个放进背包中或不放进背包中，也

5、不允许重复放入。试设计一个求解此问题的算法，并计算其时间复杂度。五．设计一个时间的算法，找出个数组成的序列的最长单调递增子序列。六．字符出现的频率恰好是前8个Fibonacci数，它们的Huffman编码是什么？将结果推广到个字符的频率恰好是前个Fibonacci数的情形。Fibonacci数的定义为：。七．（双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最

6、短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：八．考虑下面特殊的整数线性规划问题试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。四．考虑下列问题i.在一个由元素组成的表中，出现次数最多的元素称为众数。试写出一个求众数的算法，并分析其时间复杂性。ii.主元素问题：数组中的元素称为该数组的主元素，如果该数组中有多于一半的元素等于，即。主元素问题是确定已知数组中是否存在主元素。设计一个线性时间算法求解主元素问题。五．分派问题一般陈述为：给个人分派件工作，把工作分派给第个人的成本为。设计一个回溯算法，在给每个人分派一件

7、不同工作的情况下，使得总成本最小。六．已知一个无向连通图用它的邻接矩阵表示，试设计一个回溯算法HamiltonCycle，判定该图是否有Hanmilton圈，如果有将所有不同的Hanmilton圈都打印出来。七．设和，使用求定和子集问题的回溯算法找出中所有和数为的子集，并画出所生成的部分状态空间树。八．画出优先队列式算法对于下列0/1背包问题实例所生成的部分状态空间树：九．栈式分枝限界法将活结点表以后进先出(LIFO)的方式存储于一个栈中。试设计一个解0/1背包问题的栈式分枝限界算法，并说明栈式分枝限界算法与回溯法的区别。部分问题提示：问题一．1.3个f

8、or循环，时间复杂度为;2.将序列分成两部分：和，此时有三种可能情况：(1)的最