《算法分析与设计》期末考试复*题纲(完整版)要点

发布时间:2021-10-19 16:32:03

《算法分析与设计》期末复*题

一、选择题

1. 算法必须具备输入、输出和( D )等 4 个特性。

A.可行性和安全性

B.确定性和易读性

C.有穷性和安全性

D.有穷性和确定性

2. 算法分析中,记号 O 表示( B ),记号Ω 表示( A )

A.渐进下界

B.渐进上界

C.非紧上界

D.紧渐进界

3. 假设某算法在输入规模为 n 时的计算时间为 T(n)=3*2^n。在某台计算机上实现并

完成概算法的时间为 t 秒。现有另一台计算机,其运行速度为第一台的 64 倍,那

么在这台新机器上用同一算法在 t 秒内能解输入规模为多大的问题?( B )解

题方法:3*2^n*64=3*2^x

A.n+8

B.n+6

C.n+7

D.n+5

4. 设 问 题 规 模 为 N 时 , 某 递 归 算 法 的 时 间 复 杂 度 记 为 T(N) , 已 知 T(1)=1 ,

T(N)=2T(N/2)+N/2,用 O 表示的时间复杂度为( C )。

A.O(logN)

B.O(N)

C.O(NlogN)

D.O(N?logN)

5. 直接或间接调用自身的算法称为( B )。

A.贪心算法

B.递归算法

C.迭代算法

D.回溯法

6. Fibonacci 数列中,第 4 个和第 11 个数分别是( D )。

A.5,89

B.3,89

C.5,144

D.3,144

7. 在有 8 个顶点的凸多边形的三角剖分中,恰有( B )。

A.6 条弦和 7 个三角形

B.5 条弦和 6 个三角形

C.6 条弦和 6 个三角形

D.5 条弦和 5 个三角形

8. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的( B )。

A.重叠子问题

B.最优子结构性质

C.贪心选择性质

D.定义最优解

9. 下列哪个问题不用贪心法求解( C )。

A.哈夫曼编码问题

B.单源最短路径问题

C.最大团问题

D.最小生成树问题

10. 下列算法中通常以自底向上的方式求解最优解的是( B )。

A.备忘录法

B.动态规划法

C.贪心法

D.回溯法

11. 下列算法中不能解决 0/1 背包问题的是( A )。

A.贪心法

B.动态规划

C.回溯法

D.分支限界法

12. 下列哪个问题可以用贪心算法求解( D )。

1

A.LCS 问题

B.批处理作业问题

C.0-1 背包问题

D.哈夫曼编码问题

13. 用回溯法求解最优装载问题时,若待选物品为 m 种,则该问题的解空间树的结点

个数为( )。

A.m!

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 )。P44

A.递归地定义最优值

B.分析最优解的性质,并刻画其结构特征

C.根据计算最优值时得到的信息,构造最优解 (可以省去的)

D.以自底向上的方式计算出最优值

24. 分治法所能解决的问题应具有的关键特征是( C )。P16

2

A.该问题的规模缩小到一定的程度就可以容易地解决 B.该问题可以分解为若干个规模较小的相同问题 C.利用该问题分解出的子问题的解可以合并为该问题的解 D.该问题所分解出的各个子问题是相互独立的 25. 下列关于回溯法的描述不正确的是( D )。P114 A.回溯法也称为试探法 B.回溯法有“通用解题法”之称 C.回溯法是一种能避免不必要搜索的穷举式搜索法 D.用回溯法对解空间作深度优先搜索时只能用递归方法实现 26. 常见的两种分支限界法为( D )。P161 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
阶乘的非递归方式定义: n!? n? (n ?1)? (n ? 2)??? 2?1

试写出阶乖的递归式及算法。

递归式为:

? 1 n?0 n!? ??n(n ?1)! n ? 0

边界条件

3

递归算法:

递归方程

int factorial (int n) { if (n==0) return 1; 递归出口 return n * factorial (n-1); 递归调用

} 例 2:用递归技术求解 Hanoi 塔问题,Hanoi 塔的递归算法。P15 其中 Hanoi (int n, int a, int c, int b)表示将塔座 A 上的 n 个盘子移至塔座 C,以塔座 B 为辅助。 Move(a,c)表示将塔座 a 上编号为 n 的圆盘移至塔座 c 上。

void hanoi (int n, int a, int c, int b) { 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<class Type> void QuickSort (Type a[], int p, int r) {
if (p<r) { int q=Partition(a,p,r); QuickSort (a,p,q-1); QuickSort (a,q+1,r); }
}
4

Partition 函数的具体实现 template<class Type> int Partition (Type a[], int p, int r) {
int i = p, j = r + 1; Type x=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; return j; } 3. 用贪心算法求解最优装载问题。 最优装载问题 P95 课件第 4 章(2)第 3-8 页 template<class Type> void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i <= n; i++) x[i] = 0; for (int j = 1; j <= n && w[t[j]] <= c; j++)
{x[t[i]] = 1; c -= w[t[j]];} }
5

4. 用回溯法求解 0-1 背包/批处理作业调度 /最大团问题,要会画解空间树。 例 1:用回溯法求解 0-1 背包 P133 课件第 5 章(2)第 24-38 页 template<typename Typew,typename Typep> class Knap {
private: Typep Bound(int i); //计算上界 void Backtrack(int i); Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最优价值
};
void Knap<Typew,Typep>::Backtrack(int i) { 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) //进入右子树 Backtrack(i+1); }
Typep Knap<Typew,Typep>::Bound(int i) {
Typew cleft=c-cw; //剩余的背包容量 Typep b=cp; //b 为当前价值 //依次装入单位重量价值高的整个物品
6

while(i<=n&&w[i]<=cleft)

{ cleft-=w[i];

b+=p[i];

if(i<=n) //装入物品的一部分

b+=p[i]*cleft/w[i];

return b; //返回上界

}

i++; }

class Object //物品类 {
friend int Knapsack(int *,int *,int,int); public:
int operator <(Object a) const {
return (d>=a.d); } int ID; //物品编号 float d; //单位重量价值 };

Typep Knapsack( Typep p[],Typew w[],Typew c,int n)

{ //为 Typep Knapsack 初始化

Typew W=0; //总重量

Typep P=0; //总价值

Object* Q=new Object[n]; //创建物品数组,下标从 0 开始

for(int i=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) //能装入所有物品

return P;

if(W<=c) //能装入所有物品

return P;

QuickSort(Q,0,n-1); //依物品单位重量价值非增排序

7

Knap<Typew,Typep> K;

K.p=new Typep[n+1];

K.w=new Typew[n+1];

for(int i=1;i<=n;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; return K.bestp;

}

例 2:批处理作业调度 课件第 5 章(2)P2-5 问题描述,课本 P125-127 解空间:排列树

算法描述:

class Flowshop

{

static int [][] m, // 各作业所需的处理时间

[] x,

// 当前作业调度

[] bestx, // 当前最优作业调度

[] f2,

// 机器 2 完成处理时间

f1,

// 机器 1 完成处理时间

f,

// 完成时间和

bestf, // 当前最优的完成时间和

n;

// 作业数

static void Backtrack(int i)

{

if (i > n)

{ for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestf = f; }

else

for (int j = i; j <= n; 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];

}

}

8

例 3:最大团问题,要会画解空间树。 class Clique {
friend int MaxClique(int **,int [],int); public: void Print(); //输出最优解 private:
void Backtrack(int i); int **a; //图 G 的邻接矩阵,下标从 1 开始 int n; //图 G 的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前团的顶点数 int bestn; //当前最大团的顶点数 }; void Clique::Backtrack(int i) { if(i>n) { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn; return;} //判断第 i 个顶点是否与已选顶点都有边相连 int OK=1; for(int j=1;j<i;j++) //x[1:i-1],已入选的顶点集
if(x[j]&&a[i][j]==0) //i 与当前团中的顶点无边相连 { OK=0; break; } //只要与当前团中一个顶点无边相连,则中止 if(OK) //进入左子树
9

{ 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. 请简述使用动态规划算法解题的基本步骤。P44 动态规划的设计分为以下 4 个步骤: (1)找出最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息,构造最优解。 2. 简述动态规划方法与分治法的异同。P44 相同点:动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题, 然后从这些子问题的解得到原问题的解。 不同点:分治法的子问题互相独立且与原问题相同。与分治法不同的是,适合于动态规划 求解的问题,经分解得到的子问题往往不是互相独立的。也就是各个子问题包含公共的子 子问题。 3. 试比较 Prim 算法与 Kruskal 算法的异同。105-P107 相同点:Prim(普里姆)算法和 Kruskal(克鲁斯卡尔)算法都可以看作是应用贪心算法构造最 小生成树的例子。利用了最小生成树性质。 不同点:
10

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)搜索方式:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最 小耗费优先的方式搜索解空间树。 五、算法应用题 1. 用动态规划求解凸多边形最优三角剖分问题。 三角剖分的结构及其相关问题 P61 (1)语法树与完全加括号方式 一个表达式的完全加括号方式相应于一棵完全二叉树,称为表达式的语法树。 例如,完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。
(2)语法树与凸多边形三角剖分 凸多边形 P={v0,v1,…vn-1}的三角剖分也可以用语法树表示。 如图:根结点是边 v0v 6(可以任选)。其他边则是语法树的叶子节点。 v0v 6 是三角形 v0v3v
11

6 的一条边。
2、三角剖分与矩阵连乘 P61 (1)一般来说,凸多边形的三角剖分和有 n-1 个叶节点的语法树存在一一对应关系。 (2)N 个矩阵连乘的完全加括号和有 n 个叶节点的语法树也存在一一对应关系 。 (3)所以,n 个矩阵连乘的完全加括号和有 n+1 个节点的凸多边形的三角剖分也存在一一对应 关系。
(4)矩阵连乘积中 A1 A2 …An 中的每个矩阵 Ai 对应于凸(n+1)边形中的一条边 vi-1vi。三角 剖分中的一条弦 vivj,i<j,对应于矩阵连乘积 A[i+1:j]。 (5)矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的特殊情况。
课后*题(第 3 章小结**) 对于如下矩阵链 P={10,100,5,50,30,20,60,45,50},请按照构造其最优完全加括号方式,并列出相应的语法树 和最优三角剖分图。
12

2. 用贪心算法求解活动安排问题/最小生成树问题/哈夫曼编码问题。 贪心算法求解活动安排问题 例:设待安排的 11 个活动的开始时间和结束时间按结束时间的非减序排列如下: 最小生成树问题 P103-P105
哈夫曼编码问题,前缀码二叉树表示法 例子: 图 a:与固定长度编码对应的树(叶子高度一致) 图 b:与可变长度编码对应的树(叶子高度不一致)
13

3. 用回溯法求解 0-1 背包问题/最优装载问题。 用回溯法求 0-1 背包问题。P133, 实例:n=5,M=50 N1 2 3 45 W 15 5 25 27 30 P 30 12 44 46 50 P/W 2 2.4 1.76 1.70 1.67 (1).令 bestp=0,将物体的序号按价值体积比排序结果是(2,1,3,4,5) N2 1 3 45 W 5 15 25 27 30 P 12 30 44 46 50 P/W 2.4 2 1.76 1.70 1.67 (2). 根据排序得到部分解(1,1,1,0),估计当前部分解的价值 b,86+(50-45)*1.67=94.3, b >bestp. (3). 继续向下搜索生成结点 F,得到可行解(1,1,1,0,0),得到价值为 86,更新 bestp=86(如图 第 3 步)

第3步

第5步

第8步

(4). 回溯:沿 E 回溯到左孩子 D,生成相应右孩子 G,得到部分解( 1,1,0,1 ),此时 b=93.1

b>bestp,可以生成右子树(第 4 步在第 5 步的基础上没有 H 和 I 的图形)

(5). 继续生成结点 H,I,得到可行解( 1,1,0,1,0 ),价值为 88,更新 bestp=88(如图第 5 步)

(6). 回溯 H 生成 J,得到部分解( 1,1,0,0 ),估计部分解 b=92>88(第 6 步在第 8 步的基

础上没有 K 和 L 的图形)

(7). 继续生成结点 K,得到可行解( 1,1,0,0, 1 ),价值为 92,更新 bestp=92(第 7 步在

第 8 步的基础上没有 L 的图形)

(8). K 是左孩子,生成其对应的右孩子 L,得到可行解( 1,1,0,0,0) (如图第 8 步)

14

(9). 回溯,沿结点 L 向上回溯到结点 B,生成结点 M,得到部分解 (1,0), 估计部分解 b=90<92,回溯(第 9 步在第 10 步的基础上没有 N 的图形) (10). 向上继续回溯生成结点 N,得到部分解(0),此时得到的 b=74+10*(46/27) =91.03<92, 回溯,此时已回到根结点,结束。最优解( 1,1,0,0, 1 ),价值为 92. (如图第 10 步)
练* n=8, M=110, W=( 1, 11,21,23,33,43,45,55 ) P=(11,21,31,33,43,53,55,65 ) 用回溯法求此 0-1 背包问题的最优解。
最优装载问题 P119 课件第 P37- P54 页 假定 n= 4,w= [ 8 , 6 , 2 , 3 ],c1 = c2 =12. 试根据改进后的最优装载算法找出最优装载量及相应的最优装载方案。 要求:
a) 列出问题的解空间。 b) 构造解空间树。 c) 根据递归回溯算法求出最优解和最优值。
15

六、算法设计题 使用贪心算法求解。 题型一: 开会问题: 某公司的会议很多,以至于全公司唯一的会议室不够用。现在给出这段时期的会议时间表, 要求你适当删除一些会议,使得剩余的会议在时间上互不冲突,要求删除的会议数最少。 解题算法:
template<class Type> void GS (int n, Type s[], Type f[], bool A[]) {
A[1]=false; int j=1; int sum=0; for (int i=2;i<=n;i++)
{ if (s[i]>=f[j]) { A[i]=false; j=i; } else {A[i]=true; sum++;} }
} 题型二: 试用贪心算法求解下列问题:将正整数 n 分解为若干个互不相同的自然数之和,使这些自然 数的乘积最大,写出该算法。先看看几个 n 比较小的例子,看能否从中找出规律:
16

算法分析: ? 猜想一下是不是将 n 拆成尽量多的数乘积最大?(拆出的数中最小为 2)。 ? 为了使因数个数尽可能多,我们用 n 减 2、3…i,直到 n<i。 ? 若此时 n 和 i 相等,则先将 i+1,同时 n-1。 ? 若此时 n>0,则均匀地分给前面各项。 ? 因此我们可以得到一个贪心策略,即将 n 不停地拆分开来,使得所有的数都不同且 不能再拆。
解题算法:
17

题型三: 田忌赛马:如果 3 匹马变成 n 匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任 意顺序选择他的赛马出赛。赢一局,田忌可以得到 200 两银子,输一局,田忌就要输掉 200 两银子。已知国王和田忌的所有马的奔跑速度,并且所有马奔跑的速度均不相同,现已经对 两人的马分别从快到慢排好序,请设计一个算法,帮助田忌赢得最多的银子。 解题思路:
? 先对两组马按速度排序。 ? 如果田忌(A)最快的马比齐王(B)最快的马快,直接赢; ? 如果 A 最快的马比 B 慢,用 A 最慢的马拼 B 最快的马; ? 如果 A 最慢的马比 B 最慢的马快,直接拼掉; ? 如果 A 最慢的马比 B 最慢的马慢,用 A 最慢的马拼 B 最快的马; ? 如果 A 和 B 最快和最慢的马都速度相同,用 A 最慢的马拼 B 最快的马 算法分析:
18


相关文档

  • 《算法分析与设计》期末考试复*题纲(完整版)
  • 《算法分析与设计》期末复*题
  • 算法分析与设计期末考试题
  • 算法分析与设计试题
  • 算法分析与设计 重点知识及试题
  • 算法分析与设计期末模拟试题
  • 算法分析与设计(第二版)王晓东 期末考试复*资料
  • 算法分析与设计考试复*题及参考答案jing
  • 算法分析与设计考试复*题及参考答案
  • 猜你喜欢

    电脑版