重庆大学网络教育

算法设计分析参考资料

一、单项选择题（本大题共0分，共60小题，每小题0分）

C1.算法的时间复杂度是指（）

C.算法执行过程中所需要的基本运算次数

C2.衡量一个算法好坏的标准是（）。

C.时间复杂度低

D3.在最长公共子序列问题中，如果定义c[i,j]为X1..Xi和Y1..Yj的最长公共子序列的长

度，则长度为m的X序列与长度为n的Y序列的最长公共子序列的长度为（）。

D.c[m,n]

D4.以下关于贪心算法，不正确的说法是（）。

D.所需求解的问题可以不满足最优子结构性质

C5.合并排序法的基本思想是：将待排序元素分成大小大致相同的（）个子集合，分别对

每个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

C.2

C6.对于n个元素的排序问题，n＝2时,只要作（）次比较即可排好序。

C.1

A7.二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进

行比较：如果（），则只要在数组a的左半部继续搜索x。

A.x＜a[n/2]

A8.备忘录方法的递归方式是（）

A.自顶向下

C9.算法指的是（）。

C.解决问题的方法和过程

D10.应用Johnson法则的流水作业调度采用的算法是（）

D.动态规划算法

A11.算法分析中，记号O表示（）

A.渐进上界

B12.在找零钱问题中，收银员算法中所应用的贪心规则的最恰当描述是（）。

B.总是选择不超过剩余应找钱数的最大面值的硬币

B13.由边界条件出发,通过递推式求f(n)的值,从边界到求解的全过程十分清楚的是（）

B.递推

D14.考虑最长公共子序列问题的下述递归表达式，如果全部子问题组织在一个c[i,j]的二维

表格中，则c[i,j]不依赖于下述哪个子问题：（）。

D.同一行的下一列

A15.活动选择问题就是在所给的活动集合中，选出（）的相容活动子集。

A.当前可选活动中结束时间最早的活动

A16.一个长度为n英寸的钢管的最优切割问题，总共有()个不同的子问题。

A.n+1

D17.算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是

D.f(n)=f(n-1)+2,f(1)=10,n为自然数

A18.实现快速排序算法如下：QuickSort(A,p,r)

IFp

ort(A,q-1,r)

A19.找零钱问题中，定义C[j]为兑换j所需要的硬币的最少数量，如果找出的第一个硬币

为5分，则下述公式哪个是对的（）。

A.C[j]=1+C[j-5]

B20.最长公共子序列算法利用的算法是（）。

B.动态规划法

n编码的贪心算法所需的计算时间为（）。

B.O（nlogn）

A22.使用分治法求解不需要满足的条件是（）。

A.子问题必须是一样的

D23.下列关于算法速度的描述，正确的是（）

D.对于问题规模比较大的时候，对数时间算法比指数时间算法快非常多

C24.在使用伪代码进行算法描述时，不可以实现循环的是（）。

B25.大型程序设计一般用（）数据类型来描述算法。

B.抽象

A26.与分治法不同的是，适合于用动态规划求解的问题（）。

A.经分解得到子问题往往不是互相独立的

D27.快速排序法的基本思想是对输入的数组按以下三个步骤进行排序（）。

D.分解，递归求解,合并

D28.在最优二叉搜索树问题中，我们的优化目标是（）。

D.元素搜索代价的数学期望为最小

C29.T(n)=2n3+10n2log(n)+30n的渐近时间复杂度为（）。

C.O(n3)

s-Karp算法中寻找增广路径的方法是（）。

B.广度优先算法

B31.在矩阵连乘问题的动态规划解决方案里，我们的所做的顶层决策是（）。

B.最后一次矩阵乘法发生的位置

A32.关于0-1背包问题的下述形式化公式描述：下述说法不正确的是（）。

A航天日 .i表示物品的重量

A33.在活动安排问题中，如果把全部活动按照结束时间递增序排序后，按贪心算法，我们

总是安排（）。

A.当前可选活动中结束时间最早的活动

A34.找零钱问题中，定义C[j]为兑换j所需要的硬币的最少数量，考虑下述递归表达式，

下列关于对i的寻优的最恰当描述是（）。

A.考虑找出的第一个硬币面值的各种可能性

n编码问题中，我们的优化目标是（）。

A.所有字符编码长度的数学期望为最小

B36.一个有n个结点的带权无向图，其生成树应有（）条边。

B.n-1

B37.算法必须具备输入、输出和（）等5个特性。

B.可行性、确定性和有穷性

A38.当问题的规模n趋向无穷大时，（）的数量级(阶)称为算法的渐进时间复杂度。

A.时间复杂度

B39.下列算法中通常以自底向上的方式求解最优解的是（）。

B.动态规划法

B40.贪心算法与动态规划算法的主要区别是（）。

B.贪心选择性质

D41.最优二叉搜索树的时间复杂度为（）。

D.O(nlogn)

D42.对于三个物体的背包问题，问题相关的数据为n=3,M=20,P=(25,24,15),W(18,15,10)。

下面给出的四个可行解中，最好的是（）

D.(0，1，1/2)

B43.递归函数f(n)=f(n-1)+n(n>1)的递归出口是()。

B.f(1)=1

B44.下面关于快速排序的说法，正确的是（）

B.快速排序的速度在分解的均匀的时候效果最好，速度最快

D45.下面关于货郎担问题的描述，正确的是（）

D.货郎担问题可以通过动态规划算法实现

B46.在最优二叉搜索树问题中，定义e[i,j]为ki,...,kj的最优二叉查找

树的期望搜索成本，而我们确定根结点下标为r,则其左子树的下标范围是（）。

-1

C47.贪心算法与动态规划类似，用于解决最优化问题，下面关于它们的叙述正确的是（）

C.贪心算法是期望通过所做的局部最优选择来产生全局最优解决方案

D48.关于几种排序算法的速度描述，正确的是()

D.快速排序速度快，适合大规模数据

B49.下面关于网络流的属性的描述，激励学习的名言 正确的是（）

B.对于所有；

B50.算法simpleMaxMin(])如下，

Max=Min=A[l];

fori=l+1tordo

ifA[i]>MaxMax←A[i];

elifA[i]

returnMax,Min

其时间复杂度是（）。

B.2(n-1)

C51.下面是贪心算法的基本要素的是（）。

C.贪心选择性质

C52.分治法所能解决的问题应具有的关键特征是（）。

C.利用该问题分解出的子问题的解可以合并为该问题的解

A53.在钢管切割问题里，如果用rn表示长度为n英寸的钢管的最优切割方案所获得的

最大收益，且已知rn所代表的最优解里，第一刀切下了3英寸，则下述公式正确的是（）。

=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.当一个问题具有最优子结构性质时只能用动态规划方法求解。()

nn编码树所对应的编码并不一定是前缀码。（）

√28.通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理。

29.问题的计算复杂性一般是随着问题规模的增加而减小。()

√30.子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。()

算法是一种动态规划算法。（）

√32.标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用

于理论上的分析。()

√33.问题解法按递归算法实现的问题适用于递归求解。()

√34.一般认为，执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处

理速度的常数。()

√35.如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为

多阶段决策问题。（）

√36.对于矩阵链连乘的子问题m[i,j]，其对应的s[i,j]用于记录该矩阵链最后一次乘法发生

的位置。（）

√37.分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分

治法的计算效率通常可以用递归方程来进行分析。()

38.如果两个序列的最后一个字符相同，则其最长公共子序列必以那个相同的字符结尾。

√39.反复应用分治手段,不能使子问题与原问题类型一致而其规模却不断缩小。()

√40.分治法在每一层递归上有三个步骤：分解、解决、合并。()

√41.递归是从函数本身出发来达到边界条件。()

√42.递归的长处是能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。()

√43.数据之间的关系(即数据结构)按递归定义，如树的遍历，图的搜索等，这类问题适用

递归算法。()

√44.贪心算法和动态规划算法都要求问题具有最优子结构性质。()

√45.备忘录方法可以看作是动态规划算法的变形。（）

√46.适宜于用贪心策略来解的问题都有两个特点:贪心选择性质和最优子结构。()

√nn编码树一定是满树。（）

√48.归并排序算法是渐进最优算法。()

√49.动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。()

√50.数量级反映了算法时间复杂度的最本质的特征。()

51.对于0-1背包问题的解向量X，Xi=1表明选择物品1..i。（）

-Fulkerson算法规定了增广路径的搜索算法。()

√53.f(n)=62n+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.有如下递归过程：voidrever(intn){printf(“%d”,n%10);

if(n/10!=0)rever(n/10);}调用语句rever(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.参考答案：动态规划

nn算法是一种______。

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++;

eli++;

}

(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--;}

elx++;

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)）、0（n）、0（4^n）、0（20^n）、0（n！）

10.b），写出求它们的最大公约数的算法或程序。

10.参考答案：算法如下：输入a，b（a>b）；②求a/b的余数r；③如果r≠0，则

将b→a，r→b，再次求a/b的余数r，转至③；④输出最大公约数b。

intgcd(inta,intb)

{

inttmp;

if(a

{

tmp=a;a=b;b=tmp;

}

while(b>1)

{

tmp=a%b;

if(tmp==0)break;

a=b;b=tmp;

}

returnb;}

11.对于aeklu五个字符，及其频度数据：=0.32,=0.25,=0.20,=0.18,=0.05。请用Huffmann

算法构造其Huffmann树。

11.参考答案：对于aeklu五个字符，及其频度数据：=0.32,=0.25,=0.20,=0.18,=0.05。请

用Huffmann算法构造其Huffmann树。

由题可知字符a,e,k,l,u五个字符的权值分别为0.32,0.25,0.20,0.18,0.05。

(1)先由两个权值最小的字符作为叶子节点构造二叉树，即l,u。则权值变为

0.32,0.25,0.20,0.23

(2)再选择权值最小的节点构造二叉树，即0.20,0.23则权值变为0.32,0.25，0.43

(3)同理选择0.32和0.25对应的节点作为叶子节点，则权值变为0.57,0.43

(4)只剩下两个则继续构造，权值变为1，构造结束。结构为：

12.有如下四个矩阵：

请计算所需要的总的数乘次数，并说明计算方法。

12.参考答案：

13.有5个关键字，其搜索概率如下:

p1=0.25,p2=0.2,p3=0.05,p4=0.2,p5=0.3.

请计算上述二叉搜索树的搜索代价的数学期望。

13.参考答案：

14.对于钢管切割问题的下述价格表：

请计算r1..r5。

14.参考答案：由算法自底向上版本

BOTTOM-UP-CUT-ROD(p,n)

]beanewarray

2r[0]=0

3forj=1ton

4q=

5fori=1toj

6q=max(q,p[i]+r[j-1])

7r[j]=q

8returnr[n]

有以上算法可以解出r[j]

(1)当j=1时，i=1，则q=max;所以，r[1]=1.

(2)当j=2时，当i=1时，所以，r[2]=5.

同理j=3,4,5时，可计算出r[3]=8;r[4]=10;r[5]=13.

i12345

1481013

-Fulkerson算法的主要问题是什么？

15.参考答案：当最大流值较大时可能发生的情况是每次寻找出来的增广路径，都只能将流

网络的流量增加很小的值，这样的话，会大大增加循坏的次数。尤其是|f*|=2|E|

时，算法的时间复杂度变成流网络规模O(|V|+|E|)的指数函数O(|E|2|E|)。

16.何谓P、NP、NPC问题。

16.参考答案：P问题也就是多项式复杂度的问题；NP问题就是多项式复杂度非确定性问

题；NPC问题是指只有把解域里面所有可能都穷举了之后才能得到答案，这样的问题是NP

里面最难的问题，这类问题就是NPC问题。

17.有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求

解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集

合），得到的最大相容活动子集合为活动____________。

17.参考答案：{1，4，8，11}

18.描述分治法与动态规划法的的异同。

18.参考答案：分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先

求解子问题，然后从这些子问题的解得到原问题的解；两者的不同点是：适合于用动态规划

法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解

得到的子问题往往是互相独立的。

19.设是一个流网络，f为G的流，(S,T)为G的一个割，证明|f|=f(S,T)。

19.参考答案：

|f|=f（s,V）=f（S,V）-f（S-{s},V）=f（S,V）

t⊈S-{s}=f（S,T）+f（S,S）=f（S,T）

20.按增长率由小至大的顺序排列下列各函数：

20.参考答案

五、问答题（本大题共0分，共20小题，每小题0分）

1.什么是最优子结构性质？

五、问答题（0分，共20题，每小题0分）

1.参考答案：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策

所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略

总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

2.什么是算法的数据输入、输出性？

2.参考答案：具有数据输入：一个算法有零个或多个数据输入，它们是在算法开始之前对

算法最初赋予的量，这些输入取自特定的对象集合。

具有数据输出：一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。

3.试给出归并排序的复杂度分析。

3.参考答案：合并两个长度为n/2的子序列的时间复杂度为O(n)。比较两个元素大小的时

间为O(1)，而每次比较都会从其中一个子序列中取出一个元素放到合并空间中，因此比较

的总次数不会超过n次，时间复杂度为O(n)。同时，其中一个子序列中的元素都被取出为

止，合并的过程不会停止，所以时间复杂度满足O(n)。

4.试叙述流网络的基本性质。

4.参考答案：（1)容量限制；(2)流量守恒

5.阐述动态规划算法与分治法不同之处。

5.参考答案：与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题

往往不是互相独立的。

若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指

数时间。

6.已知变量x和y中分别存放了数据，交换其中的数据。请用自然语言描述算法。

6.参考答案：为了交换，需要引进一个中间变量m，其算法如下：①将x中的数据送给

变量m，即x→m；②将y中的数据送给变量x，即y→x；③将m中的数据送给变量y，

即m→y。

7.请概述最小代价生成树的贪心选择性质，并证明。

7.参考答案：贪心选择的性质指的是局部最优选择可以得到全局最优解决方案，在最小代

价生成树中，其表现为每次选择的为当前可选情况下权值最小的边。

证明：（1）一定有一个最优解包含了当前权值最小的边。假设最优解不包含该边，

则将加入其中，会形成一个环，任意去掉环里比权值大的一条边，则形成了一

个更优的解，与假设矛盾。

（2）选择了后，子问题为去掉了关联的点的剩余的点为顶点集，剩余的边为

边集的图的最小代价问题，规模变小，性质不变。通过归纳法，其可以通过贪心性质得到最

优解。

8.描述Ford-Fulkerson算法基本步骤。

8.参考答案：（1）开始的时候，所有的节点u,v∈V间的流值都为0，即f(u,v)=0。（2）

在每一次迭代中，我们将流网络G的流量进行增加，方法就是在一个关联的“剩余网络”

Gf中寻找一条“增广路径”。一旦知道Gf中的一条增广路径的边，就可以很容易辨别出G

中的对应的边，我们可以对这些边上的车上的lock是什么意思 流值进行修改，从而增加流量（3）重复第2的操作，

直到剩余网络中不再存在增广路径为止。

9.用伪代码或程序语言写出二分搜索的算法，并分析其时间复杂度。

9.参考答案：i容易出汗是什么原因 ntbinary_arch(int*a,intn,intkey){

intmid,front=0,back=n-1;

while(front<=back){

mid=(front+back)/2;

if(a[mid]==key)

returnmid;

if(a[mid]

front=mid+1;

el

back=mid-1;

}

return-1;

}

时间复杂度O(log(n))

10.简述分治法在每一层递归上的三个步骤的具体内容。

10.参考答案：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子

问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：

将各个子问题的解合并为原问题的解。

11.简述快速排序的具体过程。

11.参考答案：通过一趟排序将纪录分割，其中一部分关键字均比另一部分小；然后再分别

对这两部分进行排序；通常选取序列的第一个纪录作为比较的参照（称为支点Pivot），然

后将关键字小的排在其前卷发梳怎么用 ，大的排在其后，并以此时关键字的位置将序列分成两部分，再对

两部分进行快速排序；因此快速排序是一个递归的算法。

12.有面值分别为1、5和11单位的硬币，希望找回总额为15单位的硬币，贪心算法的

思路和最优解分别是什么？

12.参考答案：假设当前的找回总额为a，贪心算法总是在可行的选择中寻找小于等于a的

最大值b，然后改变找回额，即a=a-b，重新上面的过程直到不能继续为止。按贪心算法，

应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。最优的解应

是3个5单位面值的硬币。

13.简述贪心算法的基本思想？

13.参考答案：贪心算法是通过做一系列的选择来给出某一问题的最优解的对算法中的每一

决策点，做一个当时(看起来像是)最佳的选择。这种启发式策略并不是总能产生出最优解，

但正像我们在活动选择问题中看到的那样，它常常能给出最优解。

14.快速排序算法基本思想？

14.参考答案：快速排序算法是基于分治策略的一个算法。其基本思想是，对于输入的子数

组a[p:r],按以下3个步骤进行排序：分解、递归求解、合并。

15.简述程序与算法的异同点。

15.参考答案生活故事 ：程序与算法不同。程序是算法用某种程序设计语言的具体实现。程序可以不

满足算法具有数据输出的性质。一个算法产生一个或多个输出，它们是同输入有某种特定关

系的量)例如操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。然而我们

可把操作系统的各种任务看成是一些单独的问题，每一个问题由操作系统中的一个子程序通

过特定的算法来实现。该子程序得到输出结果后便终止。

16.简单区分语言、算法、程序的不同之处。

16.参考答案：语言：实现的工具；算法：解的描述；程序：算法+数据结构

17.简单阐述动态规划算法的基本思想。

17.参考答案：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个问

题，先求解子问题，然后从这些子问题的解得到原问题的解。

18.分治法基本步骤是什么？

18.参考答案：分治模式在每一层递归上都有三个步骤：

1分解：将原问题分解成一系列子问题；

2解决：递归地解各小问题。若小问题足够小，则直接求解

3合并：将子问题的结果合并成原问题的解。

19.

19.参考答案：

20.简述动态规划法解最优化问题通常的几个步骤。

20.参考答案：动态规划法解最优化问题通常按以下几个步骤进行：（1）找出最优解的性

质，并刻画其结构特征；（2）递规地定义最优值；（3）以自底向下地方式计算出最优值；

（4）根据计算最优值时得到的信息，构造最优解。

三数取中划分的快速排序算法是基于______策略的一个算法。

分治

一个人把一对兔子用围墙围住。如果最初的一对兔子（一雌一雄）是新生的，并且所有的兔

子在出生后的第一个月都不能繁殖，但是在之后的每个月末都能生出一对兔子（一雌一雄），

那么一年后围墙里将会有多少对兔子？

第一个月后：2+2=4第二个月后：(2+2)x2=8第三个月后：(2+2)x2x2=16因此12个月后有兔

子：(2+2)x2^11=4x2^11=8192只兔子也就是4096对兔子。

x(1)=0，当n>1时x(n)=2x(n-1)+1，则x(n)等于（）。

在活动安排问题中，下述哪项描述中的活动A,B是相容的（）？

关于解决最小代价生成树问题的Prim算法的下述说法，不正确的是（）。

以下关于Huffmann树的描述，哪一项是错误的（）。

B、在树的同一层，字符的出现顺序会影响平均编码长度的数学期望

阶乘函数用递归定义Publicstaticintfactorial(intn){if(n==0)return1;return（）;}

A、n*factorial(n-1)

关于二分检索算法的一些描述，正确的是（）。

当问题的最优解包含了其子问题的最优解时，称该问题具有（）。

D、最优子结构性质

考虑关于0-1背包问题的如下递归表达式，如果物品i的重量小于背包的剩余容量，并且我

们选择装入了物品i,则OPT(i，w)的取值为（）。

A、OPT(i-1,w)

Java的类一般有4个部分组成：请选出不属于的一个（）

适用动态规划解决的问题必须满足最优子结构和（）性质。

x(1)=4，当n>1时x(n)=3x(n-1)。则x(n)等于（）。

当n越来越大时，下列函数中，增长速度最快的应该是（）。

二分搜索算法是基于（）设计的算法。

A、分治法