算法设计和分析参考试卷.doc

……………………………………………装………………………………订…………………………线……………………………………………………… 此处不能书写 此处不能书写 此处不能书写 此处不能书写 此处不能书写 此处不能书写 此处不能书写 第PAGE 2页 共 NUMPAGES 3页 第  PAGE 3 页 共  NUMPAGES 3 页 算法设计与分析参考试卷 一、单项选择题 1. 当输入规模为n时，下列算法渐进复杂性中最低的是（A ）。 A. 5n B. n2 C. 2n2 D. 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．出于“平衡子问题”的思想，通常分治法在分解原问题时，形成若干子问题，这些子问题的规模都大致 相同 。 三、简答题 简述单源最短路径问题，该问题适合采用什么方法求解。 二分有哪些信誉好的足球投注网站要解决什么问题?二分有哪些信誉好的足球投注网站如何体现分治的思想?简述二分有哪些信誉好的足球投注网站算法的步骤. 什么是0-1背包问题?用动态规划解决0-1背包问题时,它的最优子结构(问题)是什么?简述0-1背包问题的动态规划算法. 什么是图的m着色问题?图的m着色问题的解空间是什么?简述回溯法解决图的m着色问题算法步骤. 什么是旅行售货员问题?它的解空间是什么?简述分支限界法解决旅行售货员问题的算法步骤 四、分析、计算题 1．考虑矩阵的连乘积问题。设有3个矩阵A、B、C，它们的维数分别为2×3、3×4、4×3，试分别按（（AB）C）、(A(BC))的计算顺序，给出它们的计算量（数乘次数）。 五、算法设计题 圆排列回溯算法中，用文字或C/C++语言片段给出当前圆排列长度的计算以及圆心坐标的计算过程。