算法：练习（选择题）
1、关于算法的说法中正确的有（C）。
Ⅰ.求解某⼀类问题的算法是唯⼀的（如：冒泡排序可以⽤：穷举法、递归）
Ⅱ.算法必须在有限步操作之后停⽌
Ⅲ.算法的每⼀步操作必须是明确的，不能有歧义或含义模糊
Ⅳ.算法执⾏后⼀定产⽣确定的结果
A.1个
B.2个
C.3个
D.4个
算法设计的⽬标：
（1）正确性：正确地执⾏预先规定的功能和性能要求。
（2）可使⽤性（⽤户友好性）：可以很⽅便地使⽤。
（3）可读性：易于理解。
（4）健壮性：提供异常处理，能够对不合理的数据进⾏检查。
（5）⾼效率与低存储：执⾏时间短的算法效率⾼，所需的最⼤存储容量低的算法好。
二叉树的基本性质算法的重要特性：
（1）有限性：执⾏有限步之后结束。
（2）确定性：每⼀条指令⽆⼆义性。
（3）可⾏性：每⼀条运算都能精确地执⾏。
（4）输⼊性：⼀个算法有零个或多个输⼊。
（5）输出性：⼀个算法有⼀个或多个输出。
2、T(n)表⽰当输⼊规模为n时的算法效率，以下算法效率最优的是（C）。
A.T(n)= T(n-1)+1，T(1)=1
B.T(n)= 2n2
C.T(n)= T(n/2)+1，T(1)=1
D.T(n)=3nlog2n
3、以下关于渐近记号的性质是正确的是（A)
A.f(n)=O(g(n))，g(n)=O(h(n))⇒f(n)=O(h(n))      (传递性)
B.f(n)=O(g(n))，g(n)=O(h(n))⇒h(n)=O(f(n))        (不满⾜传递性)
C.O(f(n))+O(g(n))=O(min(f(n),g(n)))      (max)
D.f(n)=O(g(n))⇔g(n)=O(f(n))    (上限不满⾜反⾝性)
4.Hanoi塔问题如下图所⽰，现要求将塔座A上的所有圆盘移到塔座B上，并仍按同样顺序叠置，移动圆盘时遵守Hanoi塔问题的移动规则，由此设计出解Hanoi塔问题的递归算法正确的是（B）
A、
void Hanoi(int n, int A,int C,int B){
if(n>0)
{Hanoi (n-1,A,C,B);
Move(n,a,b);
Hanoi(n-1,C,B,A);
}
}
B、
void Hanoi(int n, int A,int B,int C){
if(n>0){
Hanoi (n-1,A,C,B);
Move(n,a,b);
Hanoi(n-1,C,B,A);
}
}
C、
void Hanoi(int n,int C,int B,int A){
if(n>0)
{
Hanoi(n-1,A,C,B);
Move(n,a,b);
Hanoi(n-1,C,B,A);
}
D、
void Hanoi(int n, int C,int A,int B)
{
if(n>0)
{
Hanoi(n-1,A,C,B);
Move(n,a,b);
Hanoi(n-1,C,B,A)
}
5.分治法的设计思想是将⼀个难以直接解决的⼤问题分割成规模较⼩的⼦问题，分别解决⼦问题，最后将⼦问题的解组合起来形成原问题的解。这要求原问题和⼦问题（C）。
A.问题规模相同，问题性质相同
B.问题规模相同，问题性质不同
C.问题规模不同，问题性质相同
D.问题规模不同，问题性质不同
分治法是采⽤递归的思想，将⼤问题转化为⼩问题，然后由⼩问题（⼦问题之间相互独⽴且与原问题的形式相同）构造出⼤问题的解。
分治法的特性：
（1）问题的规模缩⼩到⼀定程度可以很容易的解决；
（2）可以分解为若⼲个规模较⼩的相同问题；
（3）⼦问题的解可以合并为该问题的解；
（4）该问题分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题
6、在寻n个元素中第k⼩元素问题中，如快速排序算法思想，运⽤分治算法对n个元素进⾏划分，如何选择划分基准？下⾯（D）答案解释最合理。
A.随机选择⼀个元素作为划分基准
B.取⼦序列的第⼀个元素作为划分基准
C.⽤中位数的中位数⽅法寻划分基准
D.以上皆可⾏，但不同⽅法，算法复杂度上界可能不同
取第⼀个元素的话时间复杂度为（Onlog2n），P81。
7、⼆分搜索算法是利⽤( A )实现的算法。
A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
⼆分搜索（⼆分查）：搜索过程从数组的中间元素开始，如果中间元素正好是要查的元素，则搜索过程结束；如果某⼀特定元素⼤于或者⼩于中间元素，则在数组⼤于或⼩于中间元素的那⼀半中查，⽽且跟开始⼀样从中间元素开始⽐较。如果在某⼀步骤数组为空，则代表不到。但是前提是搜索的数组是有序的。
8、Strassen矩阵乘法是利⽤( A )实现的算法。
A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
9、使⽤分治法求解不需要满⾜的条件是( A )。
A、⼦问题必须是⼀样的
B、⼦问题不能够重复
C、⼦问题的解可以合并
D、原问题和⼦问题使⽤相同的⽅法解
规模改变，问题性质不变
10、实现合并排序利⽤的算法是( A )
A、分治策略
B、动态规划法
C、贪⼼法
D、回溯法
先分解：将序列分解为length长度的若⼲⼦问题
求解⼦问题：将相邻的两个⼦问题合并为⼀个有序的⼦序列
合并：合并不需要执⾏任何操作
11、实现⼤整数的乘法是利⽤的算法( C )
A、贪⼼法
B、动态规划法
C、分治策略
D、回溯法
12.（C）是贪⼼算法的基本要素。
A.重叠⼦问题
B.构造最优解
C.贪⼼选择性质
D.定义最优解
贪⼼算法基本要素：
（1）贪⼼选择性质：每⼀步所做的贪⼼选择最终导致问题的整体最优解。
（2）最优⼦结构性质：⼀个问题的最优解包含其⼦问题的最优解。
13.采⽤贪⼼算法的最优装载问题的主要计算量在于将集装箱依其重量从⼩到⼤排序，故算法的时间复杂度为（D）。
A.O(n)
B.O(log2n)
C.O(n3)
D.O(nlog2n)
有⼀批集装箱要装上⼀艘载重量为C的轮船，其中集装箱i的重量为Wi。要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
14.⼀棵哈夫曼树共有215个结点，对其进⾏哈夫曼编码，共能得到（B ）个不同的码字。
A.107
B.108
C.214
D.215
哈夫曼树中只有度为零和度为⼆的节点，没有度为⼀的结点，且n0=n2+1（⾮空⼆叉树的性质）,n=n0+n2
只有叶⼦结点能够产⽣码字，也就是计算度为零的结点。
15、哈弗曼编码的贪⼼算法所需的计算时间为（B）。
A、O（n2n）
B、O（nlog2n）
C、O（2n）
D、O（n）
Onlog2n
16、背包问题的贪⼼算法所需的计算时间为（B）
A、O（n2n）
B、O（nlog2n）
C、O（2n）
D、O（n）
问题描述：与0 / 1背包问题不同的是，完全背包问题可以装⼊⼀部分物品进⼊背包，也就是说背包⼀定可以装满。⽅案：将物品以单位价值从⼤到⼩排序，除最后⼀个物品只取⼀部分之外，其他物品要么全拿，要么不拿
时间复杂度：快速排序（Onlog2n）
while循环（n）
所以时间复杂度为（Onlog2n）
17、以下不属于贪⼼算法的是（ D）
A.Prim算法
B.Kruskal算法
C.Dijkstra算法
D.深度优先遍历
（1）Prim算法：按照顶点规定
Kruskal算法：按照边规定
Dijkstra算法：单源最短路径
深度优先遍历：回溯，⾛不通的时候回溯
18、下⾯问题( B )不能使⽤贪⼼法解决。
A、单源最短路径问题
B、N皇后问题
C、最⼩⽣成树问题
D、背包问题
N皇后为递归。
19、关于0/1背包问题，以下描述正确的是（D）。
A.可以使⽤贪⼼算法到最优解
B.能到多项式时间的有效算法
C.使⽤教材介绍的动态规划⽅法可求解任意0－1背包问题
D.对于同⼀背包与相同的物品，背包问题取得的总价值⼀定⼤于等于做0/1背包问题
A：穷举法（结合求解幂集的⽅法）
C：动态规划可以求解完全背包问题：每种物品可以挑选任意多件。
20.⼀个问题可⽤动态规划算法或贪⼼算法求解的关键特征是问题的（ C）。
A.贪⼼选择性质
B.重叠⼦问题
C.最优⼦结构性质
D.定义最优解
最优⼦结构性质：⼀个问题的最优解包含其⼦问题的最优解。
21.能采⽤贪⼼算法求最优解的问题，⼀般具有的重要性质为:( A )
A、最优⼦结构性质与贪⼼选择性质
B、重叠⼦问题性质与贪⼼选择性质
C、最优⼦结构性质与重叠⼦问题性质
D、预排序与递归调⽤
贪⼼算法基本要素：
（1）贪⼼选择性质：每⼀步所做的贪⼼选择最终导致问题的整体最优解。
（2）最优⼦结构性质：⼀个问题的最优解包含其⼦问题的最优解。
22. ( D )是贪⼼算法与动态规划算法的共同点。
A.重叠⼦问题 B、构造最优解 C、贪⼼选择性质 D、最优⼦结构性质
最优⼦结构性质：⼀个问题的最优解包含其⼦问题的最优解。
23.下列算法中不能解决0/1背包问题的是(A)
A、贪⼼法
B、动态规划
C、回溯法
D、分⽀限界法
（1）贪⼼算法在某些情况下会出错。
（2）0-1背包问题可以⽤动态规划、回溯法和分⽀限界法这三种任意⼀种算法策略来求解。
24.下列算法中通常以⾃底向上的⽅式求解最优解的是( B )。
A.分去限界法 B、动态规划法 C、贪⼼法 D、回溯法
25.贪⼼算法与动态规划算法的主要区别是( B )。
A、最优⼦结构
B、贪⼼选择性质
C、构造最优解
D、定义最优解
贪⼼算法基本要素：
（1）贪⼼选择性质：每⼀步所做的贪⼼选择最终导致问题的整体最优解。
（2）最优⼦结构性质：⼀个问题的最优解包含其⼦问题的最优解。
⽽动态规划也具有最优⼦结构性质。
26.动态规划算法的基本要素为( C )
A、最优⼦结构性质与贪⼼选择性质
B、重叠⼦问题性质与贪⼼选择性质
C、最优⼦结构性质与重叠⼦问题性质
D、预排序与递归调⽤
（1）⼦问题重叠性（要与分治法区别，分治的⼦问题是相互独⽴的）
（2）最优⼦结构性质
27.关于回溯法以下叙述中不正确的是（C）。
A.回溯法有“通⽤解题法”之称，它可以系统地搜索⼀个问题的所有解或任意解
B.回溯法是⼀种既带系统性⼜带有跳跃性的搜索算法
C.回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
D.回溯算法在⽣成解空间的任⼀结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的⼦树的搜索，逐层向祖先结点回溯 C：借助于树结构
28、下列算法中通常以深度优先⽅式系统搜索问题解的是( D )。
A、备忘录法
B、动态规划法
C、贪⼼法
D、回溯法
回溯法：深度优先
分⽀限界法：⼴度优先
29.下⾯哪种函数是回溯法中为避免⽆效搜索采取的策略( B )
A、递归函数
B、剪枝函数
C、随机数函数
D、搜索函数

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。