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