final-exam/算法设计与分析/试题册/试题1.md

tags, create time

tags	create time
算法设计与分析 试题	2026-06-10 10:00

试题 1 — 武汉科技大学《算法设计与分析》

概述

• 课程：算法设计与分析
• 学校：武汉科技大学
• 题型：单选题、简答题、代码分析题、算法设计与编程题
• 知识点：算法复杂度分析、贪心算法、分治法、动态规划、回溯法、图算法

[!tip] 学习建议 本试题包含代码分析和算法设计题，建议先理解各算法的核心思想，再对照代码验证。重点关注 n皇后回溯 和 最大连续子数组和 两个经典问题。

正文

一、单选题（每题2分，共10题，20分）

从备选的答案中选出合适的答案，并把答案标号写在答题纸中。

1. 算法必须具备输入、输出和（ ）等四个特性。

   • A. 可行性
   • B. 程序代码
   • C. 确定性
   • D. 无限循环

2. 算法的复杂度包含（ ）两种。

   • A. 空间复杂度和时间复杂度
   • B. 最好复杂度和最坏复杂度
   • C. 平均复杂度和最坏复杂度
   • D. 最低复杂度和最高复杂度

3. 下列关于时间复杂度的说法中，一般认为哪个复杂度最高的是（ ）。

   • A. O(logn)
   • B. O(n²)
   • C. O(n!)
   • D. O(n)

4. 斐波那契数列的递归实现时间复杂度是（ ）。

   • A. O(n)
   • B. O(2ⁿ)
   • C. O(logn)
   • D. O(nlogn)

5. 在解决一个问题时，可以将问题划分成 k 个子问题，（ ）。

   • A. 分治策略
   • B. 贪心策略
   • C. 动态规划策略
   • D. 回溯策略

6. 哪些是图问题的优化算法可以在多项式时间实现（ ）。

   • A. 最大流最小割算法
   • B. 分支限界算法
   • C. 贪心算法
   • D. 广度优先算法

7. 以下关于回溯法的描述中，不正确的是（ ）。

   • A. 回溯法一般用深度优先策略搜索解空间
   • B. 回溯法适用于求解组合数较大的问题
   • C. 回溯法的时间复杂度一般为 O(n!)
   • D. 回溯法在问题的解空间中按深度优先搜索

8. 有一个集合有 n 个元素，如果进行所有的子集的搜索，则当 n=10 时，最多搜索到的子集树的第（ ）层。

   • A. 3
   • B. 5
   • C. 7
   • D. 1

9. 分治法通常基于（ ）策略。

   • A. 递归
   • B. 迭代
   • C. 贪心
   • D. 动态规划

10. 设有一个递归算法 int f(int n) { if(n<=1) return 1; else return f(n-1)+f(n-2); }，计算 f(5) 需要调用（ ）次。

    • A. 5
    • B. 10
    • C. 15
    • D. 以上都不对

参考答案：

题号	1	2	3	4	5	6	7	8	9	10
答案	C	A	C	B	A	B	B	B	A	A

[!warning] 易错点 第4题：斐波那契递归实现的时间复杂度是 O(2ⁿ) 而非 O(n)。递归树是二叉树结构，每层展开2个分支，深度为 n，因此总调用次数为指数级。第10题 f(5) 的递归调用次数为 15 次。

[!tip] 答题技巧 算法四要素：有穷性、确定性、可行性、输入输出。复杂度从低到高排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)。

---

二、简答题（每题5分，共6题，30分）

要求：200字以内，不需配代码，不要配图。

1. 中国剩余定理问题（10分）

有一堆苹果，3个3个地数，最后余2个；5个5个地数，最后余3个；7个7个地数，最后余2个。这堆苹果至少有多少个？

参考答案：

这是典型的中国剩余定理（孙子定理）问题。

设苹果数为 x，则：

• x ≡ 2 (mod 3)
• x ≡ 3 (mod 5)
• x ≡ 2 (mod 7)

由条件1和条件3：x ≡ 2 (mod 3) 且 x ≡ 2 (mod 7)，因为 gcd(3,7)=1，所以 x ≡ 2 (mod 21)。

即 x = 21k + 2，代入条件2：21k + 2 ≡ 3 (mod 5) → k ≡ 1 (mod 5)

最小正整数解：k = 1，x = 21×1 + 2 = 23。

[!note] 教学提示 中国剩余定理的关键在于逐步合并同余方程。先找两个模数的最小公倍数，将两个条件合并为一个，再与第三个合并。

2. 晋级赛问题

N人晋级赛，每人每轮淘汰一名对手。编号为1~N人进行一轮比赛，下一轮的比赛选手的编号规律是：1和N比赛，2和N-1比赛，3和N-2比赛，……。问晋级比赛的轮次和比赛场次。

参考答案：

• 每轮比赛场次为 floor(N/2)，晋级人数为 ceil(N/2)
• 配对规则：第 i 号与第 (N+1-i) 号对阵（对称配对）
• 总比赛场次 = N - 1（每场淘汰1人）
• 轮次 = ceil(log₂N)

3. 贪心算法框架

贪心算法的框架是什么？

参考答案：

贪心算法基本框架：

1. 从问题的初始解出发
2. 循环执行：从候选解集中选取当前最优的候选解
3. 若加入该候选解后解仍可行，则将其加入当前解
4. 重复直到达到目标或候选集为空

flowchart TD
    A["Start: Empty Solution"] --> B{"Candidate Set Empty?"}
    B -->|"No"| C["Select Best Candidate"]
    C --> D{"Solution Still Valid?"}
    D -->|"Yes"| E["Add to Solution"]
    E --> B
    D -->|"No"| F["Discard Candidate"]
    F --> B
    B -->|"Yes"| G["Return Solution"]

[!note] 教学提示 贪心法的核心性质：贪心选择性质（局部最优导致全局最优）和最优子结构。并非所有问题都适用贪心法，如0-1背包问题用贪心法得不到最优解。

4. 回溯法基本思想

回溯法的基本思想是什么？

参考答案：

1. 解空间：定义问题的解空间树（子集树或排列树）
2. 深度优先搜索：从根节点出发，按DFS策略搜索解空间
3. 剪枝函数：用约束函数和限界函数剪去不可能产生最优解的子树
4. 回溯：当搜索到某节点不满足约束时，回退到上一个节点，尝试其他分支

flowchart TD
    A["Root Node"] --> B["Expand Node"]
    B --> C{"Constraint Satisfied?"}
    C -->|"Yes"| D{"Leaf Node?"}
    D -->|"Yes"| E["Record Solution"]
    D -->|"No"| F["Go Deeper"]
    F --> B
    C -->|"No"| G["Prune & Backtrack"]
    G --> H{"More Branches?"}
    H -->|"Yes"| B
    H -->|"No"| I["Return to Parent"]

5. 候诊椅问题

在某医院的大厅，100个座位的候诊椅排成一排。第一个来的人选择任意一个座位坐下；后来的人要么坐在空位上，要么坐在已坐有人的旁边。当两边都有人时，这个人要坐在这两人的中间。求第100个人最多可以坐几次空位。

参考答案：

这是一个经典的递推/概率问题。

分析表明，第100个人最多可以坐到 1个空位。

6. 贪心、分治、动态规划比较

请简要描述贪心算法、分治法、动态规划法的基本思想及异同。

参考答案：

特性	贪心法	分治法	动态规划
核心思想	局部最优→全局最优	分解→递归→合并	子问题重叠→表格存储
子问题	不回溯	独立不重叠	重叠子问题
适用条件	贪心选择性质	可分解可合并	最优子结构+重叠子问题

flowchart LR
    subgraph Greedy["Greedy"]
        G1["Local Optimal"] --> G2["Global Optimal"]
    end
    subgraph Divide["Divide & Conquer"]
        D1["Divide"] --> D2["Recurse"]
        D2 --> D3["Merge"]
    end
    subgraph DP["Dynamic Programming"]
        P1["Subproblems"] --> P2["Table Lookup"]
        P2 --> P3["Optimal Solution"]
    end

---

三、代码分析题（每题8分，共3题，24分）

要求：300字以内。

1. n皇后问题代码分析

阅读以下 n 后问题的分析代码，指出其算法策略：

int COL[20], MAIN_DIAG[40], COUNTER_DIAG[40];
int n, COUNT;

int check(int t) {
    int i, j;
    i = t; j = COL[t];
    while (i > 0) {
        if (COL[i] == j || (COL[i]-j)==i-t || (j-COL[i])==i-t)
            return 0;
        i--;
    }
    return 1;
}

void backtrack(int t) {
    int i;
    if (t > n) {
        for (i = 1; i <= n; i++) printf("%d ", COL[i]);
        printf("\n"); COUNT++;
    } else {
        for (i = 1; i <= n; i++) {
            COL[t] = i;
            if (check(t)) backtrack(t + 1);
            COL[t] = 0;
        }
    }
}

参考答案：

算法策略：回溯法（深度优先搜索 + 剪枝）

• COL[i] 记录第 i 行皇后所在的列号
• check(t) 检查第 t 行放置皇后是否与前面已放置的皇后冲突（同行、同列、同对角线）
• backtrack(t) 递归地在第 t 行尝试放置皇后，若 t > n 则找到一个解
• 时间复杂度：O(n!)

[!note] 教学提示 n皇后问题是回溯法的经典应用。剪枝函数 check() 是关键——它利用"同一列"和"同对角线"约束大幅减少搜索空间。对角线判断公式：|COL[i]-COL[j]| == |i-j|。

2. 最大连续子数组和

阅读以下代码，判断代码实现了哪个算法分析设计原理：

int MaxSum(int a[], int n) {
    int sum = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (b > 0) b += a[i];
        else b = a[i];
        if (b > sum) sum = b;
    }
    return sum;
}

参考答案：

算法策略：动态规划（Kadane算法）

• 维护当前子数组和 b，若 b > 0 则继续累加，否则从当前元素重新开始
• 状态转移：b[i] = max(a[i], b[i-1] + a[i])
• 时间复杂度：O(n)，空间复杂度：O(1)

[!tip] 关键理解 这是动态规划的经典应用。核心思想：如果前面的子数组和为负数，那么它对后面的结果只会产生负面影响，不如重新开始。这也是"局部最优→全局最优"的体现。

3. max2函数分析

已知 max 函数，求 4 个数 a、b、c、d 中分别相邻两数的最大数，以 max 函数为基本对象，讨论 max2 函数的求解过程，写出 max2 的函数原型（C语言格式），并分析 max2 函数的时间复杂度和空间复杂度。

参考答案：

void max2(int a, int b, int c, int d,
          int *max1, int *max2, int *min1, int *min2);

求解过程：

1. 比较 a 和 b → max1=max(a,b), min1=min(a,b)
2. 比较 c 和 d → max2=max(c,d), min2=min(c,d)
3. 从 {max1, max2} 中选较大者为总最大值

• 时间复杂度：O(1)（最多3次比较）
• 空间复杂度：O(1)

---

四、算法设计与编程题（每题13分，共2题，26分）

1. 分治法求最大两个数和最小两个数

利用分治算法求一组数据中最大的两个数和最小的两个数。

参考答案：

算法策略：分治法 — 将数组分为两半，递归地在每半中找最大/最小的两个数，然后合并。

// 分治法求最大两个数和最小两个数
void findMaxMin(int a[], int l, int r,
                int *max1, int *max2, int *min1, int *min2) {
    if (l == r) {
        *max1 = *min1 = a[l];
        *max2 = INT_MIN; *min2 = INT_MAX;
        return;
    }
    if (r - l == 1) { // 基本情况：两个元素
        if (a[l] > a[r]) {
            *max1 = a[l]; *max2 = a[r];
            *min1 = a[r]; *min2 = a[l];
        } else {
            *max1 = a[r]; *max2 = a[l];
            *min1 = a[l]; *min2 = a[r];
        }
        return;
    }
    // 分治：递归处理左右两半
    int mid = (l + r) / 2;
    int lm1, lm2, rm1, rm2, ln1, ln2, rn1, rn2;
    findMaxMin(a, l, mid, &lm1, &lm2, &ln1, &ln2);
    findMaxMin(a, mid+1, r, &rm1, &rm2, &rn1, &rn2);
    // 合并：从4个候选中选最大2个和最小2个
    // ...（合并逻辑）
}

时间复杂度：T(n) = 2T(n/2) + O(1) = O(n)

flowchart TD
    A["Array: a[l..r]"] --> B{"r-l <= 1?"}
    B -->|"Yes"| C["Direct Compare"]
    B -->|"No"| D["Divide: mid = (l+r)/2"]
    D --> E["findMaxMin(l, mid)"]
    D --> F["findMaxMin(mid+1, r)"]
    E --> G["Merge: Select Top 2 Max & Min"]
    F --> G

[!note] 教学提示 分治法的关键是分解、递归求解、合并三步。本题的合并步骤需要从4个候选值中选出最大的两个和最小的两个，最多需要6次比较。

2. 方阵最大路径和（动态规划）

在一个 n×n 的方阵中，填入 1, 2, 3... n² 个数字。方阵最下方有一人，此人走完 n 个方格后必须在最下方出来。任意时刻，每个人走过一方格，必须走到此方格的8个方向之一继续走。输入为 n，找出使所有数相加之和为最大的路径。

参考答案：

算法策略：动态规划 — 从最后一行向上递推，每个格子的最大路径和 = 自身值 + 下方三格中的最大值。

int maxPathSum(int n, int grid[n][n]) {
    int dp[n][n];
    for (int j = 0; j < n; j++)
        dp[n-1][j] = grid[n-1][j];  // 初始化最后一行
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = grid[i][j];
            int maxDown = dp[i+1][j];           // 正下方
            if (j > 0 && dp[i+1][j-1] > maxDown)
                maxDown = dp[i+1][j-1];         // 左下方
            if (j < n-1 && dp[i+1][j+1] > maxDown)
                maxDown = dp[i+1][j+1];         // 右下方
            dp[i][j] += maxDown;
        }
    }
    int result = dp[0][0];
    for (int j = 1; j < n; j++)
        if (dp[0][0+j] > result) result = dp[0][j];
    return result;
}

时间复杂度：O(n²)，空间复杂度：O(n²)

flowchart TD
    A["Grid n x n"] --> B["Initialize Bottom Row"]
    B --> C["For i = n-2 downto 0"]
    C --> D["dp[i][j] = grid[i][j] + max(down-left, down, down-right)"]
    D --> E["Answer = max(dp[0][0..n-1])"]

[!tip] 关键理解 动态规划的状态定义：dp[i][j] 表示从第 i 行第 j 列出发到最下方的最大路径和。状态转移方程：dp[i][j] = grid[i][j] + max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])。这是典型的"自底向上"递推。

---

关联笔记

• 算法设计与分析/试题册/试题2
• 算法设计与分析/试题册/试题3
• 算法设计与分析/试题册/试题4
• 算法设计与分析/试题册/试题5