算法设计技巧与分析习题答案

【篇一：算法设计与分析考试题及答案】

一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 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所需的时间分别为ai和bi，且(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），并画出其解空间树，计算其最优值及最优解。

6.描述0-1背包问题。 三、简答题（30分）

1.流水作业调度中，已知有n个作业，机器m1和m2上加工作业i所需的时间分别为ai和bi，请写出流水作业调度问题的johnson法则中对ai和bi的排序算法。（函数名可写为sort(s,n)）

2.最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree)） 答案： 一、填空

1．确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.时间复杂性 空间复杂性 时间复杂度高低3. 该问题具有最优子结构性质4.{babcd}或{cabcd}或{cadcd｝5.一个（最优）解 6.子问题子问题子问题 7.回溯法

8. o(n*2n) o(min{nc,2n}) 9.最优子结构 重叠子问题 10.动态规划法 二、综合题

1.①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解；

2. ①令n1={i|aibi}，n2={i|ai=bi}；②将n1中作业按ai的非减序排序得到n1’，将n2中作业按bi的非增序排序得到n2’；③n1’中作业接n2’中作业就构成了满足johnson法则的最优调度。 3.步骤为：n1={1，3}，n2={2，4}；

n1’={1，3}， n2’={4，2}； 最优值为：38

4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为：

该问题的最优值为：16 最优解为：（1，1，0） 5.二叉树t的平均路长p=?bi*(1?ci)+?aj*dj i?1n n j?0 ? 1.

m[i][j]=w[i][j]+min{m[i][k]+m[k+1][j]} (1=i=j=n,m[i][i-1]=0) m[i][j]=0(ij)

6.已知一个背包的容量为c，有n件物品，物品i的重量为wi，价值为vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 三、简答题

void sort(flowjope s[],int n) { int i,k,j,l; for(i=1;i=n-1;i++)//-----选择排序 {k=i;

while(k=ns[k].tag!=0) k++;if(kn) break;//-----没有ai，跳出else{ for(j=k+1;j=n;j++)if(s[j].tag==0)

if(s[k].as[j].a)k=j; swap(s[i].index,s[k].index); swap(s[i].tag,s[k].tag); } }

l=i;//-----记下当前第一个bi的下标 for(i=l;i=n-1;i++) {k=i;

for(j=k+1;j=n;j++) if(s[k].bs[j].b) k=j;

swap(s[i].index,s[k].index); //-----只移动index和tag swap(s[i].tag,s[k].tag);} }

【篇二：计算方法的课后答案】

>第一章 数值计算中的误差

1．什么是计算方法？（狭义解释）

答：计算方法就是将所求的的数学问题简化为一系列的算术运算和逻辑运算，以便在计算机上编程上机，求出问题的数值解，并对算法的收敛性、稳定性和误差进行分析、计算。

2．一个实际问题利用计算机解决所采取的五个步骤是什么？

答：一个实际问题当利用计算机来解决时，应采取以下五个步骤： 实际问题→建立数学模型→构造数值算法→编程上机→获得近似结果 4．利用秦九韶算法计算多项式p(x)?x?x3?x5?4在x??3处的值，并编程获得解。 解：p(x)?x5?0?x4?x3?0?x2?x?4，从而 所以，多项式p(x)?x?x3?x5?4在x??3处的值p(?3)??223。 5．叙述误差的种类及来源。

答：误差的种类及来源有如下四个方面：

（1）模型误差：数学模型是对实际问题进行抽象，忽略一些次要因素简化得到的，它是原始问题的近似，即使数学模型能求出准确解，也与实际问题的真解不同，我们把数学模型与实际问题之间存在的误差称为模型误差。

（2）观测误差：在建模和具体运算过程中所用的一些原始数据往往都是通过观测、实验得来的，由于仪器的精密性，实验手段的局限性，周围环境的变化以及人们的工作态度和能力等因素，而使数据必然带有误差，这种误差称为观测误差。

（3）截断误差：理论上的精确值往往要求用无限次的运算才能得到，而实际运算时只能用有限次运算的结果来近似，这样引起的误差称为截断误差（或方法误差）。

（4）舍入误差：在数值计算过程中还会用到一些无穷小数，而计算机受机器字长的限制，它所能表示的数据只能是一定的有限数位，需要把数据按四舍五入成一定位数的近似的有理数来代替。这样引起的误差称为舍入误差。

6．掌握绝对误差（限）和相对误差（限）的定义公式。

答：设x是某个量的精确值，x是其近似值，则称差e?x?x为近似值x的绝对误差（简称误差）。若存在一个正数?使e?x?x??，称这个数?为近似值x的绝对误差限（简称误差限或精度）。 * * *

ex*?x把绝对误差e与精确值x之比er?*?称为近似值x的相对误差，称 xx* * ?? ? x*

为近似值x的相对误差限er??，由于真值x是未知的，所以常常用 *

x*?xeer??来表示相对误差，于是相对误差可以从绝对误差求出。 xx

7．近似值的规格化表示形式如何？

答：一般地，对于一个精确值x，其近似值x的规格化形式为x??0.x1x2?xp?10m， *

其中x1?0,xi??0,1,2,?9?(i?1,2,?p)，p为正整数，m为整数。 8．有效数字的概念是什么？掌握有效数字与误差的关系。

答：若近似值x的（绝对）误差限是它的某一位的半个单位，也就是说该近似值准确到这一位，且从该位起直到前面第一个非零数字为止的所有数字都称为有效数字。 若近似值x的（绝对）误差限为e?x?x?数字的有效数，或称它精确到10 * * 1

?10m?n，则称x为具有n位有效2 m?n

位，其中的每一位数字x1,x2,?xn都是x的有效数字。 m

设精确值x的近似值x的规格化形式为x??0.x1x2?xp?10，若x具有n位有效数字，则其相对误差限为er? 1