📚 Typical Exam Questions Explained | 典型例题详解
This article presents a selection of typical A-Level Computer Science questions from the CIE specification, covering topics such as data structures, algorithms, programming paradigms, databases, logic circuits, computer architecture, and networking. Each section includes a worked example with detailed commentary to help you understand the reasoning required to achieve full marks.
本文精选了 CIE A-Level 计算机科学考试中的典型例题，涵盖数据结构、算法、编程范式、数据库、逻辑电路、计算机体系结构和网络等主题。每个小节都包含一道精讲例题，并配有详细的解析，以帮助你理解获得满分所需的推理过程。
1. Infix to Postfix Conversion Using a Stack | 用栈将中缀表达式转为后缀表达式
Problem: Convert the following infix expression to postfix notation showing the stack contents step by step: A + B * C – D / E. Assume standard operator precedence: *, / have higher precedence than +, -, and operators of equal precedence are left‑associative.
题目：将下列中缀表达式转换为后缀表示，并逐步显示栈内容：A + B * C – D / E。假设标准运算符优先级：*、/ 高于 +、-，相同优先级的运算符遵循左结合规则。
We scan the expression from left to right. Operands are immediately output. For operators, we pop from the stack to the output until the stack is empty or the top operator has lower precedence, then push the current operator. For left‑associative operators, pop equal precedence before pushing. The stack initially empty.
我们从左到右扫描表达式。遇到操作数直接输出。遇到运算符时，将栈中优先级高于或等于（左结合时）当前运算符的运算符弹出并输出，然后将当前运算符压栈。栈初始为空。
| Step | Current Symbol | Stack (top→right) | Output (postfix) |
|---|---|---|---|
| 1 | A | empty | A |
| 2 | + | + | A |
| 3 | B | + | A B |
| 4 | * | + * | A B |
| 5 | C | + * | A B C |
| 6 | – | – | A B C * + |
| 7 | D | – | A B C * + D |
| 8 | / | – / | A B C * + D |
| 9 | E | – / | A B C * + D E |
| 10 | end | empty | A B C * + D E / – |
At step 6, ‘-‘ encounters ‘+’ and ‘*’ in the stack. Since ‘+’ has lower precedence than ‘-‘, only ‘*’ (higher precedence) is popped first, then we compare with ‘+’: precedence equal and left‑associative means pop ‘+’ as well. Then push ‘-‘. The final postfix expression is A B C * + D E / –.
在第 6 步，’-‘ 遇到栈中的 ‘+’ 和 ‘*’。因为 ‘*’ 优先级高于 ‘-‘，先弹出；然后与 ‘+’ 比较，优先级相等且左结合，因此也弹出 ‘+’。最后压入 ‘-‘。最终后缀表达式为 A B C * + D E / –。
2. Recursive Function Execution Trace | 递归函数执行跟踪
Problem: Consider the following recursive function defined in pseudocode:
FUNCTION mystery(n) RETURNS INTEGER
IF n ≤ 1 THEN
RETURN 1
ELSE
RETURN mystery(n-1) + mystery(n-2)
ENDIF
Determine the value returned by mystery(5). Show the recursion tree and state the name of the sequence produced.
题目：考虑下列用伪代码定义的递归函数，求 mystery(5) 的返回值。画出递归树并说明该函数生成的数列名称。
The function computes a well‑known sequence: each call returns the sum of the two previous calls when n > 1. For n=1 or 0 it returns 1. Tracing:
该函数计算一个知名数列：每当 n > 1 时返回前两个调用的和。当 n=1 或 0 时返回 1。跟踪执行如下：
- mystery(5) = mystery(4) + mystery(3)
- mystery(4) = mystery(3) + mystery(2)
- mystery(3) = mystery(2) + mystery(1)
- mystery(2) = mystery(1) + mystery(0) = 1 + 1 = 2
Now we evaluate upwards: mystery(3) = 2 + 1 = 3; mystery(4) = 3 + 2 = 5; mystery(5) = 5 + 3 = 8.
现在从底层向上计算：mystery(3) = 2 + 1 = 3；mystery(4) = 3 + 2 = 5；mystery(5) = 5 + 3 = 8。
This is the Fibonacci sequence with F(1)=1, F(2)=1, but here starting from n=0 returns 1, so the values are: 1,1,2,3,5,8,… Thus mystery(5) returns the 6th Fibonacci number if we count from 0. The sequence is the Fibonacci sequence.
这是斐波那契数列，但此处从 n=0 开始返回 1，因此数列为：1, 1, 2, 3, 5, 8, …。所以 mystery(5) 返回第 6 个斐波那契数（从 0 开始计数）。该数列为 斐波那契数列。
3. Binary Search Tree Insertion and Traversal | 二叉搜索树插入与遍历
Problem: Insert the following values into an initially empty binary search tree (BST) in the given order: 15, 8, 20, 13, 17, 5, 25. Then write the sequence of nodes visited during a post‑order traversal.
题目：按给定顺序将下列值插入一棵初始为空的二叉搜索树（BST）：15, 8, 20, 13, 17, 5, 25。然后写出后序遍历访问节点的顺序。
BST rule: for each node, left subtree contains smaller values, right subtree contains larger values. We insert one by one:
二叉搜索树规则：每个节点的左子树包含小于它的值，右子树包含大于它的值。我们逐个插入：
Insert 15 → root 15. Insert 8 → left of 15. Insert 20 → right of 15. Insert 13 → 13 > 8, so right of 8. Insert 17 → 17 < 20, left of 20. Insert 5 → left of 8. Insert 25 → right of 20.
插入 15 → 根 15。插入 8 → 15 的左孩子。插入 20 → 15 的右孩子。插入 13 → 13 大于 8，放在 8 的右孩子。插入 17 → 17 小于 20，放在 20 的左孩子。插入 5 → 8 的左孩子。插入 25 → 20 的右孩子。
Post‑order traversal visits left subtree, right subtree, then root. Starting from root 15: left subtree (8) → its left (5), its right (13), then 8; right subtree (20) → left (17), right (25), then 20; finally root 15. Sequence: 5, 13, 8, 17, 25, 20, 15.
后序遍历：先左子树，再右子树，最后根。从根 15 开始：左子树 8 → 左孩子 5，右孩子 13，再访问 8；右子树 20 → 左孩子 17，右孩子 25，再访问 20；最后根 15。顺序为：5, 13, 8, 17, 25, 20, 15。
4. Object‑Oriented Programming – Inheritance and Polymorphism | 面向对象编程 – 继承与多态
Problem: A program has a base class Vehicle with a method display() that prints “I am a vehicle”. A derived class Car inherits from Vehicle and overrides display() to print “I am a car”. Another derived class Bike overrides display() to print “I am a bike”. If an array stores objects: [Vehicle(), Car(), Bike(), Car()] and the following code is executed, what will be the output? Explain how polymorphism works here.
FOR EACH v IN vehicles
v.display()
END FOR
题目：程序有一个基类 Vehicle，包含方法 display() 打印 “I am a vehicle”。派生类 Car 继承自 Vehicle 并重写 display() 打印 “I am a car”。另一个派生类 Bike 重写 display() 打印 “I am a bike”。如果数组存储下列对象：[Vehicle(), Car(), Bike(), Car()]，执行上述代码，输出是什么？解释多态如何在此处工作。
Output (each on new line):
输出（每行一个）：
I am a vehicle
I am a car
I am a bike
I am a car
Polymorphism allows a base class reference to behave according to the actual object type at runtime. Even though the array is typed as Vehicle references, when display() is called, the most specific override is invoked thanks to dynamic method dispatch. Thus a Car object calls Car’s display, a Bike object calls Bike’s display, and a plain Vehicle uses its own version.
多态允许基类引用在运行时按照实际对象类型执行行为。尽管数组的元素类型是 Vehicle 引用，调用 display() 时，由于动态方法分派，会调用最具体的重写版本。因此 Car 对象调用 Car 的 display，Bike 对象调用 Bike 的 display，纯 Vehicle 对象使用自身的版本。
5. SQL Query with Aggregate Functions and GROUP BY | SQL 查询中的聚合函数与 GROUP BY
Problem: A table Orders has columns: OrderID (INT), CustomerName (VARCHAR), Product (VARCHAR), Quantity (INT), Price (DECIMAL). Write an SQL query to find, for each customer, the total amount spent (Quantity * Price) and list only those customers whose total spending exceeds 500. Order the result by total amount descending.
题目：表 Orders 包含列：OrderID (INT), CustomerName (VARCHAR), Product (VARCHAR), Quantity (INT), Price (DECIMAL)。编写 SQL 查询，找出每位客户的总消费金额 (Quantity * Price)，并仅列出总消费超过 500 的客户，按总金额降序排列。
The required query uses GROUP BY, SUM, HAVING, and ORDER BY. The multiplication within the SUM is straightforward: SUM(Quantity * Price).
该查询需使用 GROUP BY、SUM、HAVING 和 ORDER BY。在 SUM 内直接进行乘法：SUM(Quantity * Price)。
SELECT CustomerName, SUM(Quantity * Price) AS TotalSpent
FROM Orders
GROUP BY CustomerName
HAVING SUM(Quantity * Price) > 500
ORDER BY TotalSpent DESC;
This groups rows by customer, calculates the sum of line totals, filters groups using HAVING (not WHERE, because condition is on an aggregate), and orders the result. Note that aliases like TotalSpent may be used in ORDER BY in many SQL dialects but not in HAVING; however the full expression can be repeated.
此查询按客户分组，计算行总额的总和，使用 HAVING 过滤分组（而非 WHERE，因为条件应用于聚合结果），并对结果排序。注意在许多 SQL 方言中别名 TotalSpent 可用于 ORDER BY，但不能用于 HAVING；不过可以重复使用完整表达式。
6. Simplifying Boolean Expressions Using Karnaugh Maps | 用卡诺图化简布尔表达式
Problem: Simplify the Boolean function F(A, B, C) = Σm(1, 2, 3, 6, 7) using a Karnaugh map. Write the minimal sum‑of‑products (SOP) expression.
题目：用卡诺图化简布尔函数 F(A, B, C) = Σm(1, 2, 3, 6, 7)，写出最简的与或式（SOP）。
We have three variables A, B, C. The minterms: 1 (001), 2 (010), 3 (011), 6 (110), 7 (111). A is the most significant bit.
我们使用三个变量 A, B, C。最小项：1 (001), 2 (010), 3 (011), 6 (110), 7 (111)。A 为最高位。
Draw a 2×4 K‑map (A on rows, BC on columns). Group the ones: group of four covers m2,m3,m6,m7? Let’s arrange:
绘制 2×4 卡诺图（A 为行，BC 为列）。将 1 单元格分组：四个一组是否覆盖 m2, m3, m6, m7？布置如下：
| A\BC | 00 | 01 | 11 | 10 |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
The cells for minterms: m1 (A=0,BC=01)=1; m2 (0,10)=1; m3 (0,11)=1; m6 (1,10)=1; m7 (1,11)=1. We can form a group of four: cells where BC=10 and 11, across both A=0 and A=1 — that covers m2,m3,m6,m7. This group simplifies to B (since C changes within the group, and A changes too? Actually for BC=10,11, B remains 1 while C varies and A varies, so the group gives B). Then the remaining lone cell m1 (001) cannot combine with any other, so it remains A’·B’·C. However, check if a group of two can include m1 with m3? m1 (001) and m3 (011) differ in B only, so they could form a group A’·C? But m3 is already used. To minimize literals, it’s better to group all possible ones. Often, the optimal SOP groups: group 1: (m2,m3,m6,m7) → B; group 2: (m1,m3) → A’C. Then F = B + A’·C. Let’s verify: m1: A’C is true (B false), plus B false? Wait B=0 for m1, so B term is 0, A’C term =1*1=1, so 1. m3: B=1 (1), A’C=1 as well, but B already covers. Works. So minimal SOP: F = B + A’·C.
最小项 m1 (0,01)=1; m2 (0,10)=1; m3 (0,11)=1; m6 (1,10)=1; m7 (1,11)=1。可以组成一个包含四个单元格的组：BC=10 和 11 两列，A=0 和 A=1 两行，涵盖了 m2,m3,m6,m7。该组简化为 B（因为组内 C 变化，A 也变化，但 B 恒为 1）。剩下的单个单元格 m1 (001) 无法与其他组合，若单独则为 A’B’C。但检查与 m3 组合：m1 (001) 和 m3 (011) 仅在 B 上不同，可组成 A’C。由于 m3 已被大组覆盖，该组合依然有效。最终最简与或式：F = B + A’·C。
7. Instruction Pipelining and Hazards | 指令流水线与冒险
Problem: A processor has a 5‑stage pipeline: Fetch (F), Decode (D), Execute (E), Memory (M), Write‑back (W). Each stage takes one clock cycle. For the following sequence of instructions, identify any data hazard and explain how forwarding can resolve it. Show the pipeline diagram.
I1: ADD R1, R2, R3 // R1 ← R2 + R3
I2: SUB R4, R1, R5 // R4 ← R1 – R5
I3: AND R6, R1, R7 // R6 ← R1 AND R7
I4: OR R8, R2, R9 // R8 ← R2 OR R9
题目：某处理器具有五级流水线：取指 (F)、译码 (D)、执行 (E)、访存 (M)、写回 (W)。每级一个时钟周期。对于下列指令序列，找出数据冒险并解释如何通过转发解决。画出流水线时空图。
Data hazard occurs when an instruction depends on the result of a previous instruction that has not yet been written back. Here I2 uses R1 produced by I1, and I3 also uses R1. Without forwarding, I2 must stall until I1 completes W stage. Pipeline diagram without forwarding:
数据冒险发生在指令需要用到前一条指令尚未写回的结果时。此处 I2 使用了 I1 产生的 R1，I3 也使用 R1。若无转发，I2 需停顿直到 I1 完成写回。无转发时的流水线时空图：
| Cycle | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| I1 | F | D | E | M | W | |||
| I2 | F | D | D | D | E | M | W |
I2 stalls in decode for two cycles waiting for R1. With forwarding, the result from I1 is available after its execute stage (end of cycle 3) and can be forwarded to I2’s execute stage (beginning of cycle 4). Thus no stall is needed. Pipeline with forwarding:
I2 在译码级停顿两个周期等待 R1。采用转发技术后，I1 的结果在其执行级结束时（周期 3 末）即可获得，并被转发到 I2 的执行级（周期 4 初）。因此无需停顿。带转发的流水线：
| Cycle | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| I1 | F | D | E | M | W | ||
| I2 | F | D | E | M | W | ||
| I3 | F | D | E | M | W |
Likewise, I3 receives R1 via forwarding from I1’s W stage or directly from M stage if available. Forwarding hardware detects the RAW (read‑after‑write) dependency and routes the result from the output of the ALU (or memory) directly to the input of the ALU for the dependent instruction.
类似地，I3 通过转发从 I1 的写回级或访存级获取 R1。转发硬件检测到 RAW（读后写）相关性，并将结果从 ALU（或存储器）的输出直接路由到相关指令的 ALU 输入端。
8. Subnetting and CIDR Notation | 子网划分与 CIDR 表示法
Problem: An organization is assigned the IP address block 192.168.10.0/24. It needs to create four subnets with equal numbers of hosts, one per department. List the subnet addresses, subnet masks, range of usable host addresses, and broadcast address for each subnet. What is the maximum number of hosts per subnet?
题目：某组织获得 IP 地址块 192.168.10.0/24，需创建四个大小相等的子网，每个部门一个。列出每个子网的子网地址、子网掩码、可用主机地址范围以及广播地址。每个子网最多可容纳多少台主机？
A /24 network provides 256 addresses (0‑255). To create four equal subnets, we need to borrow 2 bits from the host portion, making the prefix length /26 (since 2² = 4). The subnet mask becomes 255.255.255.192. Each subnet has 64 addresses, but two are reserved (network address and broadcast). Thus usable hosts per subnet = 62.
/24 网络提供 256 个地址（0‑255）。创建 4 个相等子网需从主机位借 2 位，前缀长度变为 /26（因 2² = 4）。子网掩码为 255.255.255.192。每个子网有 64 个地址，但保留网络地址和广播地址，因此每个子网可用主机数 = 62。
| Subnet | Network Address | Subnet Mask | Usable Host Range | Broadcast |
|---|---|---|---|---|
更多咨询请联系16621398022（同微信）
CommentsMore posts |
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导