期末考试模拟题及参考答案.docx

期末考试模拟题A答案及评分标准

一.简答题（共60分，每题15分）

1.简述算法在最坏情况下的时间复杂度和平均时间复杂度的含义；这两种评估算法复杂性的方法各自有什么实际意义？（15分）

答：

算法在最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

平均时间复杂度考虑了所有可能的输入及其出现的概率，因此它更能反映算法在实际应用中的平均性能。

2.简述动态规划与分治法的共同点、各自的实现方法和主要区别。（15分）

答：

一、分治法与动态规划主要共同点：

二者都是将原问题分而治之，分解成若干个规模较小(小到很容易解决的程序)的子问题，然后将子问题的解合并,形成原问题的解。

二、分治法与动态规划实现方法：

①分治法通常利用递归求解

②动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解

三、分治法与动态规划主要区别：

①分治法将分解后的子问题看成相互独立的

②动态规划将分解后的子问题理解为相互间有联系,有重叠部分

3.采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程，请写出这一过程的伪代码。（15分）

答：

voiditerativeBacktrack()

{

intt=1;

while(t0){

if(f(n,t)=g(n,t))

for(inti=f(n,t);i=g(n,t);i++){

x[t]=h(i);

if(constraint(t)bound(t)){

if(solution(t))output(x);

elset++;}

}

elset--;

}

}

4.简述回溯算法与分枝限界算法的共同点和不同点。（15分）

答：

相同点：

(1)都是在问题的解空间树上有哪些信誉好的足球投注网站问题解的算法；

(2)都是一种既带有系统性又带有跳跃性的有哪些信誉好的足球投注网站算法；

(3)都是基于穷举有哪些信誉好的足球投注网站的算法，都需要设定一个初始解，然后通过不断地枚举有哪些信誉好的足球投注网站来逐步接近最优解；

(4)都可以应用于非线性规划问题的求解。

不同点：

(1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解;

(2)有哪些信誉好的足球投注网站方式的不同：回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树,而分支限界法则以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树；

(3)对节点存储的要求不同：分支限界法通常需要存储一些额外的信息以利于进一步地展开有哪些信誉好的足球投注网站，而回溯法则不需要；

(4)存储空间的要求不同：分支限界法的算法框架中，每一个活结点只有一次机会成为扩展结点，而回溯法则没有这样的限制。

二.算法设计题（40分，每题20分）

1.半数集问题（20分）

问题描述：

给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。

(1)n∈set(n)；

(2)在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；

(3)按此规则进行处理，直到不能再添加自然数为止。

例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。

注意半数集是多重集。

编程任务：

对于给定的自然数n，编程计算半数集set(n)中的元素个数。

数据输入：

每个输入包含若干行，每行给出一个整数n。(0n1000)

直到0结束输入。

结果输出:

输出中每行输出半数集set(n)中的元素个数。

样例输入：

1

2

6

0

样例输出：

1

2

6

参考答案：

#includebits/stdc++.h

usingnamespacestd;

typedeflonglongll;

inta[1007];

intf(intn)

{

if(n==1)return1;

intsum=1,i;

if(a[n]0)returna[n];

for(i=1;i=n/2;i++)

sum+=f(i);

a[n]=sum;

returna[n];

}

intmain()

{

intn;

cinn;

while(n)

{

coutf(n)endl;

cinn;

}

}

2.最小m段和问题（20分）

问题描述：

给定