《算法分析与设计》期末考试复习题纲(完整版)Word文件下载.doc
《《算法分析与设计》期末考试复习题纲(完整版)Word文件下载.doc》由会员分享，可在线阅读，更多相关《《算法分析与设计》期末考试复习题纲(完整版)Word文件下载.doc（18页珍藏版）》请在冰点文库上搜索。
B．2m+1
C．2m+1-1 D．2m
14.二分搜索算法是利用（
A
）实现的算法。
A．分治策略
B．动态规划法
C．贪心法
D．回溯法
15.下列不是动态规划算法基本步骤的是（
B
）。
P44
A．找出最优解的性质
B．构造最优解
C．算出最优解（应该是最优值）
D．定义最优解
16.下面问题（B）不能使用贪心法解决。
A．单源最短路径问题 B．N皇后问题
C．最小花费生成树问题 D．背包问题
17.使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最好情况和最坏情况下搜索的时间复杂性分别为（A）。
P17
A．O
（1），O（logn）B．O（n），O（logn）
C．O
（1），O（nlogn）D．O（n），O（nlogn）
18.优先队列式分支限界法选取扩展结点的原则是（
C
P162
A．先进先出 B．后进先出
C．结点的优先级 D．随机
19.下面不是分支界限法搜索方式的是（D）。
P161
A．广度优先 B．最小耗费优先
C．最大效益优先 D．深度优先
20.分支限界法解最大团问题时，活结点表的组织形式是（B）。
A．最小堆 B．最大堆
C．栈 D．数组
21.下列关于计算机算法的描述不正确的是（C）。
P1
A．算法是指解决问题的一种方法或一个过程
B．算法是若干指令的有穷序列
C.算法必须要有输入和输出
D．算法是编程的思想
22.下列关于凸多边形最优三角剖分问题描述不正确的是（A）。
A．n+1个矩阵连乘的完全加括号和n个点的凸多边形的三角剖分对应
B．在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦
C．该问题可以用动态规划法来求解
D．在有n个顶点的凸多边形的三角剖分中，恰有n-2个三角形
23.动态规划法求解问题的基本步骤不包括（C）。
A．递归地定义最优值
B．分析最优解的性质，并刻画其结构特征
C．根据计算最优值时得到的信息，构造最优解（可以省去的）
D．以自底向上的方式计算出最优值
24.分治法所能解决的问题应具有的关键特征是（C）。
P16
A．该问题的规模缩小到一定的程度就可以容易地解决
B．该问题可以分解为若干个规模较小的相同问题
C．利用该问题分解出的子问题的解可以合并为该问题的解
D．该问题所分解出的各个子问题是相互独立的
25.下列关于回溯法的描述不正确的是（D）。
P114
A．回溯法也称为试探法
B．回溯法有“通用解题法”之称
C．回溯法是一种能避免不必要搜索的穷举式搜索法
D．用回溯法对解空间作深度优先搜索时只能用递归方法实现
26.常见的两种分支限界法为（D）。
A.广度优先分支限界法与深度优先分支限界法；
B.队列式（FIFO）分支限界法与堆栈式分支限界法；
C.排列树法与子集树法；
D.队列式（FIFO）分支限界法与优先队列式分支限界法；
二、填空题
1.f（n）=3n2+10的渐近性态f（n）=O（
n2），
g（n）=10log3n的渐近性态g（n）=O（
n
2.一个“好”的算法应具有正确性、可读性、健壮性和高效率和低存储量需求等特性。
3.算法的时间复杂性函数表示为C=F（N,I,A），分析算法复杂性的目的在于比较求解同意问题的两个不同算法的效率的效率。
4.构成递归式的两个基本要素是递归的边界条件和递归的定义。
5.单源最短路径问题可用分支限界法和贪心算法求解。
6.用分治法实现快速排序算法时，最好情况下的时间复杂性为O（nlogn），最坏情况下的时间复杂性为O（n^2），该算法所需的时间与运行时间和划分两方面因素有关。
P26
7.0-1背包问题的解空间树为完全二叉树；
n后问题的解空间树为排列树；
8.常见的分支限界法有队列式（FIFO）分支限界法和优先队列式分支限界法。
9.回溯法搜索解空间树时常用的两种剪枝函数为约束函数和剪枝函数。
10.分支限界法解最大团问题时，活结点表的组织形式是最大堆；
分支限界法解单源最短路径问题时，活结点表的组织形式是最小堆。
三、算法填空题
1.递归求解Hanoi塔问题/阶乘问题。
例1:
阶乘函数n!
P12
阶乘的非递归方式定义：
试写出阶乖的递归式及算法。
递归式为：
边界条件
递归方程
递归算法：
intfactorial（intn）
{if（n==0）return1;
递归出口
returnn*factorial（n-1）;
递归调用
}
例2:
用递归技术求解Hanoi塔问题,Hanoi塔的递归算法。
P15
其中Hanoi（intn,inta,intc,intb）表示将塔座A上的n个盘子移至塔座C，以塔座B为辅助。
Move（a,c）表示将塔座a上编号为n的圆盘移至塔座c上。
voidhanoi（intn,inta,intc,intb）
{
if（n>
0）
{
hanoi（n-1,a,b,c）;
move（a,c）;
hanoi（n-1,b,c,a）;
}
}
2.用分治法求解快速排序问题。
快速排序算法P25、作业、课件第2章
（2）42页-50页
template<
classType>
voidQuickSort（Typea[],intp,intr）
{
if（p<
r）{
intq=Partition（a,p,r）;
QuickSort（a,p,q-1）;
QuickSort（a,q+1,r）；
}
}
Partition函数的具体实现
intPartition（Typea[],intp,intr）
inti=p,j=r+1;
Typex=a[p];
//将<
x的元素交换到左边区域
//将>
x的元素交换到右边区域
while（true）{
while（a[++i]<
x&
&
i<
r）;
while（a[--j]>
x）;
if（i>
=j）break;
Swap（a[i],a[j]）;
}
a[p]=a[j];
a[j]=x;
returnj;
3.用贪心算法求解最优装载问题。
最优装载问题P95课件第4章
（2）第3-8页
voidLoading（intx[],Typew[],Typec,intn）
int*t=newint[n+1];
Sort（w,t,n）;
for（inti=1;
i<
=n;
i++）x[i]=0;
for（intj=1;
j<
=n&
w[t[j]]<
=c;
j++）
{x[t[i]]=1;
c-=w[t[j]];
4.用回溯法求解0-1背包/批处理作业调度/最大团问题，要会画解空间树。
例1：
用回溯法求解0-1背包P133课件第5章
（2）第24-38页
typenameTypew,typenameTypep>
classKnap
{
private:
TypepBound（inti）;
//计算上界
voidBacktrack（inti）;
Typewc;
//背包容量
intn;
//物品数
Typew*w;
//物品重量数组
Typep*p;
//物品价值数组
Typewcw;
//当前重量
Typepcp;
//当前价值
Typepbestp;
//当前最优价值
};
voidKnap<
Typew,Typep>
:
Backtrack（inti）
{if（i>
n）{bestp=cp;
return;
}
if（cw+w[i]<
=c）//进入左子树
{cw+=w[i];
cp+=p[i];
Backtrack（i+1）;
cw-=w[i];
cp-=p[i];
if（Bound（i+1）>
bestp）//进入右子树
TypepKnap<
Bound（inti）
Typewcleft=c-cw;
//剩余的背包容量
Typepb=cp;
//b为当前价值
//依次装入单位重量价值高的整个物品
while（i<
=n&
w[i]<
=cleft）
{cleft-=w[i];
b+=p[i];
i++;
if（i<
=n）//装入物品的一部分
b+=p[i]*cleft/w[i];
returnb;
//返回上界
classObject//物品类
friendintKnapsack（int*,int*,int,int）;
public:
intoperator<
（Objecta）const
return（d>
=a.d）;
intID;
//物品编号
floatd;
//单位重量价值
TypepKnapsack（Typepp[],Typeww[],Typewc,intn）
{//为TypepKnapsack初始化
TypewW=0;
//总重量
TypepP=0;
//总价值
Object*Q=newObject[n];
//创建物品数组，下标从0开始
for（inti=1;
i<
=n;
i++）//初始物品数组数据
{Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
if（W<
=c）//能装入所有物品
returnP;
returnP;
QuickSort（Q,0,n-1）;
//依物品单位重量价值非增排序
Knap<
K;
K.p=newTypep[n+1];
K.w=newTypew[n+1];
i++）
{K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
K.Backtrack
（1）;
delete[]Q;
delete[]K.w;
delete[]K.p;
returnK.bestp;
例2：
批处理作业调度课件第5章
（2）P2-5问题描述,课本P125-127
解空间：
排列树
算法描述：
classFlowshop
staticint[][]m,//各作业所需的处理时间
[]x,//当前作业调度
[]bestx,//当前最优作业调度
[]f2,//机器2完成处理时间
f1,//机器1完成处理时间
f,//完成时间和
bestf,//当前最优的完成时间和
n;
//作业数
staticvoidBacktrack（inti）
if（i>
n）
{for（intj=1;
j++）bestx[j]=x[j];
bestf=f;
else
for（intj=i;
j++）{
f1+=m[x[j]][1];
//第j个作业在第一台机器上所需时间
f2[i]=（（f2[i-1]>
f1）?
f2[i-1]:
f1）+m[x[j]][2];
f+=f2[i];
if（f<
bestf）//约束函数
{Swap（x[i],x[j]）;
Backtrack（i+1）;
Swap（x[i],x[j]）;
f1-=m[x[j]][1];
f-=f2[i];
}
例3：
最大团问题，要会画解空间树。
classClique
friendintMaxClique（int**,int[],int）;
voidPrint（）;
//输出最优解
private:
int**a;
//图G的邻接矩阵，下标从1开始
//图G的顶点数
int*x;
//当前解
int*bestx;
//当前最优解
intcn;
//当前团的顶点数
intbestn;
//当前最大团的顶点数
voidClique:
n）
{for（intj=1;
j<
j++）bestx[j]=x[j];
bestn=cn;
return;
//判断第i个顶点是否与已选顶点都有边相连
intOK=1;
for（intj=1;
i;
j++）//x[1:
i-1]，已入选的顶点集
if（x[j]&
a[i][j]==0）//i与当前团中的顶点无边相连
{OK=0;
break;
}//只要与当前团中一个顶点无边相连，则中止
if（OK）//进入左子树
{x[i]=1;
cn++;
Backtrack（i+1）;
x[i]=0;
cn--;
if（cn+n-i>
bestn）//如有可能在右子树中找到更大的团，则进入右子树
{x[i]=0;
Backtrack（i+1）;
}
计算时间：
O（n2n）
四、简答题
1.请简述使用动态规划算法解题的基本步骤。
动态规划的设计分为以下4个步骤：
（1）找出最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
2.简述动态规划方法与分治法的异同。
相同点：
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。
不同点：
分治法的子问题互相独立且与原问题相同。
与分治法不同的是，适合于动态规划求解的问题，经分解得到的子问题往往不是互相独立的。
也就是各个子问题包含公共的子子问题。
3.试比较Prim算法与Kruskal算法的异同。
105-P107
Prim（普里姆）算法和Kruskal（克鲁斯卡尔）算法都可以看作是应用贪心算法构造最小生成树的例子。
利用了最小生成树性质。
Prim（普里姆）算法：
在这个过程中选取到的所有边恰好构成G的一棵最小生成树T，T中包含G的n-1条边，且不形成回路。
Kruskal（克鲁斯卡尔）算法：
是构造最小生成树的另一个常用算法。
该算法不是通过扩充连通子集来进行贪心选择。
而是通过选择具有最小权的边的集合来进行贪心选择。
在选择的同时可以进行连通操作以便形成生成树。
4.请简述分支限界法的搜索策略。
P161课件第6章
（1）第6页
（1）分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
（2）每一个活结点只有一次机会成为扩展结点。
（3）活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
（4）儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
（5）从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
5.试比较分支限界法与回溯法的异同。
P161课件第6章
（1）第5页
（1）求解目标：
回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式：
回
升级会员 