填空题

GGBOND2026/1/30大约 11 分钟

填空题

第一章算法基础

1. 算法的“确定性”指的是组成算法的每条（指令）是清晰的，无歧义的。

2. 算法是指解决问题的( 一种方法) 或 (一个过程) 。

3. 任何可用计算机求解的问题所需的时间都与其（规模）有关。

4. 计算一个算法时间复杂度通常可以计算（循环次数）、（基本操作的频率）或计算步骤。

5. 算法是由若干条指令组成的有穷序列，且要满足输入，输出、确定性和（有限性）四条性质。

6. 问题的（最优子结构性质）是该问题可用动态规划算法或贪心算法求解的关键特征。

第二章递归与分治策略

1. 递归与分治策略的典型应用包括归并排序和快速排序等算法。其中，归并排序的时间复杂度为（O(n log n)），而快速排序的平均时间复杂度为（O(n log n)）。

解析：

归并排序的时间复杂度：归并排序采用分治策略，将数组分为两半，递归排序后合并。合并操作的时间复杂度为O(n)，递归深度为O(log n)，因此总时间复杂度为O(n log n)。
快速排序的时间复杂度：快速排序的平均时间复杂度为O(n log n)，但在最坏情况下（如数组已排序），时间复杂度为O(n²)。

核心知识点：归并排序和快速排序都是分治策略的典型应用，它们的时间复杂度分析基于分治策略的递归深度和每层的处理时间。

2. 从分治法的一般设计模式可以看出，用它设计出的程序一般是（递归算法）。

第三章贪心算法

1.（贪心选择）是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

2. 贪心算法在每一步选择中都采取当前状态下的（局部最优）决策，以期望最终得到全局最优解。这种方法通常用于解决具有（贪心选择）性质的问题。

解析：

贪心算法的基本思想：贪心算法在每一步都选择当前状态下的最优解，即局部最优解，希望通过局部最优解的选择最终得到全局最优解。
贪心选择性质：贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到。

3. 背包问题的贪心算法

void Knapsack(int n,float M,float v[],float w[],float x[])
{
       Sort(n,v,w); // 按单位重量价值降序排序物品
       int i;
       for (i=1;i<=n;i++) x[i]=0; // 初始化解向量
       float c=M; // 剩余背包容量
       float total_value=0; // 总价值
       for (i=1;i<=n;i++) {
             if (w[i]>c) break; // 如果当前物品重量大于背包容量，跳出循环
             x[i]=1; // 放入整个物品
             total_value+=v[i]; // 更新背包价值           
             (  c -= w[i]  ); // 更新背包容量（第一空答案）
        }
        if (i<=n) { 
             (  x[i] = c/w[i]  ); // 为了将背包填满，取当前物品的一部分（第二空答案）
             total_value+=x[i]*v[i]; // 更新背包的价值
        }
}

解析：

贪心算法解决背包问题的基本思想：
- 选择单位重量价值最高的物品优先放入背包
- 当物品无法完整放入时，取其一部分填满背包
- 该算法适用于分数背包问题，能得到最优解
代码执行流程：
- 首先对物品按单位重量价值降序排序（Sort函数实现）
- 初始化解向量x，所有元素为0
- 遍历排序后的物品，依次放入背包
- 当剩余容量不足时，计算能放入的比例
- 最后计算总价值
填空解析：
- 第一空：放入物品后，需要将剩余背包容量减去当前物品的重量，即 c -= w[i]
- 第二空：当物品无法完整放入时，取当前物品的一部分，比例为剩余容量与物品重量的比值，即 x[i] = c/w[i]

核心知识点：贪心算法解决分数背包问题的关键是按单位重量价值排序，然后依次放入物品，最后处理剩余容量的部分物品。

4. 贪心算法的基本要素是（贪心选择）性质和（最优子结构）性质。

第四章回溯法

1. N皇后问题的放置函数

在N皇后问题中，设x[i]为第i个的皇后位置，现有一个函数判断第k个皇后与先前皇后不同列、不同斜线，请完成下列填空。

bool Place(int k)   //考察皇后k放置在x[k]列是否发生冲突
    {
         for (i=1; i<k; i++)  
             if ( （x[k] == x[i]） || （abs(k - i) == abs(x[k] - x[i])））
                 return false;
             return true;
     }

解析：

N皇后问题的约束条件：
- 任意两个皇后不能在同一行（由解向量的定义保证，x[i]表示第i行皇后的列位置）
- 任意两个皇后不能在同一列
- 任意两个皇后不能在同一斜线上
冲突检测逻辑：
- 解向量的表示：在N皇后问题中，解向量x[i]表示第i行皇后所在的列号。因此，第i个皇后的位置可以表示为(i, x[i])，其中：
  - i是行号（从1到n）
  - x[i]是列号（从1到n）
- 遍历前k-1个皇后，检查与第k个皇后是否冲突
- 同一列冲突：如果x[k] == x[i]，表示第k个皇后（位置(k, x[k])）与第i个皇后（位置(i, x[i])）在同一列
- 同一斜线冲突：如果abs(k - i) == abs(x[k] - x[i])，表示第k个皇后与第i个皇后在同一斜线上
  - k - i是行差（第k行与第i行的行数差），abs(k - i)是行差的绝对值
  - x[k] - x[i]是列差（第k行皇后与第i行皇后的列数差），abs(x[k] - x[i])是列差的绝对值
  - 当行差绝对值等于列差绝对值时，两个皇后在同一斜线上（斜率为1或-1）
- 示例：若皇后A在(1, 2)，皇后B在(3, 4)，则行差为2，列差为2，绝对值相等，说明在同一斜线上；若皇后C在(2, 4)，皇后D在(4, 2)，则行差为2，列差为-2，绝对值相等，也在同一斜线上
填空解析：
- 第一空：需要检查是否在同一列，即x[k] == x[i]
- 第二空：需要检查是否在同一斜线，即abs(k - i) == abs(x[k] - x[i])

核心知识点：N皇后问题的冲突检测需要检查同一列和同一斜线，同一斜线的条件是行差绝对值等于列差绝对值。

2. 回溯法是一种基于（深度优先搜索）的搜索算法，通过尝试所有可能的候选解来找出满足条件的解。在搜索过程中，一旦发现当前路径不可能达到解，就立即（回溯）。

3. 以深度优先方式系统搜索问题解的算法称为( 回溯法 )。

4. 回溯法搜索解空间树时，常用的两种剪枝函数为（约束函数）和（限界函数）

5. 回溯法是一种既带有（系统性）又带有（跳跃性）的搜索算法。

6. 使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是（0/1背包问题），只使用约束条件进行裁剪的是（N皇后问题）。

解析：

回溯法的基本思想：回溯法是一种基于深度优先搜索的试探性搜索算法，它系统地搜索问题的解空间，尝试所有可能的候选解。
回溯的时机：当搜索到某个节点时，如果发现当前路径不可能达到解（即不满足约束条件或限界条件），就立即回溯到上一个节点，尝试其他可能的路径。

核心知识点：回溯法通过深度优先搜索解空间树，并在搜索过程中进行剪枝，以减少搜索空间，提高算法效率。

第五章分支限定法

1. 分支限界法常用于求解组合优化问题，它通过构造一个（解空间树），并根据某种规则对活结点进行（扩展），以减少搜索空间。常用的剪枝策略包括对（下界）的剪枝和对（上界）的剪枝。

2. 解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是（动态规划），需要排序的是（回溯法）和（分支限界法）。

解析：

分支限界法的基本思想：分支限界法通过构造解空间树，系统地搜索问题的解，并使用限界函数来剪枝，避免无效搜索。
活结点的扩展：分支限界法使用队列或优先队列来存储活结点，并根据某种规则（如优先级规则）对活结点进行扩展，选择下一个要处理的节点。
剪枝策略：分支限界法常用的剪枝策略包括：
- 下界剪枝：如果当前节点的下界大于已知的最优解，则剪枝
- 上界剪枝：如果当前节点的上界小于已知的最优解，则剪枝

第六章动态规划

1. 矩阵连乘问题的算法可由 (动态规划) 设计实现。

2. 若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的最长公共子序列 (BABCD)(CABCD)(CADCD)。

解析：

最长公共子序列(LCS)定义：LCS是指两个序列中最长的公共子序列，子序列不需要连续但保持相对顺序。
动态规划解法：
- DP数组定义：
  - dp[i][j] 表示序列X的前i个元素(X[1..i])和序列Y的前j个元素(Y[1..j])的最长公共子序列长度
  - 数组大小为(m+1)×(n+1)，其中m=len(X), n=len(Y)，多一行一列是为了处理边界条件
  - dp[0][j] = 0 和 dp[i][0] = 0 表示空序列与任何序列的LCS长度为0
- 状态转移方程：
  - 若X[i]=Y[j]，则dp[i][j] = dp[i-1][j-1] + 1，表示当前字符匹配，LCS长度加1
  - 否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示取X前i-1个与Y前j个，或X前i个与Y前j-1个的较大LCS长度
答案验证：
- BABCD：B(1)、A(3)、B(5)、C(6)、D(7)
- CABCD：C(2)、A(3)、B(5)、C(6)、D(7)
- CADCD：C(2)、A(3)、D(4)、C(6)、D(7)
  均为长度为5的有效LCS，符合最长公共子序列定义。

2. 动态规划的核心思想是将原问题分解为相互重叠的（子问题），通过保存中间结果避免重复计算，从而提高效率。动态规划的典型特征包括（最优子结构）和（重叠子问题）。

3. 动态规划算法的两个基本要素是（最优子结构性质）和（重叠子问题）性质

4. 动态规划算法的基本思想是将待求解问题分解成若干（子问题），先求解子问题，然后从这些子问题的解得到原问题的解。

解析：

动态规划的核心思想：动态规划通过将原问题分解为规模较小的子问题，先求解子问题，再利用子问题的解来求解原问题。
动态规划的典型特征：
- 最优子结构：原问题的最优解包含其子问题的最优解
- 重叠子问题：在求解过程中，会重复计算相同的子问题
中间结果的保存：动态规划通过保存子问题的解，避免重复计算，从而提高算法效率。

第七章智能算法

1. 在智能算法的范畴中，遗传算法的三个主要操作包括（选择）、（交叉）和（变异）。这些操作模拟了自然界生物的进化过程，以求解复杂优化问题。

解析：

遗传算法的基本思想：遗传算法模拟自然界生物的进化过程，通过选择、交叉和变异等操作，不断进化种群，以求解复杂优化问题。
遗传算法的三个主要操作：
- 选择：根据适应度函数选择优秀个体，使其有更大机会繁殖后代
- 交叉：将两个个体的染色体进行交换，生成新的个体
- 变异：对个体的染色体进行随机修改，增加种群的多样性