北航研究生算法(2018精心整理)

一：判断题1、一个正确的算法，对于每个合法输入，都会在有限的时间内输出一个满足要求的结果。（对）2、NP完全问题比其他所有NP问题都要难。（错）3、回溯法用深度优先法或广度优先法搜索状态空间树。（错，仅深度优先）4、在动态规划中，各个阶段所确定的策略就构成一个策略序列，通常称为一个决策。（错）5、P类和NP类问题的关系用P⊂NP来表示是错误的。（错）6、若近似算法A求解某极小化问题一实例的解为Sa，且已知该问题的最优解为Sa/3，则该近似算法的性能比为3。（错）7、通常来说，算法的最坏情况的时间复杂行比平均情况的时间复杂性容易计算。（对）8、若P2多项式时间转化为(polynomialtransformsto)P1，则P2至少与P1一样难。（错）9、快速排序算法的平均时间复杂度是O(nlogn)，使用随机化快速排序算法可以将平均时间复杂度降得更低。（错）10、基于比较的寻找数组A[1,…,n]中最大元素的问题下届是Ω(n/3)。（错）11、O(f(n))+O(g(n))=O(min{f(n),g(n)})（错）12、若f(n)=Ω(g(n))，g(n)=Ω(h(n))，则f(n)=Ω(h(n))（对）13、若f(n)=O(g(n))，则g(n)=Ω(f(n))（对）14、贪婪技术所做的每一步选择所产生的部分解，不一定是可行性的。（错）15、LasVegas算法只要给出解就是正确的。（对）16、一个完全多项式近似方案是一个近似方案{Aε}，其中每一个算法Aε在输入实例I的规模的多项式时间内运行。（错）二：简答1、二叉查找树属于减治策略的三个变种中的哪一个的应用？什么情况下二叉查找树表现出最差的效率？此时的查找和插入算法的复杂性如何？答：减治策略有3个主要的变种，包括减常量、减常数因子和减可变规模。(1)二叉查找树属于减可变规模变种的应用。(2)当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于n，此时二叉查找树表现出最差的效率，(3)查找和插入算法的时间效率都属于Θ(n)。2、何谓伪多项式算法？如何将一MonteCarlo算法转化为LasVegas算法？答：若一个数值算法的时间复杂度可以表示为输入数值N的多项式，但其运行时间与输入数值N的二进制位数呈指数增长关系，则称其时间复杂度为伪多项式时间。LasVegas算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时用拉斯维加斯算法找不到解。MonteCarlo算法每次都能得到问题的解，但不保证所得解的准确性转化：可以在MonteCarlo算法给出的解上加一个验证算法，如果正确就得到解，如果错误就不能生成问题的解，这样MonteCarlo算法便转化为了LasVegas算法。3、构造AVL树和2-3树的主要目的是什么？它们各自有什么样的查找和插入的效率？答：(1)当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度等于n，此时二叉查找树表现出最差的效率，为了解决这一问题，可以构造AVL树或2-3树，使树的深度减小。一棵AVL树要求它的每个节点的左右子树的高度差不能超过1。2-3树和2-3-4树允许一棵查找树的单个节点不止包含一个元素。(2)AVL树在最差情况下，查找和插入操作的效率属于Θ(lgn)。2-3树无论在最差还是平均情况下，查找和插入的效率都属于Θ(logn)。4、写出0/1背包问题的一个多项式等价(PolynomialEquivalent)的判定问题，并说明为什么它们是多项式等价的。答：0/1背包问题：从M件物品中，取出若干件放在空间为W的背包里，给出一个能获得最大价值的方案。每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。+判定问题I：从M件物品中，取出若干件放在空间为W的背包里，是否存在一个方案，所获价值≥P*？。每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。若判定问题I存在多项式时间的解法，则反复调用该算法就可以在多项式时间内解决0/1背包的优化问题。因而这个判定问题与原问题多项式等价。5、下面问题是否属于NP问题？为什么？问题表述：给定图𝐺=(𝑁,𝐴)中的两个点𝑝、𝑞，整数𝑐和𝑡，图𝐺中每条边的长度𝑐𝑖𝑗及便利这条边的时间𝑡𝑖𝑗，问图𝐺中是否存在一条由𝑝到𝑞的路径，使得其长度大于𝑐，且遍历时间小于𝑡？答：这个问题属于NP问题。因为若给出该问题的一个解，可以在多项式时间内检验这个解的正确性。如给出一条由p到q的路径，可以在多项式时间内计算出它的长度及遍历时间，然后分别与C和t进行比较，从而可以判断这个解的对错。分治题1.写出一个求解下列问题的分治算法，推导其时间复杂性并与蛮力法相比较。给定互不相等的n个数的一个序列𝑎1,𝑎2,…,𝑎𝑛，若其中某两个数𝑎𝑖和𝑎𝑗的关系为：𝑎𝑖𝑎𝑗且𝑖𝑗，则称𝑎𝑖和𝑎𝑗是逆序的。要求计算该序列中的逆序个数，即具有逆序关系的元素对的总数目。解：/***求解n个数的一个序列，具有逆序关系的元素对的总数目*/count=0;//逆序元素对的全局计数变量mergeInvertedPairs(A,low,mid,high){i=low;j=mid+1;k=low;tmp[n];//用于归并排序的辅助数组whilei=mid&&j=high{if(A[i]A[j]){tmp[k]=A[j++];count+=(mid-i+1);//相比归并排序，就多了这一条语句}else{tmp[k]=A[i++];}k++;}whilei=mid{tmp[k++]=A[i++];}whilej=high{tmp[k++]=A[j++];}for(j=low;j=high;j++){A[j]=tmp[j];}}findInvertedPairs(A[],low,high){if(lowhigh){mid=(low+high)/2;findInvertedPairs(A,low,mid);findInvertedPairs(A,mid+1,high);mergeInvertedPairs(A,low,mid,high);}算法思路：以归并排序为基础，在两两集合合并的时候如果前一个集合的元素a[i]a[j]，那么说明需要调整次序，逆序数num=num+mid-i。时间复杂度的迭代公式为11;(n)2(n/2)(n)n1;nTTO因此算法的时间复杂度为T(n)=O(nlogn)；蛮力法的时间复杂度为O(n2)，当n数目较大时，分治法计算规模远小于蛮力法。2.A[1,…,𝑛]为一个整数序列，A中的整数𝑎如果在A中出现次数多余⌊𝑛/2⌋，那么𝑎称为多数元素。例如，在序列1,3,2,3,3,4,3中3是多数元素，因为出现了4次，大于⌊7/2⌋。求A的多数元素问题的蛮力算法复杂性如何？设计一个具有变治思想的算法，提高蛮力算法的效率，写出伪代码并分析其事件复杂性。2.num-src[0];count-0;fori-0ton-1do{if(num==src[i]){count++;}else{count--;if(count0){num-src[i];count=0;}}}采用减治的思想每一个减去一个元素，时间复杂度为O(n)，蛮力法的时间复杂度为O(n2)。动态规划题1.某工厂调查了解市场情况，估计在今后四个月内，市场对其产品的需求量如下表所示。时期（月）需要量（产品单位）12233244已知：对每个月来讲，生产一批产品的固定成本费为3（千元），若不生成，则为零。每生产单位产品的成本费为1（千元）。同时，在任何一个月内，生产能力所允许的最大生产批量为不超过6个单位。又知：每单位产品的库存费用为每月0.5（千元），同时要求在第一个月开始之初，及在第四个月末，均无产品库存。问：在满足上述条件下，该厂应如何安排各个时期的生产与库存，使所花的总成本费用最低？写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。解：设阶段序数k表示月份，状态变量xk为第k个月初拥有的单位产品数量，亦为第k-1月末时的单位产品数量，决策变量uk为第k个月生产的单位产品数量，ck为第k月份需要的产品数量，这里xk和uk均取离散变量。状态转移方程为：xk+1=xk+uk−ck,k=1,2,3,4;且x1=0。k段允许决策集合为:Dk(xk)={max⁡(0,ck−xk)≤uk≤6},⁡k=1,2,3;当k=4时，uk=ck−xk。设vk(xk,uk)为第k月的成本费,单位为(千元)，则vk=0.5∗xk+uk+I(uk),I(uk)={3,uk00,uk=0故指标函数为V1,4=∑vk4k=1令fk(xk)表示为由xk出发采用最优生产方案到第4个月结束这段期间的产品成本。根据最优化原理，则有递推公式：{fk(xk)=0,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡k=5fk(xk)={0.5∗xkuk∈Dk(xk)min+uk+I(uk)+fk+1(xk+uk−ck)},𝑘=1,2,3,4其中：ck={2,⁡⁡⁡⁡k=13,⁡⁡⁡⁡k=22,⁡⁡⁡⁡k=34,⁡⁡⁡⁡k=4逆序计算的详细步骤如下：(1)当k=4时，f4(x4)={0.5∗x4u4∈D4(x4)min+u4+I(u4)}={2⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡x4=4,⁡u4=05.5⁡⁡⁡⁡⁡x4=3,u4=16⁡⁡⁡⁡⁡⁡⁡⁡x4=2,u4=26.5⁡⁡⁡⁡⁡x4=1,u4=37⁡⁡⁡⁡⁡⁡⁡⁡⁡x4=0,u4=4(2)当k=3时，因为x4=x3+u3−c3=x3+u3−2≤4,u3+x3=x4+2∈[2,6]，且𝑢3≤6所以有：当x3=0,u3=(6,5,4,3,2),此时f3(x3)=min(11,13.5,13,12.5,12)=11,在u3=6,u4=0处取得最小值。当x3=1,u3=(5,4,3,2,1),此时f3(x3)=min(10.5,13,12.5,12,11.5)=10.5,在u3=5,u4=0处取得最小值。当x3=2,u3=(4,3,2,1,0),此时f3(x3)=min(10,12.5,12,11.5,8)=8,在u3=0,u4=4处取得最小值。当x3=3,u3=(3,2,1,0),此时f3(x3)=min(9.5,12,11.5,8)=8,在u3=0,u4=4处取得最小值。当x3=4,u3=(2,1,0),此时f3(x3)=min(9,11.5,8)=8,在u3=0,u4=4处取得最小值。当x3=5,u3=(1,0),此时f3(x3)=min(8.5,8)=8,在u3=0,u4=4处取得最小值。当x3=6,u3=(0),此时f3(x3)=min(5)=5,在u3=0,u4=0处取得最小值。(3)当k=2时，因为x3=x2+u2−c2=x2+u2−3≤6,u2+x2=x3+3∈[3,9]，且x2≤6,𝑢2≤6所以有：当x2=0,u2=(6,5,4,3)时，f2(x2)=min(17,16,17.5,17)=16,在u2=5,u3=0,u4=4处取得最小值。当x2=1,u2=(6,5,4,3,2)时，f2(x2)=min(17.5,16.5,15.5,17,16.5)=15.5,且在u2=4,u3=0,u4=4处取得最小值。当x2=2,u2=(6,5,4,3,2,1)时，f2(x2)=min(18,17,16,15,16.5,16)=15,在u2=3,u3=0,u4=4处取得最小值。当x2=3,u2=(6,5,4,3,2,1,0)时，f2(x2)=min(15.5,17.5,16.5,15.5,14.5,16,12.5)=12.5，且在u2=0,u3=6,u4