下载文档原格式
一、Please answer T or F for each of the following statements to indicate whether thestatement is true or false1. An algorithm is an instance, or concrete representation, for a computer programin some programming language. ( F )2. The following problem is a Decision Problem: What is the value of a bestpossible solution? ( F )3. The dynamic programming method can not solve a problem in polynomial time.( F)4. Assume that there is a polynomial reduction from problem A to problem B. Ifwe can prove that A is NP-hard, then we know that B is NP-hard. ( F )5. If one can give a polynomial-time algorithm for a problem in NP, then all theproblems NP can be solved in polynomial time. ( F )6. In an undirected graph, the minimum cut between any two vertices a and b isunique. ( F)7. Linear programming can be solved in polynomial time, but integer linearprogramming can not be solved in polynomial time. ( T )8. We can solve the maximum independent set problem in a graph with at most100 vertices in polynomial time. ( T ) 结论9. If an algorithm solves a problem of size n by dividing it into two subproblems ofsize n/2, recursively solving each subproblems, and then combine the solutions in linear time. Then the algorithm runs in O(n log n) time. ( T )10. Neural Computation, Fuzzy Computation and Evolution Computing are thethree research fields of Computational Intelligence. ( T )二、Given the following seven functions f1(n) = n5+ 10n4, f2(n) = n2+ 3n, f3(n) =f4(n) = log n + (2log n)3, f5(n) = 2n+n!+ 5e n, f6(n) = 3log(2n) + 5log n, f7(n) = 2n log n+log n n. Please answer the questions:第 1 页共5 页(a) Give the tight asymptotic growth rate (asymptotic expression with θ) to eachof them; (7分)(b) Arrange them in ascending order of asymptotic growth rate。
算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。
2.程序：程序是算法⽤某种程序设计语⾔的具体实现。
⼆、简答题：1.算法需要满⾜哪些性质？简述之。
答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。
（2）输出：算法产⽣⾄少⼀个量作为输出。
（3）确定性：组成算法的每条指令清晰、⽆歧义。
（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。
2.简要分析分治法能解决的问题具有的特征。
答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。
3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。
答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。
该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。
（2）⽤递推来实现递归函数。
（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。
后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。
三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。
答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。
（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。
算法设计与分析1.简述算法定义、属性及指标算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
算法具有以下几个属性：●输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
●输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
●有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
●确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出口●可行性（可选）：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
质量指标：●正确性：算法应满足具体问题的需求；●可读性：算法应该好读，以有利于读者对程序的理解；●健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
●效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
2.什么是算法分析，怎么做算法设计●算法分析分为算法正确性分析和复杂性分析。
1.算法正确性分析确保算法对符合要求的输入在有限时间内能产生正确的结果。
2.算法的复杂性分析,分析算法对不同输入所需资源量,为求解一个问题选择最佳算法、最佳设备。
●怎么做算法设计：1.确定算法解决问题的目标，也是问题需求分析；2.分析问题输入输出的数据类型及结构；3.尝试匹配已有的算法解决方案，选择合适的算法模型；4.对算法模型的参数或局部计算过程进行设计；5.检查算法运行的效果并进行改进，使其达到最优；对于一些未知领域的算法设计方式更像是艺术而不像是科学，需要基础领域知识结合计算机算法技术来实现。
3.什么是算法复杂性算法复杂性包括时间复杂度和空间复杂度。
时间复杂度指程序执行时所用的时间；空间复杂度指算法占用的空间（两种占用：存储程序和输入数据的空间、存储中间结果或操作单元所占用空间——额外空间）。
一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
二、综合题（50分）1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
2019电⼦科技⼤学研究⽣试卷答案电⼦科技⼤学研究⽣试卷（考试时间：⾄，共 2 ⼩时）课程名称图论及应⽤教师学时 60 学分 3 教学⽅式堂上授课考核⽇期 2019 年 5 ⽉⽇成绩考核⽅式：（学⽣填写）⼀．填空题(每空3分，共15分) 1. 图G 的邻接矩阵为0111101111001100?? ? ? ? ? ???, 则G 的⽣成树的棵数为 8 . 2. 设1G 是11(,)n m 简单图,2G 是22(,)n m 简单图,则1G 和2G 的(Cartesian)积图12G G ?的边数()m G =1221n m n m +. 3. 图1中最⼩⽣成树T 的权值()W T = 23 .4. 图2中S 到T 的最短路的长度为 8 .5. 设G 是n 阶简单图,且不包含三⾓形,则其边数⼀定不超过24n . ⼆．单项选择题(每题3分，共15分) 学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………⽆……………效……………………座位号图1 图21. 关于彼得森(Petersen)图, 下⾯说法正确的是 ( B )A. 彼得森图是哈密尔顿图;B. 彼得森图是超哈密尔顿图;C. 彼得森图可1-因⼦分解;D. 彼得森图是可平⾯图.2. 下⾯说法正确的是 ( C )A. 有割点的三正则图⼀定没有完美匹配;B. 有割边的三正则图⼀定没有完美匹配;C. 存在哈密尔顿圈的三正则图必能1因⼦分解;D. 正则的哈密尔顿图必能2因⼦分解.3. 关于图的度序列, 下⾯说法正确的是 ( B )A. 任意两个有相同度序列的图都同构;B. 若图G 度弱于图H ，则图G 的边数⼩于等于图H 的边数;C. 若⾮负整数序列12(,,,)n d d d π=满⾜1ni i d =∑为偶数，则它⼀定是图序列;D. 如果图G 所有顶点的度和⼤于或等于图H 所有顶点的度和，则图G 度优于图H.4. 关于图的补图, 下⾯说法错误的是 ( A )A. 若图G 连通，则其补图必连通;B. 若图G 不连通，则其补图必连通;C. 图G 中的⼀个点独⽴集，在其补图中的点导出⼦图必为⼀个团;D. 存在5阶的⾃补图.5. 关于欧拉图, 下⾯说法正确的是 ( D )A. 每个欧拉图有唯⼀的欧拉环游;B. 每个顶点的度均为偶数的图是欧拉图;C. 欧拉图中⼀定没有割点;D. 欧拉图中⼀定没有割边.(三).(10分)若阶为25且边数为62的图G 的每个顶点的度只可能为3，4，5或6，且有两个度为4的顶点，11个度为6的顶点，求G 中5度顶点的个数。
5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty . (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。
电子科技大学研究生算法设计与分析拟考题及答案评分细则（3）一、Please answer T or F for each of the following statements to indicate whether the statement is true or false1. The knapsack problem can be solved in polynomial time by using dynamic programming.( F )2. Some problems in NP can be solved in polynomial time.( T )3. To show a problem is NP-hard, we can reduce it to a well-known NP-Complete problem.( F )4. In an undirected graph, the value of the maximum flow between two vertices is equivalent to the value of the minimum cut between them. ( T )5. . ( F )二、Arrange the following functions in ascending asymptotic order of growth rate:，，，，.参考答案：f2，f3，f1，f4，f5三、Please answer the following questions:(a) What are the main steps of designing a dynamic programming algorithm?参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解（建立储存表）。
(b) What are the main steps of proving the NP-Completeness of a problem?参考答案：1.证明该问题属于NP；2.选一个已知的NPC问题B；3.将问题B归约到该问题上。
第 1 页 共 6 页一、Please answer T or F for each of the following statements to indicate whetherthe statement is true or false1. The knapsack problem can be solved in polynomial time by using dynamic programming.( F )2. Some problems in NP can be solved in polynomial time.( T )3. To show a problem is NP-hard, we can reduce it to a well-known NP-Complete problem.( F )4. In an undirected graph, the value of the maximum flow between two vertices is equivalent to the value of the minimum cut between them. ( T )5. log 2)n n O =. ( F )二、Arrange the following functions in ascending asymptotic order of growth rate:log 1001()5log n f n n n n =+，log loglog 2()2n n f n +=，3()f n =，24()2n f n n =+，5()(2log )n f n n =+.参考答案：f2，f3，f1，f4，f5三、Please answer the following questions:(a) What are the main steps of designing a dynamic programming algorithm? 参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解（建立储存表）。
(b) What are the main steps of proving the NP-Completeness of a problem? 参考答案：1.证明该问题属于NP ；2.选一个已知的NPC 问题B ；3.将问题B 归约到该问题上。
四、The Traveling salesman problem (TSP) is defined as follows: Given a graph,the task is to find a shortest possible route that visits each vertex exactly once and returns to the origin vertex.Fig. 1For the graph shown in Fig. 1,(a) find a solution to TSP ((the route is starting from A and back to A);(b) find a longest directed cycle that contains vertex A.参考答案：|（a）A->D->C->B->A 35+12+30+20=97（b）A->C->B->D->A 42+30+34+35=141五、Design an algorithm for the following Interval Scheduling problem: There aren jobs each of which has a starting time s and a finishing time f. Two jobs are compatible if they don’t overlap. The goal of the problem is to find a maximum set of mutually compatible jobs.参考答案及评分标准：将所有工作（Interval）按其完成时间的先后进行排序；在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。
六、Find a minimum s-t cut in the following graph (the number beside the edge isthe capacity of the edge). You are required to give the computation steps and show the size of the cut.第 2 页共6 页参考答案：35. 有两个解：{S，4，3，8}和{S，1，2，3，4，5，6，7，8，9}评分标准：说明计算该图从s到t的最大流给出第一个增广连后面任意两个增广连（最后答案35和这个cut七、Prove that if we can check if a graph has a path of length k in polynomial timethen we can also find a path of length k in polynomial time.参考答案及评分标准：依次从图中删除一条边，然后检查是否还存在长度为k的路径，如果存在则直接删除，如果不存在则保留该边。
如此下去，最后图只剩下k条边。
以上思想正确给全分。
八、A Hamiltonian cycle in a graph is a cycle that contains each vertex. TheHamiltonian Cycle problem is to find a Hamiltonian cycle in a graph. The Constrained Hamiltonian Cycle problem is to find a Hamiltonian cycle passing through some given edges in the graph.Give a polynomial reduction from the Constrained Hamiltonian Cycle problem to the Hamiltonian Cycle problem.参考答案及评分标准：在每个给出的要求通过的边上添加一个顶点（度数第 3 页共6 页第 4 页 共 6 页为2），这样Hamilton cycle 就必须通过这些边了。
以上思想正确给全分。
九、Answer the following questions.Given a graph G with nonnegative vertex weight, the Weighted Vertex Cover problem is to find a minimum vertex set (the weight of vertices in the set is minimized) such that each edge in the graph has at least one endpoint in the set. (a) Please give an integer programming formulation of the Weighted Vertex Cover problem.(b) Give a 2-approximation algorithm based on linear programming.(c) Prove that your algorithm guarantees the approximation ratio 2.参考答案及评分标准：（a ） min ..1for each edge 0or 1for each vertex ii j i j i ix s t x x x x x x +≥=∑ （b ） 将以上整数规划改为线性规划：将约束条件0or 1for each vertex i i x x =改为01for each vertex i i x x ≤≤，并且将解中x_i 值大于等于0.5的选入点覆盖中。
（c ）证明在教材在有。
大体思路对可以给全分。
十、There are m machines and n=2m+1 jobs, where two of jobs has length of(m+1,m+2, m+3, …, 2m) respectively, and one job has length of m. Each job must be processed contiguously on a machine and each machine can process at most one job at a time. You are asked to assign jobs to machines to minimize the makespan (the longest processing time on any machine).(a) Give an approximation solution by using the longest processing time first第 5 页 共 6 页(LPT) algorithm. (give the main idea of LPT and the final solution)(b) Try to find an optimal solution for this problem.参考答案及评分标准：（a ）LPT 算法基本思想是将任务按照处理时间长度降序排列，总是将处理时间最长的任务分配到目前负载最低的机器上。
（b ）The optimal solution of the minimizing the makespan is 3m+2. 因为所有任务长度之和是3m^2+2m, 共有m 个机器，每个机器都分配相同长度的任务（3m^2+2m ）/m=3m+2.十一、 Given a graph, the Vertex Cover problem is to find a minimum subset ofvertices such that each edge has at least one endpoint in it; the Independent Set problem is to find a maximum subset of vertices such that there is no edge between any two vertices in it, and the Clique problem is to find a maximum subset of vertices such that there is an edge between any two vertices in it. Please give a polynomial reduction from the Vertex Cover problem to the Independent Set problem and a polynomial reduction from the Independent Set problem to the Clique problem.参考答案及评分标准：VC 到IS 的归约：图中除去vertex cover 中的点剩下的点就是一个independent set 。
