首页 学习学习我爱学习 期末复习

# 选择题

  1. 对一个有序序列，以比较为基础的搜索算法的最坏情况时间复杂性的下界为（D）
    A. Ω(n)
    B. Ω(n²)
    C. Ω(n log n)
    D. Ω(log n)
  2. 算法分析是（C）
    A. 将算法用某种程序设计语言恰当地表示出来
    B. 在抽象数据集合上执行程序，以确定是否会产生错误的结果
    C. 对算法需要多少计算时间和存储空间作定量分析
    D. 证明算法对所有可能的合法输入都能算出正确的答案
  3. 下列排序算法不是基于交换的是（C）
    A. 冒泡排序
    B. 快速排序
    C. 合并排序
    D. 堆排序
  4. 用贪心法设计算法的关键是（B）
    A. 将问题分解为多个子问题来分别处理
    B. 选好贪心策略
    C. 获取各阶段间的递推关系式
    D. 满足最优性原理
  5. 回溯法求解 n 个顶点的图的最大团问题时，算法的复杂度是（D）
    A. O(n²)
    B. O(n³)
    C. O(nmⁿ)
    D. O(2ⁿ)

# 填空题

  1. 算法是由若干条指令组成的有穷序列，且满足输入、输出、确定性、有限性和能行性共 5 条性质
  2. 背包问题：n=6，C=10，V(1:6)=(15,59,21,30,60,5)，W(1:6)=(1,5,2,3,6,1)n=6，C=10，V(1:6)=(15, 59, 21, 30, 60, 5)，W(1:6)=(1, 5, 2, 3, 6, 1)，该问题的最大价值为 110
  3. 用回溯法对状态空间树进行搜索时，每个结点有可能多次成为扩展结点。
  4. 对线性表执行折半搜索时，要求线性表必须以数组方式存储且关键字有序
  5. 如果背包的容量为 100，而物品共有 10 个，则使用动态规划来解 0-1 背包问题数组大小为 1000

# 简答题

  1. 贪心法的两个基本要素
    • 最优子结构性质：最优子结构性质是指一个问题的最优解一定包含其子问题的最优解
    • 贪心选择性质：贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择获得，即通过逐步局部最优选择使最终的选择方案是全局最优的
  2. 请简述随机化算法分为哪四类。
    • 蒙特卡罗算法：运行时间确定，但结果可能有一定概率出错
    • 数值随机化算法：用于求解数值问题的近似解
    • 拉斯维加斯算法：结果一定正确，但运行时间具有随机性
    • 舍伍德算法：通过随机化削弱确定性算法最坏情况的影响
  3. 简述动态规划算法的基本要素。
    • 最优子结构性质：一个问题的最优解可以由其各个子问题的最优解组合得到。
    • 重叠子问题：在求解过程中会多次遇到相同的子问题，可以通过保存子问题的解来避免重复计算。
    • 自底向上的求解方法：从最小规模的子问题开始求解，逐步构造并得到原问题的最优解。
  4. 简述哈夫曼编码算法中采用的贪心策略。
    • 每次总是选择当前频率最低的两棵子树进行合并，以保证高频字符获得更短的编码，算法流程如下
      • 先把每个字符作为一棵单节点树放入最小优先队列中。然后重复以下操作（共 n−1n-1 次）
        • 从队列取出频率最小的两棵树，以它们为左右子树构建新树（频率为两者之和），再将新树放回队列。直到队列只剩一棵树为止
      • 最后，从根节点遍历到各叶子节点，左分支记为 00、右分支记为 11，即得到每个字符的变长前缀编码。
    • 这种 “局部每次合并最小频率对” 的贪心选择，最终实现了总加权路径长度最短的全局最优。
  5. 简述 Prim 算法构造最小生成树的基本思想。
    • 从一个顶点出发，每次总是优先选取与当前已连通子图相连的权值最小的边来扩展子图，直至覆盖所有顶点，从而保证生成树的总权值最小。具体过程为
      • 先任意选择一个顶点 ss 加入已选集合 SS（初始 S={s}S=\{s\}，边集 EE 为空），之后反复进行以下操作，直到 SS 包含图的所有顶点：
        • 在所有一端在 SS 内、另一端在 V−SV-S 的横跨边中，找出权值最小的那条边 (p,q)(p, q)，将该边加入 EE，同时把顶点 qq 加入 SS。
    • 这种 “每次局部选择连接已连通部分与外部的最小权边” 的贪心策略，最终能得到总权值全局最小的生成树。

# 求解题

使用回溯算法来求解图的 m(m=3)m(m=3) 着色问题的如下图实例。

  • 给出解向量的形式，指出解空间树的类型。
  • 描述搜索过程。
  • 画出找到一个解所生成的部分搜索树，并给出这个解。
    ![[Pasted image 20251219010514.png]]
  • 解向量形式与解空间树类型
    • 设图中共有 nn 个结点，用向量 (x1,x2,…,xn)(x_1, x_2, \ldots, x_n)，表示一种着色方案，其中 xi∈{1,2,3}x_i \in \{1,2,3\} 表示第 ii 个结点所选用的颜色编号 (1≤i≤n)(1 \le i \le n)。
    • 回溯算法按结点顺序逐一确定颜色，每一层对应一个结点的颜色选择，因此解空间可以表示为一棵高度为 nn 的搜索树。在不进行剪枝的理想情况下，每个结点均有 33 种颜色可供选择，该搜索树为一棵满 33 叉树。
  • 搜索过程与剪枝策略
    • 搜索从第一个结点开始，为其依次尝试颜色 1、2、31、2、3。当前已确定前 i−1i-1 个结点颜色后，继续为第 ii 个结点选择颜色。
    • 在搜索过程中采用如下剪枝规则：当为结点 ii 赋予颜色 xix_i 时，若该颜色与所有已着色且与结点 ii 相邻的结点颜色均不相同，则该选择是可行的，搜索继续向下一层展开；否则说明产生颜色冲突，该结点对应的分支被剪去，不再继续搜索其子树。
    • 通过这种剪枝，可以有效减少无效的搜索路径，提高算法效率。
  • 部分搜索树与可行解
    • 按照上述搜索顺序与剪枝规则，在搜索过程中一旦找到满足所有相邻结点颜色不同的完整赋值，即得到一个可行解。 在本例中，搜索生成的部分解空间树中可以得到如下一个合法的 3 - 着色方案：(1,2,3,2,1)(1,2,3,2,1)

![[Pasted image 20251219010528.png]]

# 算法分析

题目：n 皇后问题，给出一种放置方案。要求：写出算法策略的思想，写出算法实现的主要步骤

选择回溯法，其思想是一种尝试并撤销的搜索策略，适合解决这类约束满足问题。其主要步骤为：

  • 从第 0 行开始，逐行放置皇后，依次尝试在每一行放置一个皇后
  • 在当前行尝试将皇后放在每一列，如果放置后不与之前已放置的皇后冲突，则进入下一行继续放置；如果所有列都尝试失败，则回溯到上一行，改变上一行的皇后位置重新尝试。
  • 每次放置皇后时，只需检查是否与之前行的皇后冲突（同一列、同一正斜线、同一反斜线）。由于每行只放一个皇后，保证了不同行。
  • 终止条件：当成功放置到第 n 行（即放置了 n 个皇后），说明找到一种合法方案。