《算法分析与设计课程考试试卷》由会员分享，可在线阅读，更多相关《算法分析与设计课程考试试卷（2页珍藏版）》请在装配图网上搜索。
1、学科专业、领域：一计算机应用技术所在学院：任课教师：河北工程大学研究生20102011学年第1学期考试试卷(A )卷一、填空题(20 分，每空2分)1. 假设某算法在输入规模为n时的计算时间为T(n)=3X2n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台计算机上用同一算法在t秒内能解决 输入规模为的问题。若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒事件能解输入规模为的问题；若算法计算时间进一步改进为T(n)=8新机器可解输入规模。2. 按照渐近阶从低到高的顺序排列下列表达式：20n，4n2，logn，3n,
2、 2, n23，n!，2n。 。3. 动态规划算法的主要步骤包括刻画最优解的性质和结构、递归定义最优值、以自底向上的方式计算最 优值、根据计算最优值的相关信息构造最优解，在分析了最优解的性质和结构之后，一个比较至关重要的 步骤是给出最优值的递归定义，请给出下面问题的最优值的递归定义：最长公共子序列问题中，ci, j表示序列X.和Y.的最长公共子序列的长度，则ci, j可递归定义为： ij0i = 0, j = 0ci, j = i, j 0； x = yi j i, j 0； X 丰 yij4. 在使用回溯法考虑求解一个具体问题时，往往需要设计出约束条件和限界条件。 0-1背包问题的约束条件是
3、；限界条件是 bound，其中， bound=。5. 用贪心算法求解单源最短路径的时间复杂度为。二、解答下列问题(40分，每题8分)1. 求解递归方程cn = 1T (n)=彳aT(n /4) + cn n 12. 求解下列递归方程F(n)的通解1n = 00n = 1F(n)= 3学科专业、领域：一计算机应用技术所在学院：任课教师：3. 用贪心算法求下图顶点1到其它顶点的的最短路径。4. 有 0-1 背包问题如下：n=5, c=16, P= （8, 15，18，12, 6），W= （3, 2，10，4, 2）。画出用回溯法求解时的搜索树，并指明约束条件、限界条件。5. 设有5个矩阵A1,A2,A3,A4, A5它们的维数分别是：A1A2A3A4A520x2525x1010x1515x1010x30用动态规划方法计算矩阵连乘的最优次数mij。三、算法设计题（共40分, 1题10分, 2、3题15分）1. 设n个不同的整数排好序后存放于TO:n-l中。若存在一个下标OWin时）终止算法。此时返回的bestw即为最优解。
算法分析与设计课程考试试卷
