算法题库解析

没标的就死记吧，有标记的能学点就学点吧，毕竟算法很切近我们的生活，这些概念都比较好记

算法设计基础

1. 解决一个问题通常有多种算法，若说一个算法“有效”是指（ D ）。
   A.这个算法能在人的反应时间内将问题解决
   B.这个算法能在一定的时间和空间资源限制内将问题解决
   C.这个算法比其他已知算法都更快地将问题解决
   D.B和C
   问题解决叫有效，比其他算法快=更有效
2. 衡量一个算法好坏的标准是（ A）。
   ①运行速度快 ②占用空间少 ③可用递归实现 ④代码短
   A①② B.③④ C.①②③ D.①②③④
   算法衡量标准 时间复杂度，空间复杂度
3. 当算法用（ C ）来描述时就是程序。
   A.自然语言 B.流程图 C.程序设计语言 D.伪代码
4. 一个算法应该包含如下几条性质，除了（ A ）。
   A.二义性 B.有限性 C.正确性 D.可终止性
   算法不可以有二义性，因为其基本性质确切性相冲
5. 当算法用（ C ）来描述时就是程序。
   A.自然语言 B.流程图 C.程序设计语言 D.伪代码
6. 已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是（ B ）。
   A.计算1到50的乘积
   B.计算1到50的和
   C.计算50个1的和
   D.计算斐波那契数列的第50个元素的值
   +是求和，有n-1所以不为求50个数字的和，乘积需要用*,斐波那契是f(n-1)+f(n-2)
7. 程序是算法用某种程序设计语言的具体实现。
8. 算法是对解题方案准确而完整的描述，是一系列解决问题的清晰指令，使用系统的方法描述解决问题的策略机制。
9. 每个递归定义必须至少设置一个终止条件，找出可解的最小规模问题。
   算法的特性，有穷性，所以必须要有一个终止条件
10. 算法设计的基本步骤包括①问题分析、②算法策略/建立计算模型、③算法设计与描述、④算法分析、⑤算法实现、⑥测试、⑦结果整理与文档编制。
11. 程序步数可以精确的反映程序运行的实际时间。 （ × ）
12. 算法的时间复杂性只与问题的规模相关。 （ × ）
13. 简单的算法一定是高效的。 （ × ）

算法效率分析基础

1. 当输入规模为n时，算法增长率最小的是（ B ）。
   A.5n B.2log n C.2n2 D.nlog n
   时间复杂度的基本排序
2. 减少子问题个数，就是减少递归方程T(n)=aT(n/b)+f(n) 中（ B ）的值。
   A.n B.a C.b D.f(n)
   aT(n/b) 为子问题的求解复杂度
3. 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
4. 渐进算法分析是指（ B ）。
   A.算法在最佳情况、最差情况和平均情况下的代价
   B.当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析
   C.数据结构所占用的空间
   D.在最小输入规模下，算法的资源代价

蛮力法

1. 枚举法是蛮力法的一种表现形式，它根据问题中的条件将所有可能的情况一一列举出来，并逐一尝试，从中找出可能的解，因此，枚举范围的设定是提升枚举算法效率的关键。
2. 使用蛮力法求解数字谜题，它具有如下特征：
   

请问A、B、C、D的值各是多少？请写出两种求解思路并分别计算其时间复杂度。
参考答案：（写两种方法就可以）
法一:枚举法。暴力求解，在计算机中我们可以一个一个试
范围为30000–99999的五位数（因为只有30000以上的数乘以最高位才可能得到六位数），取符合要求的五位数来做乘法，对得到的结果再进行判断看是否满足条件
时间复杂度为99999-30000+1=70000。
法二：构造式的枚举法。因为题中只有三个数，我们可以枚举三个三字的各种情况，然后去检测结果输出
构造符合条件的五位数，A取值从3–9，B、C取值从0–9，构造符合后与A相乘，判断其是否满足积的要求，找出所有可能的解。
时间复杂度为71010=700，因为是三重循环。
法三：构造式的枚举法——除法。于2相反，就是列举结果，然后除去一个数，看结果是不是ABCAB式的
D的取值从1–9，A的取值从3–9，判断D是否可被A整除，整除后将得到的结果即被乘数进行判断，看其最高位是否与A相等且是否符合ABCAB的样式，如果都符合则找到一个解。
时间复杂度为7*9=63，因为是二重循环。

分治算法

算法思想分而治之，就是把大问题变成小问题解决再去合并

1. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ C ）。
   A.问题规模相同，问题性质相同 B.问题规模相同，问题性质不同
   C.问题规模不同，问题性质相同 D.问题规模不同，问题性质不同

2. 下述算法中，没有利用降低规模的思路来求解问题的是（ C ）。
   A.分治法 B.贪心法 C.回溯法 D.动态规划法
   回溯算法问题规模是相同的

3. 棋盘覆盖问题可以利用分治策略求解。 （ √ ）

4. 使用分治策略求解问题，划分出来的子问题越多，能够以更快的速度得到原问题的解。 （ × ）

5. 快速排序算法的性能取决于划分的对称性。 （ √ ）

6. 简述分治法的基本思想。分解-求解-合并
   (1) 将求解的较大规模的问题分割成k个更小规模的子问题；
   (2) 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；
   (3) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上
   逐步求出原来问题的解。

7. 排序问题：假设长度为n的数组arr，要按照从小到大排序。分别利用蛮力法和分治法设计两种不同的算法求解排序问题。要求：写出所使用的算法和该算法的实现思路，并分析其时间复杂度。
   （1）蛮力法
   顺序查找算法:遍历整个目标序列,每找到一个元素,都会和目标元素进行比对,直至找到目标元素或者遍历完整个目标序列(查找失败)。
   时间复杂度：O(n)
   (2)分治法
   将n个元素分成个数大致相同的两半,取a[n/2]与x作比较。如果x=a[n/2],则找到x,算法终止。如果x<a[n/2],则在集合的前半部分继续查找,否则在后半部分查找。
   时间复杂度：O(logn)

回溯算法

一个不撞南墙不回头的算法，他叫回溯也就是说撞完南墙就直接回头了

1. 以下关于剪枝函数的描述中，错误的是（ A ）。
   A.限界函数的计算和更新只可能发生在搜索树的叶子结点处
   B.极小化问题中，若某结点处的代价函数的值小于限界函数的值则进行剪枝操作
   C.约束函数剪去不可能包含可行解的子树
   D.限界函数剪去不可能包含最优解的子树
   限界函数不会更新，你做事的时候可能不因外部因素去调整你的步骤，但计算只会报错
2. 回溯法的效率不依赖于下列哪个因素（ D ）。
   A.满足显约束的值的个数 B.计算约束函数的时间
   C.计算限界函数的时间 D.确定解空间的时间
3. 以深度优先方式进行系统搜索问题解的算法称为（ B ）。深度优先一条路走到死，即不撞南墙不回头
   A.分治法 B.回溯法 C.贪心法 D.分支限界法
4. 使用回溯法求解问题，需要满足多米诺条件/性质。
5. 回溯算法是一种既系统又跳跃的枚举、试探方法，因此可将其看做蛮力算法的升级与改进。
   不撞南墙不回头，一条路走到死，符合蛮力，不过其有剪枝函数，可以避免一些不可能的情况而蛮力法无法避免
6. 旅行商问题不可以采用回溯法进行求解。 （ × ）
7. 回溯法是一种既带有系统性又带有跳跃性的搜索算法。 （ √ ）
8. 回溯法中每个活结点可能多次成为当前扩展结点。 （ √ ）
9. 请简述回溯法的算法思想
   回溯法也称试探法，可以把它看成一个在约束条件下对解空间树进行深度优先查找的过程。并在查找过程中剪去那些不满足条件的分支。当用回溯法查找到解空间树的某个节点时，如果发现当前路径不满足约束条件或不是历史最优时，就放弃对该节点的子树的查找，并逐层向其祖先节点返回。 否则，就进入该节点的子树，继续进行深度优先查找。

分支限界算法

一个我理解不动的东西

1. 优先队列式分支界限法选取扩展节点的原则是（ C ）。
   A.先进先出 B.后进先出 C. 节点的优先级 D.随机
   优先队列，so优先级
2. 采用最大效益优先搜索方式的算法是（ D ）。
   A.回溯法 B.动态规划法
   C.回溯法和分支限界法 D.分支限界法
   有点像广搜，拿走迷宫举例，深度搜索就是你到一个路口只能选一个分支前行，而广度搜索就是你学会了影分身，可以所有路口一起探索，这样效率就大大提高了
3. 常见的两种分支限界法为（ A ）。
   A.队列式分支限界法与优先队列式分支限界法
   B.队列式分支限界法与堆栈式分支限界法
   C.排列树法与子集树法
   D.广度优先分支限界法与深度优先分支限界法
4. 简述回溯法和分支限界法的相同点和不同点。相同点都在谈搜索，不同点，一个是深搜，一个是广搜
   相同点:
   二者都是在问题的解空间树上搜索问题的解,都可以通过剪枝来提高搜索效率。
   不同点:
   求解目标不同。
   回溯法的求解目标是找出解空间树T中满足约束条件的所有解,而分支限界法的求解目标是找出满足约束条件的一个解,在某种意义下的最优解。
   (3)对解空间的搜索方式不同。回溯法通常采用深度优先查找,而分支限界法则通常采用广度优先查找。在回溯法的解空间中,同一节点可以出现多次,而在分支限界法中,同一节点只会出现一次,不会发生回溯。
   (4)对节点进行存储的常用数据结构以及节点的存储特性也各不相同。除由搜索方式决定的不同存储结构外,分支限界法通常需要存储一些额外的信息,以便之后进一步展开搜索。

贪心算法

人都是贪婪的，只想要更多，这个算法是全局最优来达到局部最优，所以就会发生捡了西瓜丢了芝麻

1. 下面（ D ）不能用贪心算法解决。
   A.单源最短路径问题 B.背包问题
   C.最小生成树问题 D.N皇后问题
   皇后问题应该都清楚，死记就好
2. 能采用贪心算法求最优解的问题，一般具有的重要性质为（ A ）。
   A.最优子结构性质与贪心选择性质 B.重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质 D.预排序与递归调用
   可以贪就贪好吧
3. 背包问题贪心算法的时间复杂度为（ B ）。
   A.O(n2n) B.O(nlogn) C.O(2n) D.O(n)
4. 下列哪个问题不用贪心算法求解（ C ）。
   A.哈夫曼编码问题 B.单源最短路径问题
   C.棋盘覆盖问题 D.最小生成树问题
   N皇后
5. 贪心算法从初始阶段开始，每一个阶段总是做一个使局部最优的贪心选择。
6. 贪心法不能解决0/1背包问题。 （ √ ）
7. 贪心算法一定能得到问题的最优解。 （ × ）
8. 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 （ √ ）
9. 最优子结构性质的含义是原问题最优解包含其子问题的最优解。 （ √ ）
10. 学生有n项活动申请使用某一个会议室，每项活动都有一个开始时间和一个结束时间。任何两个活动都不能同时使用这个会议室。问如何安排这些活动，使得被安排活动的数量达到最多？
    （1）请写出两种贪心策略，比较它们并选出一种用于贪心算法。贪心，懒，先来的先举办，想要业绩，时间短的有限
    参考答案：
    贪心策略：按活动开始时间优先；按占用时间由短到长来选择；按结束时间从小到大选择；
    因为按结束时间从小到大选择能够使活动安排数量最多，所以选择这个贪心策略作为贪心算法的选择策略。
    （2）写出贪心算法求解的主要思路。
    参考答案，合理即可：
    将活动按照结束时间进行从小到大排序。挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续下一活动与集合A中活动的相容性。
11. 假设一共有N件物品，第i件物品的价值为V_i，重量为W_i，物品可以分割成任意大小。小明有一个最多只能装下重量为M的背包，他希望带走的物品价值越高越好，请设计贪心算法使带走的物品价值最高。
    （1）请写出两种的贪心策略，比较它们并选出一种用于贪心算法。拿最贵的，拿单位价值最贵的
    每次挑选价值最大的物品装入背包
    每次挑选重量最小的物品装入背包；
    每次选取单位重量价值最大的物品装入背包
    因为每次选取单位重量价值最大的物品装入背包的贪心策略可以保证所装物品价值最大，所以选择它作为贪心算法的选择策略。
    （2）写出贪心算法的主要思路。
    先求出所有物品的单位重量价值并进行由大到小的排序。其次从排序处于首位的物品开始选择直到无法完整装入背包的物品，将其部分装入背包以填满背包的总重量，从而求得价值最高的选择。
    该算法一定能够保证带走的物品价值最大吗？并简要说明理由。
    一定。理由（仅作为参考，合理即可）：背包选择放入的物品是可以拆分的，最终能将背包装满，按照单位重量价值由大到小装物品，能保证背包价值最大。
12. 下面的通讯数据构造哈夫曼树（左子树标1，右子树标0），求出通讯数据的哈夫曼编码，并对文本100010111001010进行解码。
    | 字符 | A | B | C |D|@|
    |–|–|–|–|–|–|
    | 出现频数 | 0.1 | 0.2 |0.15|0.4|0.15|

字符 A B C D @
出现频率 0.1 0.2 0.15 0.4 0.15
哈夫曼树：

由底向上构建的树，最终频数相加结果为1，构建结束坐1右0，从根到目标字符的路径即为哈夫曼编码

哈夫曼编码：
A:011
B:000
C:010
D:1
@:001
解码：
DBDAD@C

动态规划

动态规划

1. 动态规划算法的基本要素为（ C ）。
   A.最优子结构性质与贪心选择性质
   B.重叠子问题性质与贪心选择性质
   C.最优子结构性质与重叠子问题性质
   D.预排序与递归调用
2. 动态规划算法中存储子问题的解是为了避免重复求解子问题。
3. 所有能用动态规划法求解的问题也必然能用贪心法求解。 （ × ）
4. 简述分治法和动态规划之间的异同点。
   相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
   不同点：
   ①适合用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的（重叠子问题性质），而分治法中的子问题相互独立；
   ②动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解只需查询答案，故可获得多项式级时间复杂度，效率较高，而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。
5. 简述贪心算法的基本性质，并根据其性质简要分析贪心算法与动态规划的异同。
   参考答案：
   贪心算法的性质：
   最优子结构性质
   贪心选择性质
   贪心算法与动态规划的异同点：
   相同：贪心算法与动态规划都具有最优子结构的性质；
   不同：用贪心算法求解时，只考虑能使当前子问题达到最优解的一个子问题或值考虑当前最优解；而动态规划算法不具有贪心选择性质，从整体考虑所有可能导致最优解的子集，决策是全面的。
6. 使用动态规划算法求解数塔问题：
   有一个数塔，结点中数字为其权值，按自顶向下（或自底向上）方式行走，经过的每一个结点，可以选择向左或向右走，到达底部（或顶部），求一条自顶向下（或自底向上）的路径，所经过结点权值和最大。
   
   题目有路径的描述，存储是二维数组，所以两个框
   数组显示是这样

8
11	14
10 	5	8
3 	17  9 	4
18 	7 	12  6  16

尽力给他摆整齐了，下面的转移方程尽力理解吧
设r[i][j]表示第i行第j列的数到底层的最大总和。写出状态转移方程并解释其含义。
状态转移方程：

r[i][j]=max{r[i+1][j]，r[i+1][j+1]}+data[i][j];

含义：到达节点(i, j)时，下一步只能走(r+1,j)或者(r+1, j+1)。到底走哪一步取决于r[i+1][j]和r[i+1][j+1]的大小。在两者之间选择最大的，再加上data[i][j]就是r[i][j]的值。
求出所经过结点的最大权值和以及所经过的结点。
最大权值和：58
所经过的节点：8、11、10、17、12
7. 采用动态规划策略求最长公共子序列问题。给定两个序列X=(x_1,x_2,〖…,x〗_m )和Y=(y_1,y_2,〖…,y〗_n )，求 X 和 Y 的最长公共子序列。
设c[i][j]表示X_i=(x_1,x_2,〖…,x〗_i )与Y_j=(y_1,y_2,〖…,y〗_j )的最长公共子序列的长度。写出状态转移方程并解释其含义。
状态转移方程

含义
c[i][j]用于记录最长公共子序列的长度值。初始状态，当i=0或j=0时，c[i][j]=0;如果横竖（i,j）对应的两个元素相等，该格子的值为c[i-1][j-1]+1；如果不等，取c[i-1][j]和c[i][j-1]的最大值。
求出两个序列X={B,A,C,D,C,A}和Y={A,B,D,C,A}的一个最长公共子序列。
{A,D,C,A}或者{B,D,C,A}
8. 最大子段和问题：给定由n个整数组成的序列（可能有负整数）a_1,a_2,〖…,a〗_n，求该序列子段和的最大值，当所有整数均为负整数时定义其最大字段和为0。设计两种不同的算法求解最大子段和问题。要求：写出所使用的算法和该算法的实现思路，并分析其时间复杂度。
参考答案，写两种即可：
方法一：
蛮力法：枚举所有可能的子序列，计算它们的和并找出最大值。
时间复杂度：O(n^3)
方法二：
分治法：将序列分成长度相同的左右两半，分别计算左边的最大和、右边的最大和、跨边界的最大和，然后比较其中最大者。
时间复杂度：O(nlogn)
方法三：
动态规划法：对于序列中的每个元素，记录以该元素为结尾的最大字段和。设置一个数组CSum记录以第i个数结尾的最大字段和，首先进行初始化CSum[0]=0,然后根据状态转移方程计算数组CSum中的值：

（如果dp[i-1]为负数，则dp[i]=a[i],否者dp[i]=dp[i-1]+a[i]。）
最后在所有最大字段和中找到最大值即可。如果要找出最大和子序列，只要找和最大的那个下标，往前回溯到第一个不是负数的下标。
时间复杂度：O(n)