算法设计与分析参考试卷

第1页共3页……………………………………………装………………………………订…………………………线………………………………………………………此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写算法设计与分析参考试卷一、单项选择题1.当输入规模为n时，下列算法渐进复杂性中最低．的是（A）。A.5nB.n2C.2n2D.n!2.二分搜索算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法3．最大效益优先是（A）的一种搜索方式。A．分支界限法B．动态规划法C．贪心法D．回溯法4.回溯法搜索状态空间树是按照（C）的顺序。A．中序遍历B．广度优先遍历C．深度优先遍历D．层次优先遍历5.回溯法解旅行售货员问题时的解空间树是（B）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（B）。A、备忘录法B、动态规划法C、贪心法D、回溯法7．下列算法中通常以深度优先方式系统搜索问题解的是（D）。A、备忘录法B、动态规划法C、贪心法D、回溯法8．快速排序算法是利用（A）实现的算法。A．分治策略B．动态规划法C．贪心法D．回溯法二、填空题1.通俗地讲，算法是指解决问题的一种方法或一个过程。2．出于“平衡子问题”的思想，通常分治法在分解原问题时，形成若干子问题，这些子问题的规模都大致相同。三、简答题1．简述单源最短路径问题，该问题适合采用什么方法求解。第2页共3页2．二分搜索要解决什么问题?二分搜索如何体现分治的思想?简述二分搜索算法的步骤.3．什么是0-1背包问题?用动态规划解决0-1背包问题时,它的最优子结构(问题)是什么?简述0-1背包问题的动态规划算法.4．什么是图的m着色问题?图的m着色问题的解空间是什么?简述回溯法解决图的m着色问题算法步骤.5．什么是旅行售货员问题?它的解空间是什么?简述分支限界法解决旅行售货员问题的算法步骤四、分析、计算题1．考虑矩阵的连乘积问题。设有3个矩阵A、B、C，它们的维数分别为2×3、3×4、4×3，试分别按（（AB）C）、(A(BC))的计算顺序，给出它们的计算量（数乘次数）。五、算法设计题圆排列回溯算法中，用文字或C/C++语言片段给出当前圆排列长度的计算以及圆心坐标的计算过程。第3页共3页……………………………………………装………………………………订…………………………线………………………………………………………此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写此处不能书写