《算法分析与设计试卷2019-2020》

完成布线Р Q.Add(nbr);} Р }Р8.f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O(    )Р9.分治算法的时间复杂性常常满足如下形式的递归方程：Р Р 其中，g(n)表示 。Р10.在忽略常数因子的情况下，O、和三个符号中， 提供了算法运行时间的一个上界。Р11.许多可以用贪心算法求解的问题一般具有2个重要的性质： 性质和 性质。Р12.动态规划和分治法在分解子问题方面的不同点是 。Р三、问答题（30分，每题6分）。Р1. 设计动态规划算法的主要步骤是怎么的？请简述。Р2.何谓最优子结构性质？Р3.何谓P、NP、NPC问题Р4.简单描述回溯法基本思想。Р5.用O、、表示函数f与g之间阶的关系，并分别指出下列函数中Р阶最低和最高的函数：Р(1)　f (n)=100 g(n)= Р(2) f(n)=6n+n g(n)=3nР(3) f(n)= n/logn-1 g(n)=Р四、算法设计与分析（26分,1题11分，2题15分）。Р1.分别动态规划法、回溯法设计0-1背包问题。Р要求：说明所使用的算法策略；写出算法实现的主要步骤；Р分析算法的时间。Р一个旅行者要驾车从A地到B地，A、B两地间距离为s。РA、B两地之间有n个加油站，已知第i个加油站离起点A的距离为Р公里，0=，车加满油后可行驶m公里，出发之前汽车Р油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心Р法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最Р优解的贪心算法，并分析算法的时间复杂性。