311 lines
8.9 KiB
Markdown
311 lines
8.9 KiB
Markdown
---
|
||
tags:
|
||
- 算法设计与分析
|
||
- 试题
|
||
- 武汉科技大学
|
||
create time: 2026-06-10 10:00
|
||
---
|
||
|
||
# 试题 2 — 武汉科技大学《算法设计与分析》
|
||
|
||
## 概述
|
||
|
||
- **课程**：算法设计与分析（A）第二学期
|
||
- **学校**：武汉科技大学
|
||
- **题型**：选择题、简答题、程序填空题、算法设计与编程题
|
||
- **知识点**：NP问题理论、辗转相除法、排序算法、回溯法、贪心法、图搜索
|
||
|
||
> [!tip] 学习建议
|
||
> 本试题包含 NP 问题理论和程序填空题，建议重点掌握 **NP/NP-C/NP-hard 的定义与区别**，以及 **回溯法框架代码** 的理解。
|
||
|
||
## 正文
|
||
|
||
### 一、选择题（每题2分，共15题，30分）
|
||
|
||
**从备选的答案中选出合适的答案，并把答案标号写在答题纸中。**
|
||
|
||
1. 以下属于算法基本思想的是（ ）。
|
||
- A. 递归分治思想的基本思路就是自顶向下，逐步求精
|
||
- B. 用自然语言描述算法，优点是通俗易懂，缺点是容易有歧义
|
||
- C. 穷举算法能够找到问题的全局最优解
|
||
- D. 三种基本控制结构是顺序、选择、循环
|
||
|
||
2. 下列算法时间复杂度中，哪个不是常数复杂度（ ）。
|
||
- A. O(1)
|
||
- B. O(logn)
|
||
- C. O(n)
|
||
- D. O(nlogn)
|
||
|
||
3. 下列排序算法中时间复杂度不是 O(n²) 的是（ ）。
|
||
- A. 直接插入排序
|
||
- B. 冒泡排序
|
||
- C. 简单选择排序
|
||
- D. 快速排序
|
||
|
||
4. n个人同时站在一个大水龙头前面打水，以下说法不正确的是（ ）。
|
||
- A. 让水桶小的人先打水，可以使得每个人等待的时间总和最小
|
||
- B. 让水桶大的人先打水，可以使得每个人等待的时间总和最小
|
||
- C. 让水桶小的人先打水，可以反映出后来先打水的人的等待时间
|
||
- D. 无论怎样安排打水顺序，所有人等待时间总和都是一样
|
||
|
||
5. 设 n 为按递增排列的有序数列，折半查找的时间复杂度为（ ）。
|
||
- A. O(logn)
|
||
- B. O(n)
|
||
- C. O(nlogn)
|
||
- D. O(n²)
|
||
|
||
6. 小猴子有100个苹果，第一天拿走一半多一个，以后每天拿走剩余中一半多一个，10天后还剩多少个？（ ）
|
||
- A. 766
|
||
- B. 382
|
||
- C. 190
|
||
- D. 都不对
|
||
|
||
7. `int f(int n) { if(n<=1) return 1; else return f(n-1)+f(n-2); }` 计算 f(5) 的值是（ ）。
|
||
- A. 5
|
||
- B. 8
|
||
- C. 10
|
||
- D. 以上都不对
|
||
|
||
8. 以下方法中，不属于分治法基本要素的是（ ）。
|
||
- A. 贪心法
|
||
- B. 递归求解法
|
||
- C. 分治法
|
||
- D. 逐步求精法
|
||
|
||
9. 如果一个结点不再进一步扩展并且其所有的儿子结点都已经产生出来，则该结点应该标记为（ ）。
|
||
- A. 活结点
|
||
- B. 扩展结点
|
||
- C. 死结点
|
||
- D. 以上都不对
|
||
|
||
10. 用回溯法求解一个问题时，首先需要定义问题的（ ）。
|
||
- A. 递归空间
|
||
- B. 线性空间
|
||
- C. 二叉树
|
||
- D. 解空间
|
||
|
||
11. 图的广度优先搜索类似于树的（ ）遍历。
|
||
- A. 先序遍历
|
||
- B. 中序遍历
|
||
- C. 后序遍历
|
||
- D. 层次遍历
|
||
|
||
12. 合并排序属于（ ）。
|
||
- A. 归并排序
|
||
- B. 交换排序
|
||
- C. 选择排序
|
||
- D. 插入排序
|
||
|
||
13. 下列不是分治法基本步骤的是（ ）。
|
||
- A. 分解
|
||
- B. 合并
|
||
- C. 回溯
|
||
- D. 求解子问题
|
||
|
||
14. 回溯法区别于蛮力穷举搜索的主要特点是（ ）。
|
||
- A. 有剪枝函数
|
||
- B. 不需要剪枝
|
||
- C. 只搜索部分解空间
|
||
- D. 搜索全部解空间
|
||
|
||
15. 假设1000年有一只寿命为1年的虫子，每年交配产生两对小虫，每对第二年成熟并交配……（ ）年后虫子有多少只？
|
||
- A. 96
|
||
- B. 97
|
||
- C. 95
|
||
- D. 63
|
||
|
||
**参考答案：**
|
||
|
||
| 题号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|
||
|------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||
| 答案 | D | C | D | B | A | C | B | A | C | D | D | D | C | A | B |
|
||
|
||
> [!warning] 易错点
|
||
> 第2题：O(1) 是常数复杂度，O(logn)、O(n)、O(nlogn) 都不是。第3题：快速排序平均时间复杂度为 O(nlogn)，不是 O(n²)。第6题：递推计算后剩余0个，选C"都不对"。
|
||
|
||
---
|
||
|
||
### 二、简答题（每题10分，共2题，20分）
|
||
|
||
**要求：写出详细过程，可配图。**
|
||
|
||
#### 1. NP问题、NP-C问题、NP-hard问题
|
||
|
||
回答什么是NP问题、NP-C问题、NP-hard问题。
|
||
|
||
**参考答案：**
|
||
|
||
- **P类问题**：可以在多项式时间内被确定性图灵机解决的判定问题
|
||
- **NP类问题**：可以在多项式时间内被非确定性图灵机解决的判定问题，即解可以在多项式时间内被**验证**
|
||
- **NP-C（NP完全）问题**：既是NP类问题，又是NP-hard问题的问题
|
||
- **NP-hard问题**：至少和NP-C问题一样难的问题，不一定在NP中
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
subgraph P["P Class"]
|
||
P1["Polynomial Time Solvable"]
|
||
end
|
||
subgraph NP["NP Class"]
|
||
NP1["Polynomial Time Verifiable"]
|
||
NPC["NP-Complete"]
|
||
end
|
||
subgraph NPHard["NP-hard"]
|
||
NH1["At Least as Hard as NPC"]
|
||
end
|
||
P -->|"P ⊆ NP"| NP
|
||
NPC -->|"NPC = NP ∩ NP-hard"| NPHard
|
||
NPC --> NP
|
||
```
|
||
|
||
> [!question] 思考
|
||
> P vs NP 问题至今未解——如果你能证明 P=NP 或 P≠NP，那你就是百万美元克莱数学研究所千禧年大奖得主！
|
||
|
||
#### 2. 辗转相除法
|
||
|
||
简述求2个整数的最大公约数的辗转相除法。用此算法求正整数 2146 和 8100 的最大公约数。
|
||
|
||
**参考答案：**
|
||
|
||
原理：gcd(a,b) = gcd(b, a mod b)，直到余数为0。
|
||
|
||
```
|
||
8100 = 2146 × 3 + 1662
|
||
2146 = 1662 × 1 + 484
|
||
1662 = 484 × 3 + 210
|
||
484 = 210 × 2 + 64
|
||
210 = 64 × 3 + 18
|
||
64 = 18 × 3 + 10
|
||
18 = 10 × 1 + 8
|
||
10 = 8 × 1 + 2
|
||
8 = 2 × 4 + 0
|
||
```
|
||
|
||
**gcd(2146, 8100) = 2**，时间复杂度 O(log(min(a,b)))
|
||
|
||
> [!tip] 答题技巧
|
||
> 辗转相除法的步骤要写完整，每一步都要写出被除数 = 除数 × 商 + 余数 的形式，直到余数为0。最后一个非零余数就是最大公约数。
|
||
|
||
---
|
||
|
||
### 三、程序填空题（每空2分，2×5=10分）
|
||
|
||
#### 1. 二分查找
|
||
|
||
```c
|
||
int Binary_Search(int *a, int low, int high, int key) {
|
||
int mid;
|
||
if (low > high) return (-1);
|
||
mid = (low + high) / 2;
|
||
if (a[mid] == key) return mid;
|
||
else if (a[mid] > key)
|
||
return Binary_Search(a, low, mid - 1, key);
|
||
else
|
||
return Binary_Search(a, (1)___, high, key);
|
||
}
|
||
```
|
||
|
||
**(1)** `low = mid + 1`
|
||
|
||
#### 2. 组合问题
|
||
|
||
```c
|
||
int a[20];
|
||
void main() {
|
||
int n=4, r=3;
|
||
a[0]=r;
|
||
(2)___; // comb(n, r)
|
||
}
|
||
void comb(int m, int r) {
|
||
int i, j;
|
||
for (i=m; i>=(3)___; i--) { // r
|
||
a[r] = i;
|
||
if (i > r)
|
||
comb((4)___, r-1); // i-1
|
||
else { /* 输出组合 */ }
|
||
}
|
||
}
|
||
```
|
||
|
||
**(2)** `comb(n, r)` **(3)** `r` **(4)** `i - 1`
|
||
|
||
> [!note] 教学提示
|
||
> 组合问题的递归思路：从 m 个数中选 r 个，先固定一个数，再从剩余中选 r-1 个。循环从 m 递减到 r 确保不重复。
|
||
|
||
---
|
||
|
||
### 四、算法设计与编程题（每题15分，共2题，30分）
|
||
|
||
#### 1. 马的遍历问题（回溯法）
|
||
|
||
在 m×n 的棋盘上，马处于某个方格中，每个格只能走一次，设计算法使马不重复地走过所有方格并返回原位。
|
||
|
||
**参考答案：**
|
||
|
||
**算法策略：回溯法**，马从当前位置出发，依次尝试8个方向移动。
|
||
|
||
```c
|
||
int direction[8][2] = {{1,2},{2,1},{2,-1},{1,-2},
|
||
{-1,-2},{-2,-1},{-2,1},{-1,2}};
|
||
int book[100][100] = {0};
|
||
|
||
void dfs(int x, int y, int step) {
|
||
if (step == m * n) { /* 输出结果 */ return; }
|
||
for (int k = 0; k < 8; k++) {
|
||
int tx = x + direction[k][0];
|
||
int ty = y + direction[k][1];
|
||
if (tx>=0 && tx<m && ty>=0 && ty<n && book[tx][ty]==0) {
|
||
book[tx][ty] = 1;
|
||
dfs(tx, ty, step + 1);
|
||
book[tx][ty] = 0; // 回溯
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
**时间复杂度**：O(8^(mn))，实际通过剪枝大幅减少
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["Start Position (x,y)"] --> B["Try 8 Directions"]
|
||
B --> C{"Valid Move?"}
|
||
C -->|"Yes"| D["Mark & Recurse"]
|
||
D --> E{"All Cells Visited?"}
|
||
E -->|"Yes"| F["Found Solution"]
|
||
E -->|"No"| B
|
||
C -->|"No"| G["Backtrack"]
|
||
G --> B
|
||
```
|
||
|
||
#### 2. 活动安排问题（贪心法）
|
||
|
||
有 n 个活动，每个活动有开始时间和结束时间，设计贪心算法选择尽可能多的活动。
|
||
|
||
**参考答案：**
|
||
|
||
**算法策略：贪心法** — 按结束时间排序，每次选结束最早且不冲突的活动。
|
||
|
||
```c
|
||
int selectActivities(int start[], int end[], int n) {
|
||
int count = 1, lastEnd = end[0];
|
||
for (int i = 1; i < n; i++) {
|
||
if (start[i] >= lastEnd) {
|
||
count++;
|
||
lastEnd = end[i];
|
||
}
|
||
}
|
||
return count;
|
||
}
|
||
```
|
||
|
||
**时间复杂度**：O(nlogn)
|
||
|
||
> [!tip] 关键理解
|
||
> 活动安排问题是贪心法的经典应用。贪心策略：**每次选择结束时间最早的活动**，这样可以为后续活动留出最多的时间。这体现了"局部最优→全局最优"的贪心思想。
|
||
|
||
---
|
||
|
||
## 关联笔记
|
||
|
||
- [[算法设计与分析/试题册/试题1]]
|
||
- [[算法设计与分析/试题册/试题3]]
|