简介

本文用于记录软考中，与编程算法有关的题目。

如有想要记录的题目，欢迎评论补充！

关注公众号“月上老狗”，发送“软件设计师”，获取历年软件设计师软考真题。

算法策略

1. 分治策略（Divide and Conquer）：（最常见的二分法）分治策略将原问题分解成若干个规模较小且结构与原问题相似的子问题，递归地解决这些子问题，并将子问题的解合并起来得到原问题的解。对应的排序算法：归并排序和快速排序。
2. 贪心策略（Greedy Strategy）：贪心策略在每一步都选择当前状态下的最优解，希望通过局部最优解的累积达到全局最优解。
3. 动态规划（Dynamic Programming）：动态规划通过将原问题分解成若干个子问题，并以自底向上或自顶向下的方式求解子问题，从而得到原问题的最优解。
4. 回溯法（Backtracking）：回溯法是一种通过在问题的所有可能解空间中搜索解，并逐步构建解的方法，直到找到满足约束条件的解或者确定无解为止。
5. 线性规划（Linear Programming）：线性规划是一种通过线性函数构建模型，并通过线性不等式约束找到最优解的方法。
6. 模拟退火（Simulated Annealing）：模拟退火是一种通过模拟物理退火过程来寻找最优解的随机搜索算法，通过接受较差的解以避免陷入局部最优解。
7. 遗传算法（Genetic Algorithm）：遗传算法是一种受自然界进化过程启发的优化算法，通过模拟生物进化过程中的遗传、变异、选择等操作来寻找最优解。

排序算法

1. 有哪些排序算法？

参考：【常见排序算法原理及其时间复杂度】

2. 现需要对一个基本有序的数组进行排序，此时最适宜采用什么排序算法？时间复杂度是多少？

对于一个基本有序的数组进行排序，最适合使用的排序算法是 插入排序（Insertion Sort）。插入排序在处理基本有序的数组时非常高效，其时间复杂度可以接近 O(n)。

插入排序的优势：

1. 适应性强：插入排序在处理已经基本有序的数据时，性能非常好，接近线性时间复杂度 O(n)。
2. 稳定性：插入排序是稳定的排序算法，不会改变相同元素的相对顺序。
3. 原地排序：插入排序是一种原地排序算法，只需要常数级别的额外空间 O(1)。

插入排序的工作原理：插入排序通过构建一个有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体步骤如下：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果已经排序的元素大于新元素，则将该元素移到下一位置。
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤 2-5。

时间复杂度分析：

• 最坏情况下：当数组是逆序时，插入排序需要进行大量的移动操作，时间复杂度为 O(n^2)。
• 最优情况下：当数组已经完全有序时，插入排序只需进行一次比较，时间复杂度为 O(n)。
• 平均情况下：一般情况下时间复杂度为 O(n^2)，但对于基本有序的数组，插入排序仍然能够表现出接近 O(n) 的时间复杂度。

二叉树

1. 假设某消息中只包含7个字符{a,b,c,d,e,f,g}，这7个字符在消息中出现的次数为{5，24，8，17，34，4，13}，利用哈夫曼树(最优二叉树)为该消息中的字符构造符合前缀編码要求的不等长编码。各字符的编码长度分别为( )。

• A. a:4,b:2,c:3,d:3,e:2,f:4,g:3
• B. a:6,b:2,c:5,d:3,e:1,f:6,g:4
• C. a:3,b3:,c:3,d:3,e:3,f:2,g:3
• D. a:2,b:6,c:3,d:5,e:6,f:1,g:4

解析：由题意可知各字符及其出现的频率：a:5, b:24, c:8, d:17, e:34, f:4, g:13，哈夫曼树(最优二叉树)是优先编码出现最多的字符，所以由大到小一次是 e、b、d、g、c、a、f，最小的两个字符为同一个节点分支，所以分别是 e:1,b:2,d:3,g:4,c:5,a:6,f:6，所以 选择B。

2. 设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含k个结点时，其二叉链表结点中必有( )个空的孩子指针。

解析：在二叉树中，每个节点最多有两个孩子，因此每个节点有两个孩子指针。在二叉链表表示法中，如果一个节点没有左孩子或右孩子，那么对应的孩子指针就为空。

对于包含k个节点的二叉树，总共有2k个孩子指针。然而，除了根节点外，每个节点都是其父节点的一个孩子，因此有k-1个孩子指针被使用。所以，二叉链表节点中必有2k - (k - 1) = k + 1个空的孩子指针。

3. 根据其使用频率为其构造哈夫曼编码。以下编码方案中（ ？）是不可能的。

哈夫曼编码是一种无损数据压缩算法，通过构建一棵二叉树，将频率较高的字符用较短的编码表示，频率较低的字符用较长的编码表示，从而实现数据的压缩。哈夫曼编码的关键特性是前缀码：任何编码都不是其他编码的前缀，这确保了解码的唯一性和正确性。 判断一组数据是否哈夫曼编码的步骤：

1. 检查前缀属性：哈夫曼编码中，任何一个代码都不是另一个代码的前缀。
2. 解码数据：使用哈夫曼树（解码树）从左到右逐位解码数据。如果解码过程中遇到无法识别的代码，则该数据不是哈夫曼编码。
3. 检查唯一性：哈夫曼编码中，每个符号都有一个唯一的代码。 如果解码过程中遇到相同的代码对应不同的符号，则该数据不是哈夫曼编码。

选项	分析
A. {111, 110, 101, 100, 0}	正确。
B. {0000, 0001, 001, 01, 1}	正确。
C. {11, 10, 01, 001, 000}	正确。
D. {11, 10, 011, 010, 000}	不正确。因为哈夫曼编码可以认为是由哈夫曼树得来，而哈夫曼树的构造过程是自底向上的，最外层叶子节点必然是偶数个，但D选项最外层叶子节点是011/010/000三个，所以D不正确。

4. Kruskal算法求解最小生成树，用的是什么算法策略？最小生成树是什么？Kruskal算法又是什么？

最小生成树（Minimum Spanning Tree，简称MST）是一棵包含图中所有顶点的树，并且具有最小的总权值。在一个连通的带权无向图中，其最小生成树是一棵权值和最小的生成树。

Kruskal算法是一种用于求解最小生成树的贪心算法。其基本思想是按边的权值从小到大选择边，并保证选择的边不构成环，直到选出了n-1条边为止（n为图中顶点的个数）。Kruskal算法的具体步骤如下：

1. 将图中的所有边按权值从小到大进行排序。
2. 依次选择排序后的边，如果该边不与已选择的边构成环，则将其加入最小生成树的集合中。
3. 直到最小生成树中的边数达到n-1为止，其中n为图中顶点的个数。

权值：使用 Kruskal 求得的最小生成树就是连接所有顶点权值最小的通路，权值就是通路上的值之和。

加密算法

0. 常见加密算法的加密策略：

• AES（Advanced Encryption Standard）：加密策略：对称加密算法，使用相同的密钥进行加密和解密。支持128位、192位和256位密钥长度。运作方式：将明文分块，每个块与密钥进行混淆运算，反复执行多轮的代换和置换操作，最终生成密文。
• RSA（Rivest-Shamir-Adleman）：加密策略：非对称加密算法，使用一对公钥和私钥。运作方式：发送方使用接收方的公钥对数据进行加密，接收方使用自己的私钥对数据进行解密。RSA算法基于数论中的大数分解问题，依赖于两个大素数的乘积难以分解的特性。
• ECC（Elliptic Curve Cryptography）：加密策略：非对称加密算法，利用椭圆曲线上的离散对数问题来实现加密。优点：相比RSA等算法，ECC在相同的安全强度下使用的密钥长度更短，计算量更小，适合于资源受限的环境。
• MD5（Message Digest Algorithm 5）：加密策略：哈希算法，将任意长度的输入转换为128位的输出。特点：MD5是一种不可逆的哈希算法，相同的输入会产生相同的输出，不同的输入产生不同的输出，但是不能从输出推导出输入。
• SHA-256（Secure Hash Algorithm 256位）：加密策略：哈希算法，将任意长度的输入转换为256位的输出。特点：SHA-256是一种安全性更高的哈希算法，相比MD5更难以碰撞，用于验证数据的完整性和生成数字签名等场景。

1. 以下加密算法中适合对大量的明文消息进行加密传输的是( )。

选项	分析
A. RSA	RSA是一种非对称加密算法，用于加密和数字签名。 它使用公钥和私钥配对，适用于安全通信、数字签名和密钥交换。
B. SHA-1	SHA-1也是一种信息摘要算法，用于确保数据完整性。 它产生160位的散列值，目前仍然安全，但不推荐使用，因为存在更安全的替代算法。 注意：SHA-1已被证实存在碰撞漏洞，不再被广泛推荐使用。
C. MD5	MD5是一种信息摘要算法，用于确保信息传输的完整性。 它将任意长度的输入转换为128位（16字节）的散列值，通常用于校验文件完整性或密码存储。 注意：MD5已被攻破，不适合用于安全性认证，如SSL公开密钥认证或数字签名。
D. RC5	正确。RC5术语对称加密算法。适合对大量明文消息进行加密传输的是对称加密算法。 其中，高度安全且常用的对称加密算法之一是AES。

2. 假定用户A、B分别在I1和I2两个CA处取得了各自的证书，下面( )是A、B互信的必要条件

选项	分析
A. A、B互换私钥	正确。 在公钥基础设施（PKI）中，用户A和B分别在证书颁发机构（CA）I1和I2处取得了各自的证书。 这些证书包含了用户的公钥和一些身份信息，并由CA进行签名。 为了实现A和B的互信，他们需要交换各自的公钥，而不是私钥。私钥应该始终保持私密，不应该与任何人共享。 同时，CA的公钥需要被广泛分发，以便任何人都可以验证由CA签名的证书。 但是，CA的私钥也应该保持私密，不应该与任何人共享。
B. A、B互换公钥
C. I1、I2互换私钥
D. I1、I2互换公钥