📚 A Comprehensive Guide to Computer Algorithm Typical Questions and Problem-Solving Methods | 计算机算法典型题型与解题方法解析
Algorithms are the heart of computer science, and exam questions often test your ability to analyse, design, and optimise solutions. This guide examines the most common algorithm question types and provides clear, step-by-step problem-solving strategies.
算法是计算机科学的核心，考试题目通常考查你分析、设计和优化解决方案的能力。本指南将剖析最常见的算法题型，并提供清晰、逐步的解题策略。
1. Understanding the Question Types | 理解题型分类
Exam questions generally fall into several broad categories: time complexity analysis, sorting and searching, recursion and divide-and-conquer, greedy algorithms, dynamic programming, graph algorithms, and string processing. Each type requires a distinct mindset.
考试题目通常分为几大类：时间复杂度分析、排序与查找、递归与分治、贪心算法、动态规划、图算法和字符串处理。每种类型都需要不同的思维方式。
Before attempting a solution, always identify which category the problem belongs to. This guides your choice of approach and helps you avoid wasting time on false starts.
在动手解题之前，务必先判断题目属于哪个类别。这将引导你选择合适的方法，避免在错误的思路上浪费时间。
| Question Type | Typical Signals | Core Technique |
| Complexity analysis | “What is the running time?” | Count operations, use Big-O notation |
| Sorting/searching | “Arrange”, “find an element” | Merge sort, binary search |
| Dynamic programming | “Optimal value”, “number of ways” | State definition, recurrence relation |
| Graph | “Shortest path”, “connected components” | BFS, DFS, Dijkstra |
2. Time Complexity Analysis | 时间复杂度分析
Most algorithm questions begin with complexity analysis. The key is to identify the number of times the basic operation is executed as a function of input size n.
大多数算法题都会先从复杂度分析入手。关键在于确定基本操作随输入规模 n 的变化而执行的次数。
For a single loop that runs from 1 to n, the basic operation executes n times, giving O(n). For a nested loop, multiply the bounds: two nested loops each running n times produce O(n²).
对于一个从 1 运行到 n 的单层循环，基本操作执行 n 次，即 O(n)。对于嵌套循环，将各层循环次数相乘：两层各运行 n 次的嵌套循环产生 O(n²)。
T(n) = a·T(n/b) + f(n) → Master theorem is often used
When a problem uses divide-and-conquer, the recurrence T(n) = 2T(n/2) + n appears frequently. By the Master theorem this is O(n log n), the same complexity as merge sort.
当问题使用分治法时，经常出现递推关系 T(n) = 2T(n/2) + n。根据主定理，其复杂度为 O(n log n)，与归并排序相同。
3. Sorting as a Building Block | 排序作为基础工具
Sorting questions often ask you to compare algorithms, trace through a specific pass, or use sorting as a preprocessing step. You should be able to trace selection sort, insertion sort, merge sort, and quick sort.
排序题通常会要求你比较不同算法、跟踪某一次排序过程，或者将排序作为预处理步骤。你需要能够手动跟踪选择排序、插入排序、归并排序和快速排序。
Consider the array [5, 2, 9, 1]. After one pass of selection sort, the smallest element 1 is swapped with 5, giving [1, 2, 9, 5]. After the second pass, 2 is already in place, and the process continues.
考虑数组 [5, 2, 9, 1]。经过一趟选择排序，最小元素 1 与 5 交换，得到 [1, 2, 9, 5]。第二趟之后，2 已在正确位置，过程继续。
A common trap is confusing stable and unstable sorts. Stable sorting preserves the relative order of equal elements. Merge sort is stable, but quick sort is not necessarily stable. Always check the question’s requirement before choosing an algorithm.
一个常见的陷阱是混淆稳定排序和不稳定排序。稳定排序会保留相等元素的相对顺序。归并排序是稳定的，但快速排序不一定稳定。在选择算法前，务必检查题目要求。
4. Binary Search and Its Variants | 二分查找及其变体
Binary search is one of the most tested algorithmic ideas. It works on a sorted array by repeatedly halving the search space. The basic implementation compares the target with the middle element and discards half of the array each iteration.
二分查找是考查最多的算法思想之一。它针对有序数组，通过反复将搜索空间减半来进行。基础实现将目标与中间元素比较，每次迭代舍弃一半数组。
mid = low + (high − low) ÷ 2
Use this formula instead of (low + high) ÷ 2 to avoid integer overflow. After comparing, if the target is smaller, set high = mid − 1; otherwise set low = mid + 1.
应使用该公式而不用 (low + high) ÷ 2，以避免整数溢出。比较后，若目标更小，则令 high = mid − 1；否则令 low = mid + 1。
Variants include finding the first or last occurrence of a value, and searching in a rotated sorted array. For rotated arrays, compare the middle element with the left boundary to determine which half is sorted, then decide the search range.
变体包括查找某个值的第一次或最后一次出现，以及在旋转有序数组中查找。对于旋转数组，将中间元素与左边界比较，判断哪一半是有序的，再决定搜索区间。
5. Recursion and Divide-and-Conquer | 递归与分治
Recursion is a method where a function calls itself on smaller subproblems. Divide-and-conquer follows three steps: divide, conquer, and combine. Typical examples are merge sort, quick sort, and finding the maximum subarray sum.
递归是一种函数在更小的子问题上调用自身的方法。分治法遵循三个步骤：分解、解决、合并。典型例子是归并排序、快速排序和寻找最大子数组和。
To solve a recursion-based problem, first write the base case. Then define the recursive step by assuming the function already works for smaller inputs. Finally, combine the results of subproblems.
要解决递归问题，首先写出基本情况。然后假设函数已经能处理更小的输入，并据此定义递归步骤。最后合并子问题的结果。
For the maximum subarray sum problem, the divide-and-conquer approach splits the array in half. The answer is either entirely in the left half, entirely in the right half, or crosses the midpoint. The crossing case requires scanning outward from the middle to compute the best left and right sums.
对于最大子数组和问题，分治方法将数组对半分开。答案要么完全在左半部分，要么完全在右半部分，要么跨越中点。跨越中点的情况需要从中点向外扫描，计算最佳左半和右半之和。
6. Greedy Algorithms | 贪心算法
Greedy algorithms make the locally optimal choice at each step, hoping to reach a globally optimal solution. Classic exam questions include the coin change problem, activity selection, and Huffman coding.
贪心算法在每一步做出局部最优选择，期望达到全局最优解。经典考题包括找零钱问题、活动选择和哈夫曼编码。
For activity selection, sort activities by finish time. Then greedily pick the activity that finishes earliest and does not conflict with the previously chosen one. This guarantees the maximum number of activities.
对于活动选择问题，先按结束时间对活动排序。然后贪心地选择结束最早且与已选活动不冲突的活动。这能保证选择到最多数量的活动。
However, greedy does not always work. If a question asks for a certain combination of values, test whether a counterexample exists. The coin change problem with denominations 1, 5, and 11 is a classic case where greedy can fail for a target amount such as 15, because greedy would choose 11 + 1 + 1 + 1 + 1, while the optimal solution is 5 + 5 + 5.
然而，贪心并非总是有效。如果题目要求某种数值组合，请测试是否存在反例。面值为 1、5 和 11 的找零问题是一个经典反例：当目标金额为 15 时，贪心会选 11 + 1 + 1 + 1 + 1，而最优解是 5 + 5 + 5。
7. Dynamic Programming Fundamentals | 动态规划基础
Dynamic programming (DP) is used when a problem has overlapping subproblems and an optimal substructure. Instead of recomputing subproblems, store their results in a table to avoid redundant work.
当问题具有重叠子问题和最优子结构时，使用动态规划。与其重复计算子问题，不如将结果存入表格以避免冗余工作。
The standard method consists of four steps: define the state, write the recurrence, set the initial values, and determine the answer. For example, the Fibonacci sequence can be computed with dp[n] = dp[n−1] + dp[n−2].
标准方法包含四个步骤：定义状态、写出递推关系、设定初始值、确定答案。例如，斐波那契数列可以用 dp[n] = dp[n−1] + dp[n−2] 计算。
For the 0/1 knapsack problem, define dp[i][w] as the maximum value obtainable using the first i items with capacity w. The recurrence is:
对于 0/1 背包问题，定义 dp[i][w] 为使用前 i 件物品且容量为 w 时能获得的最大价值。递推关系为：
dp[i][w] = max(dp[i−1][w], dp[i−1][w − weightᵢ] + valueᵢ)
The answer is dp[n][capacity]. You must be careful not to simply copy formulas; always verify the index range and whether the item can actually fit into the remaining capacity.
答案为 dp[n][capacity]。务必小心，不能简单照搬公式；一定要检查下标范围，并确认该物品是否真的能放入剩余容量。
8. Graph Traversal: BFS and DFS | 图的遍历：广度优先与深度优先
Graph traversal is a favourite exam topic. Depth-first search (DFS) uses a stack or recursion, while breadth-first search (BFS) uses a queue. Both have time complexity O(V + E) for an adjacency-list representation.
图的遍历是考试中的热门考点。深度优先搜索使用栈或递归，而广度优先搜索使用队列。使用邻接表表示时，两者的时间复杂度均为 O(V + E)。
DFS is useful for detecting cycles, finding connected components, and performing topological sorting. When doing DFS, mark each node as visited when you first discover it, and process it after returning from all neighbours for post-order results.
DFS 可用于检测环、寻找连通分量和执行拓扑排序。进行 DFS 时，要在首次发现节点时将其标记为已访问；对于后序结果，可在从所有邻居返回后再处理该节点。
BFS is ideal for finding the shortest path in an unweighted graph. The first time a node is reached via BFS, the path length from the source is the shortest. Use a distance array initialised to infinity, and set distance[source] = 0.
BFS 适用于在无权图中寻找最短路径。通过 BFS 首次到达某个节点时，从源点到该节点的路径长度即为最短。使用初始化为无穷大的距离数组，并令 distance[source] = 0。
9. Shortest Path and Minimum Spanning Tree | 最短路径与最小生成树
Dijkstra’s algorithm solves the single-source shortest path problem for non-negative edge weights. It repeatedly selects the unvisited vertex with the smallest known distance and relaxes its outgoing edges.
迪杰斯特拉算法解决非负边权下的单源最短路径问题。它反复选择未访问顶点中已知距离最小的顶点，并松弛其出边。
Relaxation means checking whether going through the current vertex offers a shorter path:
松弛意味着检查经过当前顶点是否能提供更短路径：
if dist[u] + w(u, v) < dist[v], then dist[v] = dist[u] + w(u, v)
Prim’s and Kruskal’s algorithms build a minimum spanning tree. Kruskal’s algorithm sorts all edges by weight and adds an edge only if it does not create a cycle, using a union-find data structure. Prim’s algorithm grows a tree from a starting vertex by always adding the cheapest edge that connects a new vertex.
普里姆算法和克鲁斯卡尔算法用于构建最小生成树。克鲁斯卡尔算法按权重对所有边排序，并仅当该边不会产生环时才加入，需借助并查集数据结构。普里姆算法则从一个起始顶点开始扩展树，始终加入连接新顶点的最便宜边。
10. String Processing and Pattern Matching | 字符串处理与模式匹配
String questions often ask for substring counting, palindrome checking, or pattern matching. The naive pattern matching approach compares the pattern with every possible starting position, giving O(n·m) worst-case time.
字符串题目通常要求统计子串、判断回文或进行模式匹配。朴素的模式匹配将模式与每个可能的起始位置比较，最坏情况时间复杂度为 O(n·m)。
KMP (Knuth-Morris-Pratt) algorithm improves this by preprocessing the pattern to build an LPS array. The LPS array stores the length of the longest proper prefix that is also a suffix for each prefix of the pattern.
KMP 算法通过预处理模式来构建 LPS 数组，从而改进效率。LPS 数组存储模式每个前缀的最长相等前后缀长度，该前缀必须是真正的前缀（不能是整体）。
When a mismatch occurs after matching j characters, instead of restarting at position 1, the pattern shifts by j − lps[j−1] positions. This avoids comparing characters that have already been matched, reducing the worst-case complexity to O(n + m).
当匹配 j 个字符后发生失配，模式不是回到位置 1 重新开始，而是移动 j − lps[j−1] 个位置。这样可以避免比较已经匹配过的字符，使最坏情况复杂度降为 O(n + m)。
11. Common Pitfalls and Exam Strategies | 常见陷阱与应试策略
One common pitfall is choosing a recursive solution without considering stack depth. A very deep recursion can cause a stack overflow in a programming implementation, but in written exams you should still mention the extra O(n) space for the recursive call stack.
一个常见陷阱是选择递归方案而不考虑栈深度。非常深的递归在编程实现中可能导致栈溢出；但在笔试中，你仍应说明递归调用栈需要额外的 O(n) 空间。
Another pitfall is forgetting to handle empty inputs or arrays of size 1. Many algorithm questions include a base case check that must be written explicitly. Always test your logic on the smallest possible input.
另一个陷阱是忘记处理空输入或大小为 1 的数组。许多算法题包含必须显式写出的基本情况检查。务必用最小的可能输入来测试你的逻辑。
Finally, pay attention to what the question wants you to output: the algorithm itself, the complexity, the data structure, or a trace. Read the question twice and underline keywords such as “stable”, “in-place”, “worst-case”, and “optimal”.
最后，注意题目到底要求输出什么：是算法本身、复杂度、数据结构、还是过程追踪。请将题目读两遍，并圈出如“稳定”“原地”“最坏情况”和“最优”等关键词。
12. Step-by-Step Framework for Tackling Algorithm Problems | 算法解题分步框架
Use this framework when facing any algorithm question. First, restate the problem in your own words. Second, identify the input size and target complexity. Third, propose a brute-force solution to understand the structure. Fourth, optimise using the appropriate technique.
面对任何算法题时，可以使用以下框架。首先，用自己的话复述问题。其次，确认输入规模和目标复杂度。第三，提出暴力解法以理解问题结构。第四，使用合适的技术进行优化。
Fifth, verify your solution with a small manual example. Sixth, consider edge cases such as large values, duplicates, negative numbers, or disconnected graphs. Finally, write down the algorithm steps in clear, logical order and state the time and space complexity.
第五，用小规模手工示例验证你的解法。第六，考虑边界情况，如大数值、重复元素、负数或不连通图。最后，以清晰、逻辑清晰的顺序写出算法步骤，并说明时间与空间复杂度。
For example, if a question asks for the number of ways to climb n stairs taking 1 or 2 steps at a time, the brute-force recursion is f(n) = f(n−1) + f(n−2). This overlaps heavily, so the optimal solution is DP with a single array or even two variables, giving O(n) time and O(1) space.
例如，如果题目要求每次走 1 级或 2 级台阶，计算爬上 n 级台阶的方法数，暴力递归为 f(n) = f(n−1) + f(n−2)。该递归重叠严重，因此最优解法是使用动态规划，只需一个数组甚至两个变量，时间复杂度为 O(n)，空间复杂度为 O(1)。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导