9.2 Algorithms 算法概念简答

Scope 本页范围

本页只整理 Chapter 9.2 中可用于简答题的概念、识别与解释：algorithm、identifier table、input/process/output、basic constructs、算法表示方法、stepwise refinement 和 logic。完整 pseudocode、flowchart 绘制及算法编写将在后续代码专项中处理。

1 What is an algorithm?

Algorithm 是：

A solution to a problem expressed as a sequence of defined steps.

关键点：

• It solves a stated problem or completes a task。
• It contains an ordered sequence of unambiguous/defined steps。
• It is independent of a particular programming language until implemented。
• It should eventually be detailed enough to be programmed and tested。

一分题问 “technical term for a sequence of steps that solves a problem”，答案就是 algorithm。

2 Reading and explaining an algorithm

简答题可能给出已有 algorithm，要求解释某些 steps 的 purpose 或找出逻辑问题。回答时不要逐行翻译，而要说明这些步骤共同产生的 effect。

例如几步用于重排 file lines，应写：

The steps ensure that the lines are output in the correct order.

Identifying a logic problem

写两层：

• 先指出哪个 assumption/initial value/condition 在某类 input 下不会成立。
• 再说明它会产生什么 incorrect output。

例：Min 固定初始化为 999，而所有输入均大于 999：

• Min is never updated because no input is smaller than 999。
• The algorithm incorrectly outputs 999 even though 999 was not in the input data。

只写 “Min is wrong” 没有说明原因与后果。

3 Identifiers and meaningful names

Identifier 是程序中用来命名 variable、constant、array、module 等项目的名称。

A meaningful identifier name should：

• Describe the data or purpose, such as CustomerName、ItemCount、DepositPaid。
• Be unambiguous in the problem context。
• Follow a consistent naming convention。

Why meaningful names are good practice

• Make the algorithm/program easier to understand。
• Make testing and debugging easier because the purpose of each value is clear。
• Make future maintenance/modification easier。

A、B、Temp 等名称不一定语法错误，但若无法反映 purpose，就不是 good programming practice。

4 Identifier tables

Identifier table 在 design stage 记录算法所需的数据。常见字段包括：

• Identifier/variable name。
• Data type。
• Description/purpose of the identifier。
• Example value or initial value。
• Constant value。
• Array size/number of elements or string length。
• Scope：local or global。

Choosing a data type from meaning

变量名和 data type 必须同时与 explanation/example 匹配。表示 InStock 的值若为 TRUE/FALSE，应使用 BOOLEAN，而不是 STRING。

Documentation answer pattern [2]

The variables can be documented using an identifier table. In addition to data type, it should record the purpose of each identifier.

5 Input, process and output

算法可按数据流理解：

• Input：data enters the algorithm, e.g. keyboard input or reading from a file/sensor。
• Process：data is calculated, compared, assigned, converted or otherwise changed。
• Output：information leaves the algorithm, e.g. display, print or write to file。

同一 statement 可能涉及不止一种。例如 OUTPUT FirstName & LastName 先 concatenates values，属于 process；再显示结果，属于 output。

6 The three basic constructs

Sequence

Instructions execute in a defined order, one after another。适用于输入、计算、输出等必须按顺序完成的步骤。

Selection

A condition is tested and one of two or more paths/actions is selected。用于根据 mark、state、range 或 user choice 做决定。

Iteration / repetition

A group of steps is repeated a fixed number of times or while/until a condition is met。用于处理 all array elements、repeated inputs 或重复搜索。

Two-mark scenario pattern

The construct is iteration, used to repeat the steps for all 100 input values.

或：

The construct is selection, used to test whether an input value is positive and choose the appropriate action.

第一分 identify construct，第二分必须描述它在题目中的具体 use。

7 Ways to document an algorithm

Structured English

Uses clear natural-language statements arranged in logical order。优点是容易被非程序员理解；缺点是自然语言可能产生 ambiguity，且复杂 control flow 不如标准结构明确。

Flowchart

Uses standard symbols and arrows to show flow of control。适合直观看到 sequence、decisions 和 loops；大型算法可能占用大量空间且修改不方便。

常见概念：

• Oval：start/end。
• Parallelogram：input/output。
• Rectangle：process/assignment。
• Diamond：decision/condition，branches should be labelled。
• Arrows：direction of control flow。

Pseudocode

Uses structured statements similar to programming code but independent of a specific programming language。它比 structured English 更精确，也较容易转成 program；具体 syntax 和编写留到代码专项。

8 Stepwise refinement 逐步求精

Stepwise refinement：

• Starts with a high-level description of the task。
• Increases the level of detail by breaking each step into smaller, more precise steps。
• Repeats this process until the steps can be directly translated into code / the task can be programmed。

Two-mark definition

Stepwise refinement increases the level of detail of an algorithm by breaking tasks into smaller steps, until the steps can be translated directly into program code.

它与 decomposition 有联系，但侧重点不同：decomposition 划分 modules/sub-problems；stepwise refinement 逐层增加 algorithm steps 的实现细节。

9 What a refined description must make explicit

即使本页不要求写完整 algorithm，学生仍需理解 refinement 会逐步明确：

• Required data and initial values。
• Exact order of actions。
• Conditions and alternative paths。
• Repetition count or stopping condition。
• File mode and when files are opened/closed。
• Which data is read, processed, stored or output。
• How an index/counter changes。

粗略描述 “process all values and output the total” 还不能直接编程。Refined description 应说明 total 初始化、如何输入、何时加入 total、重复多少次/何时停止、最后何时输出。

10 Logic statements in algorithm solutions

Logic defines the conditions controlling selection and iteration。A condition should evaluate to BOOLEAN：TRUE or FALSE。

常用关系：equal to、not equal to、greater/less than、inclusive range。多个 conditions 可用 AND、OR、NOT 组合。

• AND：all linked conditions must be TRUE。
• OR：at least one linked condition must be TRUE。
• NOT：reverses a Boolean result。

简答题需说明 condition 如何改变 control flow，而不是只复述符号。例如：

The condition tests whether the element is blank; if it is not blank, the value is written to the file.

11 Algorithm complexity in explanation questions

有时题目不要求 Big-O，而是解释 layout/requirement 为什么让 algorithm 更复杂。寻找 additional work：

• Data must be counted before earlier output can be produced。
• Data may need to be stored temporarily。
• A file may need to be read more than once。
• Extra conditions, loops or passes are required。

例：report 顶部先显示最终 item count，但 count 只有读取全部记录后才知道，则 algorithm 可能要先读一次计算 count，再重新读取输出 details；或把所有 lines 暂存后再输出。

12 Good design practice

除 meaningful identifiers 外，简答题可能接受：

• Consistent indentation and white space。
• Comments explaining non-obvious purpose。
• Consistent keyword/naming style。
• Appropriate local variables and parameters rather than unnecessary globals。
• Documentation such as identifier tables。

回答必须说明 practice 带来的结果，例如 readability、testing、debugging 或 maintenance，而不是只写 “better code”。

13 Exam-answer checklist

• Algorithm definition 是否包含 solution、problem、sequence of defined steps？
• Purpose 题是否说明几步共同实现的 outcome，而非逐行翻译？
• Logic-error 题是否同时写 cause 与 incorrect result？
• Identifier name 是否反映 data/purpose？
• Identifier table 是否能写出 type、purpose、example、scope 等字段？
• Input/process/output 是否按数据流判断，而不是只看 statement 中的一个单词？
• Construct 题是否写明 sequence/selection/iteration 及 scenario use？
• Stepwise refinement 是否写到 increased detail 和 directly programmable？
• Complexity 题是否指出额外 storage、pass、condition 或 processing？
• 是否避免在 “Do not include pseudocode” 的题目中写 pseudocode statements？

---

本页只使用 Chapter 9.2 的概念识别、定义、解释和设计文档类 past-paper evidence。完整 pseudocode、flowchart、algorithm tracing 与编写题将在后续代码专项中单独整理。