【期末测验】《算法分析与计划》期末复习题
《算法分析与计划》期末复习题一、选择题
1.算法必须具备输入、输出和（ D ）等4个特性。
A．可行性和安全性 B．确定性和易读性
C．有穷性和安全性 D．有穷性和确定性
2.算法分析中，记号O表现（ B ），记号Ω表现（ A ）
A.渐进下界 B.渐进上界
C.非紧上界 D.紧渐进界
3.假设某算法在输入规模为n时的盘算时间为T(n)=32^n。在某台盘算机上实现并完成概算法的时间为t秒。现有另一台盘算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：32n*64=3*2x
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个数分别是（ B ）。
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 ）。
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 ）。
A．找出最优解的性子 B．构造最优解
C．算出最优解(应该是最优值) D．定义最优解
16.下面问题（ B ）不能使用贪心法办理。
A．单源最短路径问题 B．N皇后问题
C．最小耗费天生树问题 D．背包问题
17.使用二分搜刮算法在n个有序元素表中搜刮一个特定元素，在最好情况和最坏情况下搜刮的时间复杂性分别为（ A ）。
A．O(1)，O(logn) B．O(n)，O(logn)
C．O(1)，O(nlogn) D．O(n)，O(nlogn)
18.优先队列式分支限界法选取扩展结点的原则是（ C ）。
A．先辈先出 B．后进先出
C．结点的优先级 D．随机
19.下面不是分支界限法搜刮方式的是（ D ）。P161
A．广度优先 B．最小泯灭优先
C．最大效益优先 D．深度优先
20.分支限界法解最大团问题时，活结点表的构造形式是（ B ）。
A．最小堆 B．最大堆
C．栈 D．数组
21.下列关于盘算机算法的描述不正确的是（ C ）。
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 ）。
A．该问题的规模缩小到一定的程度就可以容易地办理
B．该问题可以分解为若干个规模较小的雷同问题
C．使用该问题分解出的子问题的解可以合并为该问题的解
D．该问题所分解出的各个子问题是相互独立的
25.下列关于回溯法的描述不正确的是（ D ）。
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) ，该算法所需的时间与 运行时间 和 划分 两方面因素有关。
7.0-1背包问题的解空间树为 完全二叉 树**；n后问题的解空间树为 分列 树；**
8.常见的分支限界法有队列式（FIFO）分支限界法和优先队列式分支限界法。
9.回溯法搜刮解空间树时常用的两种剪枝函数为 约束函数 和 剪枝函数 。
10.分支限界法解最大团问题时，活结点表的构造形式是 最大堆 ；分支限界法解单源最短路径问题时，活结点表的构造形式是 最小堆 。
三、算法填空题
1.递归求解Hanoi塔问题/阶乘问题。
例1 :阶乘函数n!
阶乘的非递归方式定义：
试写出阶乖的递归式及算法。
递归式为： 界限条件
递归方程
递归算法：
int factorial (int n)
{ if (n==0) return 1; 递归出口
return n * factorial (n-1); 递归调用
}
例2:用递归技能求解Hanoi塔问题,Hanoi塔的递归算法。
其中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.用分治法求解快速排序问题。
template
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)；
}
}
Partition函数的详细实现
template
int Partition (Type a[], int p, int r)
{
int i = p, j = r + 1;
Type x=a;
// 将< x的元素交换到左边区域
// 将> x的元素交换到右边区域
while (true) {
while (a[++i] <x && i<r);
while (a[- -j] >x);
if (i >= j) break;
Swap(a, a);
}
a = a;
a = x;
return j;
}
3.用贪心算法求解最优装载问题。
template
void Loading(int x[], Type w[], Type c, int n)
{
int *t = new int ;
Sort(w, t, n);
for (int i = 1; i <= n; i++) x = 0;
for (int j = 1; j <= n && w] <= c; j++)
{x] = 1; c -= w];}
}
四、简答题
1.请简述使用动态规划算法解题的根本步调。
动态规划的计划分为以下4个步调：
(1)找出最优解的性子，并刻划其结构特性。
(2)递归地定义最优值。
(3)以自底向上的方式盘算出最优值。
(4)根据盘算最优值时得到的信息，构造最优解。
2.简述动态规划方法与分治法的异同。
雷同点：动态规划算法与分治法类似，其根本头脑也是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。
不同点：分治法的子问题互相独立且与原问题雷同。与分治法不同的是，适合于动态规划求解的问题，经分解得到的子问题每每不是互相独立的。也就是各个子问题包含公共的子子问题。
3.试比较Prim算法与Kruskal算法的异同。
雷同点：Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法都可以看作是应用贪心算法构造最小天生树的例子。使用了最小天生树性子。
不同点：
Prim(普里姆)算法：在这个过程中选取到的全部边恰好构成G的一棵最小天生树T，T中包含G的n-1条边，且不形成回路。
Kruskal(克鲁斯卡尔)算法：是构造最小天生树的另一个常用算法。该算法不是通过扩充连通子集来举行贪心选择。而是通过选择具有最小权的边的集合来举行贪心选择。在选择的同时可以举行连通操作以便形成天生树。
4.请简述分支限界法的搜刮策略。
(1)分支限界法以广度优先或以最小泯灭（最大效益）优先的方式搜刮问题的解空间树。
(2)每一个活结点只有一次机会成为扩展结点。
(3)活结点一旦成为扩展结点，就一次性产生其全部儿子结点。
(4)儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
(5)从活结点表中取 下一结点 成为当前扩展结点，并重复上述结点扩展过程。这个过程不停连续到找到所需的解或活结点表为空时为止。
5.试比较分支限界法与回溯法的异同。
不同点：
(1)求解目的：回溯法的求解目的是找出解空间树中满足约束条件的全部解，而分支限界法的求解目的则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
(2)搜刮方式：回溯法以深度优先的方式搜刮解空间树，而分支限界法则以广度优先或以最小泯灭优先的方式搜刮解空间树。
1.算法紧张特性是什么？
答：确定性、可实现性、输入、输出、有穷性
2.算法分析的目的是什么？
答：分析算法占用盘算机资源的情况，对算法做出比较和评价，计划出额更好的算法。
3.算法的时间复杂性与问题的什么因素相干？
答：算法的时间复杂性与问题的规模相干，是问题巨细n的函数。
4.算法的渐进时间复杂性的含义？
答：当问题的规模n趋向于无穷大的时候，影响算法服从的紧张因素是T（n）的数量级，而其他因素仅是时间复杂度相差常数倍，因此可以用T（n）的数量级评价算法、时间复杂度T（n）的数量级称为渐进时间复杂度。
5.最坏情况下的时间复杂性和均匀时间复杂性有什么不同？
答：最坏情况下的时间复杂性和均匀时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn
均匀时间复杂性是全部输入实例的处理时间与各自概率的乘积和：
A(n) =∑P(I)T(n，I) I∈Dn
6.简述二分检索（折半查找）算法的根本过程。
答：设输入是一个按非降次序分列的元素表A 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A找x，否则在A[ (i+j)/2+1：j] 找x。上述过程被反复递归调用。
7.背包问题的目的函数和贪心算法最优化量度雷同吗？
答：不雷同。目的函数：获得最大利润。最优量度：最大利润/重量比。
8.采用回溯法求解的问题，其解如何表现？有什么规定？
答：问题的解可以表现为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i<n)一定合理。
9.回溯法的搜刮特点是什么？
答：在解空间树上跳跃式地深度优先搜刮，即用判定函数考察x的取值，如果x是合理的就搜刮x为根节点的子树，如果x取完了全部的值，便回溯到x。
10.n皇后问题回溯算法的鉴别函数place的根本流程是什么？
答：将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。
11.为什么用分治法计划的算法一般有递归调用？
答：子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。
12.为什么要分析最坏情况下的算法时间复杂性？
答：最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较均匀时间复杂性游有可操作性。
13.简述渐进时间复杂性上界的定义。
答：T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)<f(n)，这种关系记作T(n)=O(f(n))。
14.二分检索算法最多的比较次数？
答：二分检索算法的最多的比较次数为 log n 。
15.快速排序算法最坏情况下需要多少次比较运算？
答：最坏情况下快速排序退化成冒泡排序，需要比较n2次。
16.贪心算法的根本头脑？
答：是一种依据最优化量度依次选择输入的分级处理方法。根本思路是：首先根据题意，选取一种量度尺度；然后按这种量度尺度对这n个输入排序，依次选择输入量加入部门解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部门解中。
17.回溯法的解（x1,x2,……xn）的隐隐束一般指什么？
答：回溯法的解（x1,x2,……xn）的隐隐束一般指个元素之间应满足的某种关系。
18.论述归并排序的分治思路。
答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。
19.快速排序的根本头脑是什么。
答：.快速排序的根本头脑是在待排序的N个记载中任意取一个记载，把该记载放在终极位置后，数据序列被此记载分成两部门。全部关键字比该记载关键字小的放在前一部门，全部比它大的放置在后一部门，并把该记载排在这两部门的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部门内只有一个记载为止。
20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？
答：在定义一个过程或者函数的时候又出现了调用本过程或者函数的身分，既调用它本身本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。
五、算法计划题
使用贪心算法求解。
题型一：
开会问题：
某公司的集会很多，以至于全公司唯一的集会室不够用。现在给出这段时期的集会时间表，要求你适当删除一些集会，使得剩余的集会在时间上互不辩论，要求删除的集会数最少。
解题算法:
template
void GS (int n, Type s[], Type f[], bool A[])
{
A=false;
int j=1;
int sum=0;
for (int i=2;i<=n;i++)
{
if (s>=f) { A=false; j=i; }
else {A=true; sum++;}
}
}
题型二：
试用贪心算法求解下列问题：将正整数n分解为若干个互不雷同的天然数之和，使这些天然数的乘积最大，写出该算法。先看看几个n比较小的例子，看可否从中找出规律：
算法分析：
猜想一下是不是将n拆成只管多的数乘积最大？（拆出的数中最小为2）。
为了使因数个数尽大概多，我们用n减2、3…i，直到n<i。
若此时n和i相等，则先将i+1,同时n-1。
若此时n>0，则匀称地分给前面各项。
因此我们可以得到一个贪心策略，即将n不停地拆分开来，使得全部的数都不同且不能再拆。
解题算法:
题型三：
田忌赛马：如果3匹马酿成n匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子。已知国王和田忌的全部马的奔驰速度，并且全部马奔驰的速度均不雷同，现已经对两人的马分别从快到慢排好序，请计划一个算法，帮助田忌赢得最多的银子。
解题思路：
先对两组马按速度排序。
如果田忌(A)最快的马比齐王(B)最快的马快,直接赢;
如果A最快的马比B慢,用A最慢的马拼B最快的马;
如果A最慢的马比B最慢的马快,直接拼掉;
如果A最慢的马比B最慢的马慢,用A最慢的马拼B最快的马;
如果A和B最快和最慢的马都速度雷同,用A最慢的马拼B最快的马
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]