returnMax,Min
其时间复杂度是（）。
B.2（n-1）
C51.下面是贪心算法的基本要素的是（）。
C.贪心选择性质
C52.分治法所能解决的问题应具有的关键特征是（）。
C.利用该问题分解出的子问题的解可以合并为该问题的解
A53.在钢管切割问题里，如果用rn表示长度为n英寸的钢管的最优切割方案所获得的最大收益，且已知rn所代表的最优解里，第一刀切下了3英寸，则下述公式正确的是（）。
A.rn=p3+rn-3
D54.（）是贪心算法与动态规划算法的共同点。
D.最优子结构性质
B55.下列关于选择排序和冒泡排序的稳定性的说法，正确的是（）。
B.选择排序是不稳定的，冒泡排序是不稳定的。
A56.使用分治法求解不需要满足的条件是（）。
A.子问题必须是一样的
C57.在流网络中，对于源节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
C.在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
D58.递归算法不能适用以下场合（）。
D.概率问题
A59.在最优二叉搜索树问题中，定义e[i,j]为ki,...,kj的最优二叉查找树的期望搜索成本，而我们需要通过寻优来确定最优二叉查找树的根结点的下标r,则r的取值范围为（）。
A.i≤r≤j
D60.程序可以不满足算法性质的（）。
D.有限性
二、判断题（本大题共0分，共60小题，每小题0分）
×1.对于矩阵链连乘的子问题m[i,j]，当i=j时表明该矩阵链有两个矩阵。
（）
×2.算法就是一组无穷的规则（）
√3.问题的规模越小，解题所需的计算时间往往也越少，从而也较容易处理。
（）
√4.动态规划和分治法在分解子问题方面的不同点是前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的（）。
√5.每一个递归定义都有其边界条件。
（）
√6.贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择。
（）
√7.用浮点数来表示大型整数，只能近似地表示它的大小。
（）
√8.多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。
（）
√9.子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。
（）
×10.裴波那契数列的定义：
f（n）=f（n-1）+f（n-2）,f（0）=1,f
（1）=2，其数据的定义形式不是按递归定义。
（）
√11.程序性能是指运行一个程序所需的内存大小和时间多少。
（）
×12.一个操作所需的时间和操作数的类型无关（）
√13.要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。
（）
√14.在JAVA语言中,执行特定认为的任务的函数或过程统称为方法。
（）
√15.与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相不独立的（）。
√16.归并排序是指将数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。
如果分割后子问题还很大，则继续分治，直到一个元素。
（）
×17.与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相独立的（）。
√18.对所有问题,贪心算法不能都得到整体最优解（）。
√19.算法重要特性是确定性、可实现性、输入、输出、有穷性（）。
√20.0-1背包问题，无论物件的顺序如何排列，动态规划总能获得最优解。
（）
√21.指数时间算法只有在n取值非常小时才实用。
（）
√22.动态规划法其具体形式是多种多样的，但都具有相同的填表格式。
（）
√23.一般来说，对一个有序序列二分法（即把任意大小的问题尽可能地等分为两个子问题）较为有效。
（）
×24.如果各子问题是不独立的，一般用动态规划法比分治法较差。
（）
√25.动态规划对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
（）
×26.当一个问题具有最优子结构性质时只能用动态规划方法求解。
（）
×27.Huffmann编码树所对应的编码并不一定是前缀码。
（）
√28.通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理。
×29.问题的计算复杂性一般是随着问题规模的增加而减小。
（）
√30.子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。
（）
×31.Prim算法是一种动态规划算法。
（）
√32.标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。
（）
√33.问题解法按递归算法实现的问题适用于递归求解。
（）
√34.一般认为，执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
（）
√35.如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为多阶段决策问题。
（）
√36.对于矩阵链连乘的子问题m[i,j]，其对应的s[i,j]用于记录该矩阵链最后一次乘法发生的位置。
（）
√37.分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。
因此，分治法的计算效率通常可以用递归方程来进行分析。
（）
×38.如果两个序列的最后一个字符相同，则其最长公共子序列必以那个相同的字符结尾。
√39.反复应用分治手段,不能使子问题与原问题类型一致而其规模却不断缩小。
（）
√40.分治法在每一层递归上有三个步骤：
分解、解决、合并。
（）
√41.递归是从函数本身出发来达到边界条件。
（）
√42.递归的长处是能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。
（）
√43.数据之间的关系（即数据结构）按递归定义，如树的遍历，图的搜索等，这类问题适用递归算法。
（）
√44.贪心算法和动态规划算法都要求问题具有最优子结构性质。
（）
√45.备忘录方法可以看作是动态规划算法的变形。
（）
√46.适宜于用贪心策略来解的问题都有两个特点:
贪心选择性质和最优子结构。
（）
√47.Huffmann编码树一定是满树。
（）
√48.归并排序算法是渐进最优算法。
（）
√49.动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。
（）
√50.数量级反映了算法时间复杂度的最本质的特征。
（）
×51.对于0-1背包问题的解向量X，Xi=1表明选择物品1..i。
（）
×52.Ford-Fulkerson算法规定了增广路径的搜索算法。
（）
√53.f（n）=6×2n+n2，f（n）的渐进性态f（n）=O（2n）。
（）
√54.如果顶点的总数为n，则Prim算法总共要选择n-1条边来构成生成树。
（）
√55.二分搜索法的二分查找只适用于顺序存储结构。
（）
×56.不同的矩阵链加括号形式会导致矩阵链相乘的不同结果。
（）
√57.算法分析的目的是分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法。
（）
√58.算法的渐进时间复杂性是指当问题的规模n趋向无穷大时，影响算法效率的重要因素是T（n）的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T（n）的数量级（阶）评价算法。
时间复杂度T（n）的数量级（阶）称为渐进时间复杂性。
（）
√59.快速排序是一个递归的算法。
（）
√60.通常用T（n）来表示某一算法的“时间复杂性”，当输入量n逐渐增大时，
时间复杂性的极限称为算法的“渐近时间复杂性”。
（）
三、填空题（本大题共0分，共40小题，每小题0分）
1.______算法是这样一种算法，它期望通过所做的局部最优选择产生出一个全局最优解。
1.参考答案：
贪心
2.0-1背包问题中，对于物品能否装入背包，我们只考虑其重量和价值，而不考虑其____。
2.参考答案：
形状和体积
3.算法的实现工具是______。
3.参考答案：
程序语言
4.由分治法产生的子问题往往是原问题的______，这就为使用递归技术提供了方便。
4.参考答案：
较小模式
5.动态规划算法的两个基本要素是______和______。
5.参考答案：
最优子结构性质重叠子问题性质
6.归并排序算法是用______策略实现对n个元素进行排序的算法。
6.参考答案：
分治
7.矩阵连乘问题的算法可由_______实现。
7.参考答案：
动态规划
8.在JAVA语言中，执行特定认为的任务的函数或过程统称为______。
8.参考答案：
方法
9.快速排序算法是基于______的一种排序算法。
9.参考答案：
分治法
10.T为时间复杂性，对于给定的算法A，设使用A的次数为E且每执行一次算法的时间为t,因此T=______。
10.参考答案：
tE
11.有如下递归过程：
voidreverse（intn）{printf（“%d”,n%10）;
if（n/10!
=0）reverse（n/10）;}调用语句reverse（582）的结果是______。
11.参考答案：
285
12.贪心算法通过___________达成全局最优。
12.参考答案：
局部最优
13.递归按其调用方式分：
___________。
13.参考答案：
直接递归间接递归
14.贪心法和动态规划设计方法都利用了______性质。
14.参考答案：
最优子结构
15.最优子结构性质的含义是_____。
15.参考答案：
问题的最优解包含其子问题的最优解
16.对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成。
该解空间包含对变量的所有0-1赋值。
当n=3时，其解空间是：
______。
16.参考答案：
｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0）（1，1．1）｝
17.最优二叉搜索树是指___________为最小的二叉搜索树。
17.参考答案：
搜索代价的数学期望
18.贪心算法与动态规划算法的主要区别是______。
18.参考答案：
贪心选择性质
19.数据之间的相互关系，即数据的组织形式称为______。
19.参考答案：
数据结构
20.算法中最基本的数据类型有______、______、______、______。
20.参考答案：
布尔值数据、字符数据、整数和实数等
21.S（n）=O（f（n）），其中n为___________，S（n）表示空间复杂度。
21.参考答案：
问题的规模
22.直接或间接地调用自身的算法称为______算法。
22.参考答案：
递归
23.动态规划法求解多阶段决策问题，用—个表来记录______。
23.参考答案：
所有已解决的子问题的答案
24.找零钱问题中，我们应用的贪心规则是____________。
24.参考答案：
总是找不超过当前剩余应找钱数的最大面值硬币
25.一个30行20列的矩阵可与一个_________行75列的矩阵相乘。
25.参考答案：
20
26.在n加倍的情况下，一个O（n2）的算法计算时间增长______倍。
26.参考答案：
4
27.用函数自身给出定义的函数称为______。
27.参考答案：
递归函数
28.算法的______指的是组成算法的每条指令是清晰的，无歧义的。
28.参考答案：
确定性
29.由分治法产生的子问题往往是原问题的较小模式，这就为使用______技术提供了方便。
29.参考答案：
递归
30.快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________
30.参考答案：
O（log（n）），O（n）
31.二叉搜索树中，搜索一个节点所需的比较次数=该节点在树中的深度+___________。
31.参考答案：
1
32.一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为_____。
32.参考答案：
O（n）
33.O记号在算法复杂性的表示法中表示______。
33.参考答案：
渐进确界或紧致界
34.按照渐近阶比较大小1000nlog（n）______0.1n2?
34.参考答案：
<
35.从分治法的一般设计模式可以看出，用它设计出的程序一般是一个______过程。
35.参考答案：
递归
36.伪代码是一种______________语言。
36.参考答案：
算法描述
37.对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成。
该解空间包含对变量的所有0-1赋值。
当n=2时，其解空间是：
______。
37.参考答案：
｛（0，0），（0，1），（1，0），（1，1）｝
38.如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用______法较好。
38.参考答案：
动态规划
39.Huffmann算法是一种______。
39.参考答案：
贪心算法
40.在二叉树的第i层上至多有______个结点。
40.参考答案：
2i
四、简答题（本大题共0分，共20小题，每小题0分）
1.描述0-1背包问题。
1.参考答案：
已知一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
2.请简单描述一下插入排序算法思想。
2.参考答案：
输入一个元素，检查数组列表中的每个元素，将其插入到一个已经排好序的数列中的适当位置，使数列依然有序，当最后一个元素放入合适位置时，该数组排序完毕。
3.给定硬币面值分别为1,5,10,25,100,设计一个方法，使得可以用最少数量的硬币来兑换钱34。
3.参考答案：
因为贪心算法对于硬币组合{1,5,10,25,100}是可以得到最优解的所以使用贪心算法，先找最大值，可以得到{25,5,1,1,1,1}最优解决方案.
4.设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。
（1）i=1;j=0;
while（i<=n）
{
if（i>j）j++;
elsei++;
}
（2）x=n;y=0
while（x>=（y+1）*（y+1））y++;
（3）x=91;y=100;
while（y>0）
if（x>100）
{x=x-10;y--;}
elsex++;
4.参考答案：
（1）T（n）=O（n）
（2）T（n）=O（n0.5）（3）T（n）=O
（1）
5.三数取中选择中心点所划分成的两子数组其长度比例不低于1:
7的概率超过90%。
在绝大多数情况下，快速排序的时间不会超过多少？
5.参考答案：
6.算法的正确性是指什么？
6.参考答案：
在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。
7.分治法的基本思想?
7.参考答案：
分治法的基本思想时将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
8.程序的空间复杂度是指什么？
8.参考答案：
一个程序的空间复杂度是指运行完一个程序所需内存的大小。
9.按照时间复杂度从低到高排列：
O（4n）、O（log（n））、O（3）、O（20n）、O
（2）、O（n）、O（n!
）?
9.参考答案：
0
（2）、0（3）、0（log（n）
升级会员 