算法设计与分析模拟试卷(精选)

1． 按分治策略求解棋盘覆盖问题时，对于如图所示的24×24的特殊棋盘，共需要多少个L 型骨牌；并在棋盘上填写L 型骨牌的覆盖情况。

2． 假设有7个物品，给出重量和价值。

若这些物品均不能被分割，且背包容量M ＝140，使用回溯方法求解此0-1背包问题。

请画出状态空间搜索树。

3． 假设有7个物品，它们的重量和价值如下表所示。

若这些物品均可以被分割，且背包容量M＝140，使用贪心算法求解此背包问题。

请写出求解策略和求解过程。

W （35,30,50,60,40,10,25）p （10,40,30,50,35,40,30）4． 在给出的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a 到b 的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。

5． 画出字符表的哈夫曼编码对应的二叉树。

6． 已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=8，r 5=5，r 6=20，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序。

7． 给出城市网络图，售货员要从城市1出发，经过所有城市回到城市1，画出该问题的解空间树，描述出用优先队列式分支限界法求解时的搜索情况。

表示出优先队列、当前扩展结点等的变化情况。

8． 依据优先队列式分支限界法，求从s 点到t 点的单源最短路径，画出求得最优解的解空间树。

一、假设有7个物品，它们的重量和价值如下表所示。

若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。

请写出状态空间搜索树（20分）。

答：按照单位效益从大到小依次排列这7个物品为：FBGDECA 。

将它们的序号分别记为1～7。

则可生产如下的状态空间搜索树。

其中各个节点处的限界函数值通过如下方式求得：【排序1分】5x =6x =7x =17分，每个节点1分】a ．1501154040305035190.62540-++++⨯=7(1,1,1,1,,0,0)8b. 1501154040305030177.560-++++⨯=7(1,1,1,1,0,,0)12c ．4040305010170++++=(1,1,1,1,0,0,1)d. 1501054040303530167.560-++++⨯=3(1,1,1,0,1,,0)4e. 150130404050353017560-++++⨯=1(1,1,0,1,1,,0)3f. 1501304040503510170.7135-++++⨯=4(1,1,0,1,1,0,)7g. 40405030160+++=(1,1,0,1,0,1,0)h. 1501404040353010146.8535-++++⨯=2(1,1,0,0,1,1,)7i.1501254030503530167.560-++++⨯=5(1,0,1,1,1,,0)12 j. 1501454030503530157.560-++++⨯=1(0,1,1,1,1,,0)12在Q 1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。

算法分析与设计试卷及参考答案济南⼤学继续教育学院算法分析与设计试卷（A）学年：学期:年级：专业：学习形式：层次：（本试题满分100分，时间90分钟）⼀、单选题（每⼩题2分，共计20分。

）1. 下列情况不适合使⽤计数排序的是（）。

A 要排序的数据表的数量很⼤B 要排序的数据表中有相同的关键字C 要排序的数据表基本有序D 要排序的数据表元素各不相同2. 集合｛Ａ，Ｂ｝的幂集合为（）。

Ａ．｛Ａ｝，｛Ｂ｝Ｂ．｛Ａ｝，｛Ｂ｝，ΦC． { ｛Ａ｝，｛Ｂ｝} D {｛Ａ，Ｂ｝，｛Ａ｝，｛Ｂ｝，Φ}3．下列字符串序列不符合字典排序的是（）。

A． abc acb bca B. abc acb cbaC． bac bca abc D abc bac bca4．对于根树，出度为零的节点为（）。

Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分⽀节点5．对完全⼆叉树⾃顶向下，从左向右给节点编号，节点编号为１0的⽗节点编号为（）。

Ａ０Ｂ２Ｃ４Ｄ６6．下列程序段的算法时间的复杂度为（）。

for i ←0 to n dofor j ←0 to m do s //某种基本操作A O（n2）B O(m2)C (m+n)D O(m*n)7.三个盘⼦的汉诺塔，⾄少要执⾏移动操作的次数为 ( )。

A 1次B 3次C 6次D 7次8．与算法英⽂单词algorithm具有相同来源的单词是（）。

A logarithmB algirosC arithmosD algebra9．从排序过程是否完全在内存中显⽰，排序问题可以分为（）。

Ａ稳定排序与不稳定排序Ｂ内排序与外排序Ｃ直接排序与间接排序Ｄ主排序与辅助排序10．下列（）不是衡量算法的标准。

Ａ时间效率Ｂ空间效率Ｃ问题难度Ｄ适应能⼒⼆、简答题（每题8分，共计24分。

）1．贪婪技术的基本思想是什么？它有哪些应⽤（给出2种）？2. 拓扑排序的基本思想是什么？它可⽤于哪些实际问题中（给出2种）？3．是么是算法，算法与程序有什么区别？三、算法设计题（每题14分，共计56分。

科技学院二○ 年 学期期末考试信息与计算科学专业年级《算法设计与分析》 试题考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 一、填空题（每小题3 分，共计30 分）1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

()()log log f n n n g n n ==2. 算法的时间复杂性为1,1()8(3/7),2n f n f n n n =⎧=⎨+≥⎩，则算法的时间复杂性的阶为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。

8. ____________________________是问题能用动态规划算法求解的前提。

9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。

10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）1. 试述回溯法的基本思想及用回溯法解题的步骤。

题 号 一二三四五总分 统分人得 分 阅卷人复查人2. 有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。

算法设计与分析试题(总4页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《算法设计与分析》期末考试试题（A卷）一、选择题：试题说明：本题包含12个小题，占24分；请将正确答案填写在题目左侧的括号内。

（）1、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（）。

A．求解目标不同，搜索方式相同B．求解目标不同，搜索方式也不同C．求解目标相同，搜索方式不同D．求解目标相同，搜索方式也相同（）2、回溯法在解空间树T上的搜索方式是（）。

A．深度优先B．广度优先C．最小耗费优先D．活结点优先（）3、回溯算法和分支限界法的问题的解空间树不会是（）。

A．有序树B．子集树C．排列树D．无序树（）4、在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。

A．回溯法B．分支限界法C．回溯法和分支限界法D．回溯法求解子集树问题（）5、从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（）之外都是最常见的方式。

A．队列式分支限界法B．优先队列式分支限界法C．栈式分支限界法D．FIFO分支限界法（）6、概率算法是一种非确定性地选择下一计算步骤的方法，力图消除问题复杂性与具体实例间的关联，以下算法暗中适合于求解问题近似解的是（）。

A．数值概率算法B．蒙特卡罗算法C．拉斯维加斯算法D．舍伍得算法（）7、（）能够求得问题的解，但却无法有效地判定解的正确性。

A．数值概率算法B．蒙特卡罗算法C．拉斯维加斯算法D．舍伍得算法（）8、下面算法实现的是素数测试，该方法使用的数学原理是（）。

A．费尔马小定理B．费尔马定理C．Wilson定理D．二次探测定理（）9、以下关于判定问题难易处理的叙述中正确的是（）。

A．可以由多项式时间算法求解的问题是难处理的B．需要超过多项式时间算法求解的问题是易处理的C．可以由多项式时间算法求解的问题是易处理的D．需要超过多项式时间算法求解的问题是不能处理的（）10、设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N，使得当N≥N时有f（N）≤Cg（N），则称函数f（N）当N充分大时有上界g（N），记作f（N）=O（g（N）），即f（N）的阶（）g（N）的阶。

《算法设计与分析》答卷说明： 1、考试方式闭卷2、满分100分题号一二三四五六七总分总分人分数得分评卷人一、单项选择题（每小题2分，共20分）1、下面关于NP问题说法正确的是（）。

A 、NP问题都是不可能解决的问题B 、P类问题包含在NP类问题中C 、NP完全问题是P类问题的子集D 、NP类问题包含在P类问题中2、能采用贪心算法求最优解的问题，一般具有的重要性质为：（）A、最优子结构性质与贪心选择性质B、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质D、预排序与递归调用3、实现合并排序利用的算法是（）。

A、分治策略B、动态规划法C、贪心法D、回溯法4、以下不可以使用分治法求解的是（）。

A、棋盘覆盖问题B、选择问题C、归并排序D、0/1背包问题5、记号O的定义正确的是（）。

A、O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤cg(n) }；B、O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤f(n) }；C、O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n>0使得对所有n≥n0有：0 ≤f(n)<cg(n) }；D、O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n>0使得对所有n≥n0有：0 ≤cg(n) < f(n) }；6、使用分治法求解不需要满足的条件是（）。

A、子问题必须是一样的B、子问题不能够重复C、子问题的解可以合并D、原问题和子问题使用相同的方法解7、以下关于渐进记号的性质是正确的有：（）A、f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ⇒=ΘB、f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==⇒=C、O(f(n))+O(g(n)) = O(min{f(n),g(n)})D、f(n)O(g(n))g(n)O(f(n))=⇔=8、衡量一个算法好坏的标准是（）。

一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外,算法还应具有以下五个重要特性：_________,________,________，__________，__________。

2。

算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。

3。

某一问题可用动态规划算法求解的显著特征是____________________________________.4.若序列X={B，C,A，D,B，C,D},Y={A，C，B,A，B，D，C,D}，请给出序列X和Y的一个最长公共子序列_____________________________.5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。

6。

动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。

7。

以深度优先方式系统搜索问题解的算法称为_____________。

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________.9。

动态规划算法的两个基本要素是___________和___________。

10。

二分搜索算法是利用_______________实现的算法。

二、综合题（50分）1。

写出设计动态规划算法的主要步骤。

2.流水作业调度问题的johnson算法的思想。

3。

若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2，a3,a4)=（4，5，12,10），(b1,b2,b3，b4)=（8，2，15,9)求4个作业的最优调度方案，并计算最优值。

4。

使用回溯法解0/1背包问题：n=3，C=9，V={6，10，3｝，W={3,4，4}，其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。

湖南科技学院二○ 年 学期期末考试信息与计算科学专业 年级《算法设计与分析》 试题考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 一、填空题（每小题3 分，共计30 分）1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

()()log log f n n n g n n ==2. 算法的时间复杂性为1,1()8(3/7),2n f n f n n n =⎧=⎨+≥⎩，则算法的时间复杂性的阶为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。

8. ____________________________是问题能用动态规划算法求解的前提。

9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。

10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）1. 试述回溯法的基本思想及用回溯法解题的步骤。

2. 有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。