一、考点归纳
1）排序
2、查找
3、复杂度
4、经典问题
| 0 - 1 背包 | 动态规划 | 0 - 1 背包问题具有最优子结构性质和重叠子问题性质。通过动态规划可以利用一个二维数组来记录子问题的解，避免重复计算，从而高效地求解出背包能装下的最大价值。 |
| 分数背包 | 贪心算法 | 分数背包问题具有贪心选择性质，即通过每次选择单位重量价值最大的物品放入背包，最终能得到全局最优解。因为物品可以分割，所以贪心策略有效。 |
| 邻分背包 | 动态规划 | 与 0 - 1 背包类似，邻分背包也需要考虑不同物品组合下的最优解，通过动态规划可以较好地处理这种组合优化问题，将问题分解为子问题并求解。 |
| 旅行商问题 | 动态规划 | 动态规划可以通过记录已经访问过的城市集合和当前所在城市来求解，但时间复杂度较高，对于大规模问题不适用。模拟退火、遗传算法等近似算法可以在合理时间内得到近似最优解，适用于实际应用中的大规模问题。 |
| 矩阵链乘 | 动态规划 | 矩阵链乘问题具有最优子结构性质，通过动态规划可以将原问题分解为多个子问题，计算出子问题的最优解并存储，避免重复计算，从而高效地确定矩阵链乘的最优计算顺序，减少计算量。 |
| 最长公共子序列 | 动态规划 | 最长公共子序列问题具有最优子结构性质和重叠子问题性质。通过动态规划利用二维数组记录两个序列的子序列之间的最长公共子序列长度，从底向上计算，最终得到整个序列的最长公共子序列长度和具体序列。 |
5、加密
二、刷题
1、采用冒泡排序算法对(49,38,65,97,76,13,27,49)进行非降序排序，两趟后的序列为()
通过相邻元素交换的方式，最值冒泡，排到队尾
第一个泡 =》38,49,65,76,13,27,49,97
第二个泡 =》38,49,65,13,27,49,76,97
2、采用简单选择排序算法对序列(34,12,49,28,31,52,51,49)进行非降序排序，两趟后的序列为()
①最值12，与首元素34交换=>[12,34,49,28,31,52,51,49]=> [12]、[34,49,28,31,52,51,49]
②最值28，与首元素34交换=>[12]、[28,49,34,31,52,51,49]=>[12,28] [49,34,31,52,51,49]
3、对于一个初始无序的关键字序列，在下面的排序方法中，()第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来
①直接插入排序 ②冒泡排序 ③简单选择排序 ④堆排序 ⑤快速排序 ⑥归并排序
关键词最终有序序列中的位置=》这道题考察快速排序
以序列 [3, 2, 1]为例
①直接插入排序
整个序列会被划分为已排序序列和待排序序列两部分，将未排序数据插入到已排序序列的合适位置。 初始已排序[3],待排序[2,1] =>第一趟结束[2,3] , [1] 否
②冒泡排序 是
③简单选择排序 是
整个序列会被划分为已排序序列和待排序序列两部分，从待排序序列中找出最小的元素
初始已排序[],待排序[3,2,1]=》找出待排序的最值1 => 最值与第一个元素交换
=》[1,2,3]=》已排序[1],待排序[2,3]
④堆排序 是
因为堆排序属于选择排序，所以它符合条件
⑤快速排序 是
快速排序选择一个基准元素，将序列分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。在第一趟排序结束后，基准元素就被放置到了它在最终有序序列中的正确位置。例如，对于序列 [3, 2, 1]，若选择 3 为基准元素，第一趟排序后变为 [2, 1, 3]，基准元素 3 的最终位置确定了。
⑥归并排序 否
归并排序是将序列分成子序列，然后两两合并。在第一趟归并时，将其看作是由单个元素组成的子序列，即[3]、2]、[1]，合并后得到[2,3] [1]
综上，答案是②③④⑤。
4.1、对一组数据进行排序，要求排序算法的时间复杂度为O(nlogn),并要求排序是稳定的，则可采用（D 归并排序）算法。
对一组数据进行排序，要求排序算法的时间复杂度为O(nlogn),且空间复杂度为O(1)，则可采用（B 堆排序）算法。
A)直接插入排序 B)堆排序 C)快速排序 D)归并排序
4.2、下列排序算法中占用辅助存储空间最多的是(A)
A)归并排序 B) 快速排序 C) 堆排序 D)冒泡排序
4.3、(A)是稳定的排序算法
A)冒泡排序 B)快速排序 C)堆排序 D)简单选择排序
见第一张插图
5、折半查找问题
①二分查找就是折半查找，因为有一个考点是折半查找属于__分治__算法，如果题目出线二分查找，那就没人会选错了。
②在线性表L中进行二分(折半)查找，要求L顺序存储，元素有序排列
写代码的时候基于有序数组实现二分查找
③考察二分查找生成二叉判定树：“左子树元素小于根节点元素，右子树元素大于根节点元素”
2023真题：折半查找等概率查找某个包含8个元素的有序表，查找成功的平均查找长度为？2.625
假设有序表为{a1, a2, a3, a4, a5, a6, a7, a8}
- 第一次折半，中间元素是a4,因为(1 + 8) /2 = 4，所以二叉判定树的根节点是a4。
- 左子树是{a1, a2, a3}，右子树是{a5, a6, a7, a8}。
- 递归左子树 (1+3)/2=2=>{a1},{a3}
- 递归右子树 (5+8)/2=6=>{a5},{a7,a8}=>{a8}
二分查找生成的二叉判定树属于平衡二叉树(树中任意节点的左右子树高度差的绝对值不超过 1，并且左右子树也都是平衡二叉树。)
结点的高度代表查找长度(次数)，比如a4是1，因为第一次折半就是它，求总长度
1*1+2*2+3*4+4*1=18
=》平均长度 21/8 = 2.625
6、 采用贪心策略求解(A)问题，一定可以得到最优解
A)分数背包 B)0-1背包 C)旅行商 D)最长公共子序列
①贪心策略就是找最贵的。
- A. 分数背包：背包容量5kg，沙土A 3千克总价值100元，沙土B 6千克总价值100元，
沙土A更贵，根据贪心策略，先把沙土A装完，再装沙土B。 - B. 0 - 1 背包：在 0 - 1 背包问题中，物品是不可分割的，要么取要么不取。
背包容量1立方米，玉石原石A 0.4立方总价值100元，玉石原石B 1立方总价值200元，先把玉石原石A装完，再装原石B，装不上=》只装了100元，失败 - C. 旅行商问题：该问题是要找出一个旅行商在访问所有城市后回到起始城市的最短路径。贪心策略可能会选择当前距离最近的未访问城市作为下一个目的地，但这种局部最优的选择可能会导致错过全局最优解。
A->B=1,A->C=2,B->C=一百万,C->A=2,C->B=3,B->A=5;
由A开始，访问所有城市后回到A，由贪心法得到A->B->C->A=一百多万
最短路径实为A->C->B->A=10 - D. 最长公共子序列：求解最长公共子序列问题需要考虑两个序列的整体结构和对应关系，不能简单地通过贪心选择来确定。例如，对于序列 “AGGTAB” 和 “GXTXAYB”，如果使用贪心策略，可能会先选择第一个序列中的 “A”，但这样会导致错过更长的公共子序列 “GTAB”。所以贪心策略不适用于最长公共子序列问题。
7、在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质，则适用(C)算法设计策略得到最优解。
A) 分治 B)贪心 C) 动态规则 D) 回溯
若了解问题的解空间，并以广度优先的方式搜索解空间，则采用的是(D)算法策略。
A) 动态规则 B)贪心 C) 回溯 D) 分支界限
动态规划：最优子结构
贪心法：局部最优解
回溯法：深度优先
分支界限：广度优先
8、利用报文摘要算法生成报文摘要的目的是(A)
A)防止发送的报文被篡改 报文摘要算法，如MD5
B)对传输数据进行加密，防止数据被窃听 随便一个加密算法，如RSA
C)验证通信对方的身份，防止假冒
| 对比项目 | 数字证书 | 数字签名 |
|---|---|---|
| 概念 | 由证书颁发机构（CA）颁发的权威性电子文档，用于证明证书持有者的身份和公钥的合法性 | 使用发送者的私钥对要发送的数据的摘要进行加密得到的信息 |
| 功能 | 提供身份验证，确保通信双方能确认对方身份的真实性和合法性 | 保证数据的完整性、认证发送者的身份以及防止抵赖 |
| 防止报文被篡改 | 本身不能直接防止报文被篡改，无法检测和防止报文在传输过程中被篡改 | 可以通过验证签名来发现报文是否被篡改，因为报文篡改会导致摘要变化，使签名验证不通过 |
| 确认身份 | 用于确认拥有该证书的一方的身份，无论是服务器端还是客户端 | 主要用于确认发送报文一方的身份，接收方通过发送方公钥验证签名来确认发送者身份 |
D)防止发送方否认发送过的数据=》数字签名
9、系统交付用户使用了一段时间后发现，系统的某个功能响应非常慢。修改了某模块的一个算法使其运算速度得到了提升，则该行为属于(C)维护
A)改正性 修改错误
B)适应性 外部环境变化，比如屏幕变大
C)改善性 扩充功能、改善性能
D)预防性 系统监控与预警
至此完结，其他章节的选择题没有太多需要理解的东西，刷刷刷，要把大片的时间放到下午的大题上去。