一、    填空题
1、    算法是指解决问题的（    ）或（    ）。
2、    直接或间接地调用自身的算法称为（    ）。
3、    用”分治法”设计出的算法一般是（    ）。
4、    动态规划算法的基本思想是将待求解问题分解成若干（    ），先求解（    ），然后从
这些（    ）的解得到原问题的解。
5、    问题的（    ）是该问题可用动态规划算法或贪心算法求解的关键特征。
6、    以深度优先方式系统搜索问题解的算法称为（    ）。
7、    算法的“确定性”指的是组成算法的每条（）是清晰的，无歧义的。
8、    用函数自身给岀定义的函数称为（    ）。
9、    二分搜索算法是利用（    ）设计的。
10、    矩阵连乘问题的算法可由（    ）设计实现。
11、    （    ）是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
12、    回溯法是一个既带有（    ）又带有（    ）的搜索算法。
13、    程序是（    ）用某种程序设计语言的具体实现。
14、    使用（    ）可以使函数的定义和算法的描述简洁且易于理解。
15、    大整数乘积算法是用（    ）来设计的。
16、    动态规划算法的两个基本要素是（    ）和（    ）。
17、    （    ）是贪心算法与动态规划算法的共同点。
18、    以广度优先或以最小耗费方式搜索问题解的算法称为（    ）。
19、    （    ）是算法运行所需的计算机资源的量，需要时间资源的量称为（    ），需要空
间资源的量称为（    ）。
20、    时间复杂性渐近分析记号包括：渐近上界记号（    ），渐近下界记号（    ），非紧
上界记号（    ），同阶记号（    ）。
21、    两种分支限界法分别是（    ）和（    ）。
二、    选择题
1、    Strassen矩阵乘法是利用（    ）实现的算法。
A、分治策略B、动态规划法 C、贪心法 D、回溯法
2、    下列是动态规划算法基本要素的是（    ）。
A、重叠子问题 B、构造最优解 C、算出最优解 D、定义最优解
3、    下列算法中通常以自底向上的方式求解最优解的是（    ）。
A、备忘录法    B、动态规划法 C、贪心法 D、回溯法
4、    下面不是分支界限法搜索方式的是（    ）。
5、    0-1背包问题的回溯算法所需的计算时间为(    )
A、O (n2n) B、O (nlogn) C、O (2n) D、O (n)
6、    合并排序算法是利用(    )实现的算法。
A、分治策略B、动态规划法 C、贪心法 D、回溯法
7、    下列是动态规划算法基本要素的是(    )。
A、最优子结构B、构造最优解 C、算出最优解 D、定义最优解
8、    下列算法中通常以自顶向下的方式求解最优解的是(    )。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
9、    广度优先是(    )的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
10、    背包问题的贪心算法所需的计算时间为(    )
A、O Cn2n) B、O (nlogn) C、O (2n) D、O (n)
三、简答题
1、    简述分治法、贪心法、动态规划法、回溯法和分支限界法的基本思想。
2、    简述分治法与动态规划法的异同。
3、    写出设计动态规划算法的主要步骤。
4、    举例说明贪心算法与动态规划算法的的主要差别。
5、    简述用回溯法设计算法的步骤。
6、    简述分支限界法与回溯法的异同。
7、    写出用回溯法搜索子集树的一般算法。
8、    写出用回溯法搜索排列树的算法。
9、    写出设计快速排序算法的主要步骤。
10、    简述队列式分支限界法和优先队列分支限界法。
11、    针对A ckerman函数的递归定义，对给定的一个A (n.m),给岀结果(如求A(3,2)的值)
12、    针对整数划分问题的递归定义，对给定的q(n,m),给出结果(如求q(6,6)的值)。
13、    例说明最小生成树在实际中的应用。
14、    写出用动态规划算法求解矩阵连乘问题的主要步骤，写出递归关系式。
15、    写出用动态规划算法求解最长公共子序列问题的主要步骤，写出递归关系式。
16、    写出动态规划算法求解0—1背包问题的主要步骤，写出递归关系式。
17、    简述利用贪心算法解决“单源最短路径”问题的基本思想。
18、    简述用回溯法解决“旅行商售货问题”的基本思想。
19、    简述用分支限界法解决“旅行商售货问题”的基本思想。
20、    简述用回溯法解决“0—1背包问题”的基本思想。
21、    简述用分支限界法解决“0—1背包问题”的基本思想。
22、画出用回溯法解n后问题的解空间(指定n的值)，写出约束函数和递归回溯函数。皇后
放置的约束条件。
四、算法设计题
1、0-1背包问题：给定n种物品和―背包，物品i的重量是w“其价值为v“背包的容量为 C。问应该如何装入背包中物品的总价值最大？写出用动态规划、回溯法、分支限界法设计解决该问 题的算法。
3、考虑如下的0/1背包问题：
n=4,w=(4,6,3,2),p=(10,15,6,4),M=12,考虑用优先队列分支限界法解此问题，但不必写出算法。
(1)画出执行你的算法搜索解空间树时所生成的子树；
(2)给出该问题的一个最优解。
4.用动态规划算法解多段图问题，即求从源点s到目标点t的最短路径:
(1)说明多段图问题具有最优子结构性质；
(2)写出多段图问题最优值的递推公式；
(3)给出下图问题的一个最优解。
5、多机调度问题：设有n个独立的作业{1, 2,    n},由m台相同的机器进行加工处理。作
业i所需的处理时间为t”现约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中 断处理，作业不能拆分成更小的子作业，求解完成所有作业的最少时间。试写出用贪心算法解决该 问题的算法。给出一个实例，用图示法描述多机调度(如P121图4-12) o
6、    考虑用贪心算法求加权无向图的最小牛成树：
(1)叙述Kruskal算法的基本思想(或步骤)；
(2)证明Kruskal算法对于每一个无向连通图G都产生一棵最小生成树。
7、    下面是归并排序算法：
MergeSort(int low, int high) // A[low : high]是一个全程数组，含有 high-low+1 个待排序的元素 { if(low<high)
{mid=(low+high)/2; 〃求当前数组的分割点
MergeS ort(low,mid); 〃将第一子组排序
MergeSort(mid+l,high); //将第二子组排序
Merge(low,mid,high): 〃合并两个已经排序的子数组
}
}
用T(n)表示执行该程序所用时间，并假定T(l) = n,合并子程序Merge所用时间与n成正比， 即cn, c是正实数。
(1)写出该程序所用时间T(n)的递推关系式；
(2)第一范式正则化不能产生稀疏解当n=2'■时，解上述递推关系式得到T(n)的表达式；
(3)证明,对于一般的n,有T(n)=O(nlogn)。
8、    按照要求完成以下各题：
(1)对数组A={ 15,29,135,18,32丄27,25,5},用快速排序方法将其排成递减序列；
(2)请描述递减数组进行二分搜索的基本思想，并给出非递归算法；
(3)给出上述算法的递归算法；
(4)使用上述算法对(1)所得到的结果搜索如下元素：18,31,135,并给出搜索过程。
9、    批处理作业调度问题：给定n个作业，每个作业都有两项任务分别在两台机器中完成，先 由机器1完成，再由机器2完成，所有作业在机器1和机器2上执行的顺序一致。所有作业在机器 2上完成时间和为该作业调度的完成时间，制定最佳作业调度方案，使其完成时间和达到最小。试 写出用回溯法解决该问题的算法。给出实例(如书中P150中的例子)的解空间树，得出最优解。
10、    电路板排列问题：将n块电路板以最佳排列方案插入带有n个插槽的机箱中，n块电路板 的不同排列对应于不同的电路板插入方案。试写出用分支限界算法解决该问题的算法。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。