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

计算机算法设计与分析练习题一 最大子段和问题：给定整数序列 ，求该序列形如的子段和的最大值： 1. 一个简单算法如下：int Maxsum(int n,int a,int& besti,int& bestj) int sum = 0; for(int i=1;i=n;i+) int suma = 0;for(int j=i;j sum) sum = suma; besti = i; bestj = j; return sum;试分析该算法的时间复杂性。2. 试用分治算法解最大子段和问题，并分析算法的时间复杂性。3. 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。二设是个互不相同的元素，每个元素有一个正实数权值，且满足。个元素的带权的中位数是满足下面不等式的元素： (1)1). 证明的（不带权的）中位数是带权 （ ）的带权中位数（不带权的中位数是指按照大小排在中间位置的数，如果有两个，则取小者）。2). 说明如何通过排序，在最坏情况下用时间求出个元素的带权中位数。3). 说明如何利用一个线性时间选择算法，在最坏情况下用时间求出个元素的带权中位数。4). 邮局位置问题是：已知个点以及与它们相联系的权，要求确定一点（未必是输入的点），使和式达到最小，其中表示与之间的距离。试论证带权的中位数是一维邮局问题的最优解，此时。三设是准备存放到长为L的磁带上的n个程序，程序需要的带长为。设，要求选取一个能放在带上的程序的最大子集合（即其中含有最多个数的程序）。构造的一种贪心策略是按的非降次序将程序计入集合。 1). 证明这一策略总能找到最大子集，使得。 2). 设是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？3). 试说明1)中提到的设计策略不一定得到使取最大值的子集合。四 电路布线问题：在一块电路板的上、下两段分别有个接线柱，如下图。根据电路设计，要求用导线将上端接线柱与下端接线柱相连，1012654389710126543897导线称为电路板上的第条连线。对于任何连线相交的充分必要条件是。在制作电路板时，要求将这条连线分布到若干个绝缘层上，使得在同一层上的连线不相交。电路布线问题就是要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题等价于确定布线集的最大不相交子集。如果记，的最大不相交子集为，试证明电路布线问题具有最优子结构性质。构造一个动态规划算法解电路布线问题（写出算法的基本步骤即可），并说明你的算法的时间复杂度。五 给定件物品和一个背包，物品的重量是，体积是，价值是；背包的容量为，容积为。一件物品只能整个放进背包中或不放进背包中，也不允许重复放入。试设计一个求解此问题的算法，并计算其时间复杂度。六 设计一个时间的算法，找出个数组成的序列的最长单调递增子序列。七 字符出现的频率恰好是前8个Fibonacci数，它们的Huffman编码是什么？将结果推广到个字符的频率恰好是前个Fibonacci数的情形。Fibonacci数的定义为：。八 （双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法： 九 考虑下面特殊的整数线性规划问题试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。十 考虑下列问题i. 在一个由元素组成的表中，出现次数最多的元素称为众数。试写出一个求众数的算法，并分析其时间复杂性。ii. 主元素问题：数组中的元素称为该数组的主元素，如果该数组中有多于一半的元素等于，即。主元素问题是确定已知数组中是否存在主元素。设计一个线性时间算法求解主元素问题。十一 分派问题一般陈述为：给个人分派件工作，把工作分派给第个人的成本为。设计一个回溯算法，在给每个人分派一件不同工作的情况下，使得总成本最小。十二 已知一个无向连通图用它的邻接矩阵表示，试设计一个回溯算法HamiltonCycle，判定该图是否有Hanmilton圈，如果有将所有不同的Hanmilton圈都打印出来。十三 设和，使用求定和子集问题的回溯算法找出中所有和数为的子集，并画出所生成的部分状态空间树。十四 画出优先队列式算法对于下列0/1背包问题实例所生成的部分状态空间树：十五 栈式分枝限界法将活结点表以后进先出(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.3)(4.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) 三元可满足性问题3SAT(3-Satisfiability)例：给定布尔变量的一个有限集合及定义于其上的逻辑语句，其中，。问：是否存在的一个真赋值，使得为真？(5) 图的独立集问题例：对于给定的无向图和正整数问：是否包含一个独立集，即是否存在一个子集，使得中的任何两个顶点在图中都不相邻。提示：考虑独立集和团的关系：如果是图的团，则是的补图的独立集；反之亦然。(6) 二部图的独立集问题例：给定一个二部图二部图，正整数问：是否含有一个不小于的独立集？(7) 团问题（CLIQUE）例：给定一个无向图和一个正整数。问：是否包含一个团？即是否存在，且对任意，有(8) 顶点覆盖问题VERTEX-COVER例：给定无向图和一个正整数问：是否有覆盖，即是否存在，使得对任意，有。(9) 定和子集问题DSS例：给定非负整数集合S，正整数M问：是否存在子集,使得(10) 精确覆盖问题XC例：已知有限集合的子集族问：是否包含一个精确覆盖，即是否存在，使得中元素互不相交，且(11) 划分问题PARTS例：已知一个有限集合，及对每个赋予的权值问：是否存在一个子集，使得(12) 0/1背包判定问题 KPS 例：给定一个有限集合，对于每个，对应一个值和另一个值。另外给定一个约束值和目标 问：是否存在的一个子集，使得，而且(13) 0/1背包最优问题(14) 旅行商判定问题例：待访问城市的集合，每对城市之间的距离，以及一个界。问：在存在一个总长不超过的、通过所有城市的旅行路线吗？(15) 旅行商最优问题(16) 有向图的有向Hamilton圈问题例：给定有向图问：G是否有一个有向Hamilton圈，即长度为，而且恰好经过每个顶点一次，然后回到起始顶点(17) 无向图的Hamilton圈问题例：给定无向图问：G是否有一个Hamilton圈，即长度为，而且恰好经过每个顶点一次，然后回到起始顶点的圈。提示：将有向图的（有向）Hamilton圈问题实例变换成无向图的Hamilton问题实例：把已知有向图的每个顶点换成欲构造的无向图的三个顶点：，并将顶点与顶点分别相连。如果在有向图中有从顶点到顶点的有向边（弧），则在无向图中将顶点与顶点连接一条边。(18) 区间排序问题（Sequencing within inte