A-Level Computer Science: Typical Example Questions Explained | A-Level 计算机：典型例题详解

📚 A-Level Computer Science: Typical Example Questions Explained | A-Level 计算机：典型例题详解

Mastering A-Level Computer Science requires more than memorising facts — it demands the ability to apply concepts to unfamiliar problems. This article walks through a series of carefully chosen example questions covering key topics, including data structures, algorithms, Boolean logic, system architecture, networking, databases, and programming paradigms. Each question is explained step by step, providing both an English breakdown and its Chinese counterpart so that bilingual learners can build confidence. Use these examples to sharpen your analytical thinking and exam technique.

要掌握 A-Level 计算机科学，仅靠记忆知识点是远远不够的——它更需要将概念灵活应用于陌生问题的能力。本文精选了一系列涵盖数据结构、算法、布尔逻辑、系统架构、网络、数据库以及编程范式的典型例题，逐题详细解析，每个步骤均提供英文讲解和对应的中文阐释，帮助双语学习者建立信心。通过这些例题，你可以锻炼分析思维与应试技巧。

1. Sorting Algorithm Efficiency | 排序算法效率分析

Question: The following pseudocode describes a sorting algorithm on an array A of length n. Determine its worst‑case time complexity, explaining your reasoning.

FOR i = 0 TO n-2
    minIndex = i
    FOR j = i+1 TO n-1
        IF A[j] < A[minIndex] THEN
            minIndex = j
        ENDIF
    NEXT j
    SWAP A[i] AND A[minIndex]
NEXT i

题目： 以下伪代码对一个长度为 n 的数组 A 执行某种排序算法。请确定其最坏情况下的时间复杂度，并说明理由。

FOR i = 0 TO n-2
    minIndex = i
    FOR j = i+1 TO n-1
        IF A[j] < A[minIndex] THEN
            minIndex = j
        ENDIF
    NEXT j
    SWAP A[i] AND A[minIndex]
NEXT i

This is the standard selection sort. The outer loop executes n−1 times. For each iteration i, the inner loop runs from i+1 to n−1, yielding approximately (n−1)+(n−2)+…+1 = n(n−1)/2 comparisons. In the worst case, the number of swaps is n−1. The dominant term is n²/2, so the worst‑case time complexity is O(n²).

这是标准的选择排序。外层循环执行 n−1 次。对于每个 i，内层循环从 i+1 执行到 n−1，比较次数约为 (n−1)+(n−2)+…+1 = n(n−1)/2。最坏情况下交换次数为 n−1。主导项为 n²/2，因此最坏时间复杂度为 O(n²)。

Key insight: nested loops where the inner range depends on the outer loop index often give O(n²). Always express the total operations as a summation and retain the fastest‑growing term.

关键要点：当内层循环的范围依赖于外层循环索引时，往往会产生 O(n²) 的时间复杂度。应始终将总操作次数写成级数形式，并保留增长最快的项。

2. Stack Simulation and Postfix Notation | 栈模拟与后缀表达式

Question: Convert the infix expression (A + B) × C − D ÷ E into postfix (Reverse Polish Notation) showing the stack stages. Then evaluate the postfix expression for A=3, B=2, C=4, D=8, E=2.

题目： 将中缀表达式 (A + B) × C − D ÷ E 转换为后缀表达式（逆波兰表示法），并展示栈的变化过程。然后针对 A=3, B=2, C=4, D=8, E=2 对后缀表达式求值。

Using the shunting‑yard algorithm with operator precedence (^ highest, ×÷ next, +− lowest):

Step 1: push '(' ; output: empty ; stack: ( .

Step 2: A → output 'A'

Step 3: '+' push ; stack: ( +

Step 4: B → output 'B'

Step 5: ')' pop '+' to output ; stack empty → output: A B +

... Final postfix: A B + C × D E ÷ −

利用调度场算法，根据运算符优先级（^最高，×÷次之，+−最低）：

步骤 1：压入 '(' ；输出：空；栈：( 。

步骤 2：A → 输出 'A'

步骤 3：压入 '+' ；栈：( +

步骤 4：B → 输出 'B'

步骤 5：')' 弹出 '+' 到输出；栈空 → 输出：A B +

... 最终后缀式：A B + C × D E ÷ −

Evaluation: push operands; on operator, pop two, apply, push result.

(3+2)=5 → push 5; push 4; × → 5×4=20; push 8; push 2; ÷ → 8÷2=4; − → 20−4=16. Result is 16.

求值：操作数入栈；遇到运算符则弹出两个操作数，运算后压回。

(3+2)=5 → 压入5；压入4；× → 5×4=20；压入8；压入2；÷ → 8÷2=4；− → 20−4=16。结果为16。

Stacks are vital in expression evaluation and recursion. Practise converting between infix and postfix to deepen your understanding of compiler design.

栈在表达式求值与递归中至关重要。多练习中缀与后缀转换，有助于理解编译器设计。

3. Recursion vs Iteration: Fibonacci Numbers | 递归与迭代：斐波那契数列

Question: Write a recursive function fib(n) that returns the n‑th Fibonacci number (with fib(0)=0, fib(1)=1). Then explain why this recursive solution is inefficient for large n and provide an iterative alternative with O(n) time.

题目： 编写递归函数 fib(n)，返回第 n 个斐波那契数（假设 fib(0)=0, fib(1)=1）。然后解释为什么这种递归解法对大的 n 效率低下，并给出一个时间复杂度为 O(n) 的迭代解法。

Recursive implementation (Python‑like pseudocode):

function fib(n)
    if n <= 1 then
        return n
    else
        return fib(n-1) + fib(n-2)
    endif
endfunction

递归实现（类 Python 伪代码）：

function fib(n)
    if n <= 1 then
        return n
    else
        return fib(n-1) + fib(n-2)
    endif
endfunction

This version has exponential time complexity O(2ⁿ) because many subproblems are recomputed. For instance, fib(5) calls fib(4) and fib(3); fib(4) again calls fib(3) and fib(2), leading to redundant calculations. An iterative solution stores only the previous two values:

该版本的时间复杂度为指数级 O(2ⁿ)，因为许多子问题被重复计算。例如 fib(5) 会调用 fib(4) 和 fib(3)，而 fib(4) 又会调用 fib(3) 和 fib(2)，造成大量冗余。迭代解只需保存前两个值：

function fib_iter(n)
    if n <= 1 then return n endif
    a = 0
    b = 1
    for i = 2 to n do
        temp = a + b
        a = b
        b = temp
    next i
    return b
endfunction

This loop runs n−1 times, giving O(n). The space complexity improves from O(n) call stack to O(1). Understanding recursion limits prepares you for dynamic programming and efficiency questions.

该循环执行 n−1 次，时间复杂度为 O(n)。空间复杂度从递归调用栈的 O(n) 优化为 O(1)。理解递归的局限性将为学习动态规划和回答效率问题打下基础。

4. Boolean Algebra Simplification | 布尔代数化简

Question: Simplify the Boolean expression F = A·B·C + A·B·C' + A·B'·C using algebraic laws. (A' denotes NOT A).

题目： 用代数定律化简布尔表达式 F = A·B·C + A·B·C' + A·B'·C （A' 表示 NOT A）。

Step 1: Factor A·B from the first two terms: A·B·(C + C') + A·B'·C. Since C + C' = 1, we get A·B·1 + A·B'·C = A·B + A·B'·C.

Step 2: Factor A: A·(B + B'·C). Apply the absorption law: B + B'·C = B + C (because B + B'·C = (B+B')·(B+C) = 1·(B+C) = B+C). Therefore, F = A·(B+C) = A·B + A·C.

步骤 1：从前两项提取公因子 A·B：A·B·(C + C') + A·B'·C。因为 C + C' = 1，得到 A·B·1 + A·B'·C = A·B + A·B'·C。

步骤 2：提取公因子 A：A·(B + B'·C)。利用吸收律：B + B'·C = B + C（因为 B + B'·C = (B+B')·(B+C) = 1·(B+C) = B+C）。因此，F = A·(B+C) = A·B + A·C。

The simplified expression is A·B + A·C. Always verify with a truth table if unsure. This skill is directly tested in logic gate minimisation.

化简后的表达式为 A·B + A·C。如不确定，可用真值表验证。这一技能在逻辑门化简题中直接考查。

5. Logic Circuit Design | 逻辑电路设计

Question: Draw a logic circuit for the simplified function F = A·B + A·C using only NAND gates (two‑input). Show that NAND is a universal gate.

题目： 仅使用二输入与非门（NAND）画出化简后函数 F = A·B + A·C 的逻辑电路，并证明 NAND 是通用门。

A NAND gate gives (X·Y)'. To obtain NOT A: connect both inputs of a NAND to A, output = (A·A)' = A'.

AND from NAND: A AND B = (A NAND B)' = NAND followed by a NOT (which is another NAND configured as inverter). OR from NAND: A + B = (A'·B')' = NAND of the inverted inputs. Thus any Boolean function can be built from NAND gates.

与非门输出为 (X·Y)'。要得到 NOT A，将 NAND 的两个输入端均接 A，输出为 (A·A)' = A'。

用 NAND 实现 AND：A AND B = (A NAND B)' = 先用一个 NAND，再接一个作为反相器的 NAND。用 NAND 实现 OR：A + B = (A'·B')'，即先取反再 NAND。因此任意布尔函数都可仅由 NAND 门构造。

Circuit for F: first create A·B using NAND + inverter; similarly A·C; then combine with an OR‑built‑from‑NAND structure. The resulting multi‑level NAND network is a favourite exam topic.

F 的电路：先用 NAND 加反相器产生 A·B；同理得到 A·C；然后用 NAND 构成的 OR 结构连接它们。由此得到的多级 NAND 网络是考试常考的主题。

6. CPU Fetch‑Decode‑Execute Cycle | CPU 取指‑译码‑执行周期

Question: Describe the steps of the fetch‑decode‑execute cycle in a von Neumann CPU, and explain the role of the program counter (PC), memory address register (MAR), memory data register (MDR), and instruction register (IR).

题目： 描述冯·诺依曼架构 CPU 的取指‑译码‑执行周期的步骤，并解释程序计数器（PC）、内存地址寄存器（MAR）、内存数据寄存器（MDR）和指令寄存器（IR）的作用。

In the fetch phase: PC holds the address of the next instruction; its value is copied to MAR; a read signal is sent to memory; the instruction is placed on the data bus and stored in MDR, then transferred to IR. The PC is incremented to point to the next instruction.

Decode: the control unit interprets the opcode in the IR.

Execute: the control unit activates relevant circuitry to carry out the operation, possibly using the ALU and other registers. If a jump occurs, the PC is overwritten.

取指阶段：PC 存放下一条指令的地址，该值被复制到 MAR；内存收到读信号，指令通过数据总线存入 MDR，再传送到 IR；之后 PC 递增指向下一条指令。

译码：控制单元解读 IR 中的操作码。

执行：控制单元激活相应电路以完成操作，可能用到 ALU 及其他寄存器。如发生跳转，PC 会被改写。

Understanding this cycle is essential for grasping how machine language instructions are processed and for evaluating pipeline hazards.

理解这个周期对于掌握机器语言指令的处理过程以及评估流水线冲突至关重要。

7. Network Protocols and the OSI Model | 网络协议与 OSI 模型

Question: Compare the roles of TCP and UDP at the transport layer, giving an appropriate application for each. Explain how the four‑layer TCP/IP model maps to the OSI seven‑layer model.

题目： 比较传输层中 TCP 和 UDP 的作用，并分别为其给出一个适用应用。解释四层 TCP/IP 模型如何映射到 OSI 七层模型。

TCP (Transmission Control Protocol) provides connection‑oriented, reliable delivery with error checking, flow control, and ordering. It is used where data integrity is crucial, e.g., HTTP/HTTPS, email (SMTP). UDP (User Datagram Protocol) is connectionless, faster, but does not guarantee delivery or order; it suits real‑time applications such as VoIP and online gaming.

TCP（传输控制协议）提供面向连接、可靠的数据传输，具有错误检查、流量控制和顺序保障，适用于数据完整性至关重要的场景，如 HTTP/HTTPS、电子邮件（SMTP）。UDP（用户数据报协议）是无连接的，速度更快但不保证交付或顺序，适合实时应用，如 VoIP 和在线游戏。

TCP/IP model: Link layer (maps to OSI Physical + Data Link), Internet layer (Network), Transport layer (Transport), Application layer (Session + Presentation + Application). Remembering this mapping helps troubleshoot network issues and understand encapsulation.

TCP/IP 模型：链路层（对应 OSI 物理层+数据链路层）、互联网层（网络层）、传输层（传输层）、应用层（会话层+表示层+应用层）。记住这种映射有助于排查网络问题并理解数据封装。

8. Normalisation of a Database to 3NF | 数据库三范式规范化

Question: Given the unnormalised table Orders(OrderID, CustomerName, ProductID, ProductName, Quantity), identify partial and transitive dependencies. Normalise the table into 1NF, 2NF, and 3NF.

题目： 给定未规范化的表 Orders(OrderID, CustomerName, ProductID, ProductName, Quantity)，找出其中的部分依赖和传递依赖，并将该表规范化至 1NF、2NF 及 3NF。

1NF assumes atomic values; the table is already in 1NF. Primary key can be (OrderID, ProductID) because a customer may order multiple products. Partial dependency: CustomerName depends only on OrderID, not on the full key; ProductName depends only on ProductID. To achieve 2NF, remove partial dependencies: split into Order(OrderID, CustomerName) and OrderDetail(OrderID, ProductID, Quantity) and Product(ProductID, ProductName).

1NF 要求属性值原子化，该表已满足。主键可设为 (OrderID, ProductID)，因为一个客户可能订购多种产品。部分依赖：CustomerName 仅依赖于 OrderID，而不依赖于完整主键；ProductName 仅依赖于 ProductID。为满足 2NF，移除部分依赖：拆分为 Order(OrderID, CustomerName)、OrderDetail(OrderID, ProductID, Quantity) 及 Product(ProductID, ProductName)。

Transitive dependency: in Order, maybe CustomerAddress depends on CustomerName, not directly on OrderID — if that existed, we would move it to a Customer table for 3NF. In our current tables, there are no non‑key transitive dependencies, so the schema is already in 3NF.

传递依赖：在 Order 表中，若存在 CustomerAddress 依赖于 CustomerName 而非直接依赖于 OrderID，则需将其移至 Customer 表以满足 3NF。在当前拆分中，所有非主属性均直接依赖于主键，因此已满足 3NF。

9. Object‑Oriented Design: Inheritance and Polymorphism | 面向对象设计：继承与多态

Question: Define a base class Shape with a method area(). Derive classes Circle and Rectangle, each overriding area(). Write pseudocode that demonstrates polymorphism by storing different shapes in an array and iterating to print areas.

题目： 定义基类 Shape，包含方法 area()。派生出 Circle 和 Rectangle 两个子类，各自重写 area()。编写伪代码，将不同的形状对象存入数组并通过循环打印面积，以展示多态性。

class Shape
    method area()
        return 0
    endmethod
endclass

class Circle inherits Shape
    property radius
    method area()
        return 3.14159 * radius * radius
    endmethod
endclass

class Rectangle inherits Shape
    property width, height
    method area()
        return width * height
    endmethod
endclass

shapes = [new Circle(5), new Rectangle(4,6), new Circle(3)]
for each s in shapes
    print(s.area())
next s

Polymorphism allows the call s.area() to execute the correct override at runtime based on the object's actual type. This promotes extensibility — you can add a Triangle class without modifying the loop.

多态使得 s.area() 调用在运行时根据对象的实际类型执行正确的重写方法。这提高了可扩展性——可以添加 Triangle 类而无须修改循环代码。

10. Computational Complexity of a Recursive Algorithm | 递归算法的计算复杂度

Question: For the merge sort algorithm, write a recurrence relation for the number of comparisons T(n) and solve it to show that the time complexity is O(n log n).

题目： 对于归并排序算法，写出比较次数的递推关系式 T(n) 并求解，证明其时间复杂度为 O(n log n)。

Merge sort divides the array into two halves of size n/2, recursively sorts them, and then merges. The merge step requires at most n comparisons. Hence the recurrence is T(n) = 2T(n/2) + n, with T(1) = 0. Using the Master Theorem or repeated substitution: T(n) = 2[2T(n/4) + n/2] + n = 4T(n/4) + 2n = ... = nT(1) + n log₂ n. Therefore T(n) = O(n log n).

归并排序将数组分成两个大小为 n/2 的子数组，递归排序后再合并。合并步骤最多需要 n 次比较。因此递推关系为 T(n) = 2T(n/2) + n，其中 T(1) = 0。利用主定理或重复代入法：T(n) = 2[2T(n/4) + n/2] + n = 4T(n/4) + 2n = ... = nT(1) + n log₂ n。因此 T(n) = O(n log n)。

This logarithmic‑linear complexity is optimal for comparison‑based sorting. The ability to formulate and solve recurrences is a tested skill for algorithm analysis.

这种线性对数复杂度是基于比较的排序算法的最优边界。建立并求解递推关系是算法分析中的考查要点。

11. Binary Search Tree Insertion and Traversal | 二叉搜索树的插入与遍历

Question: Insert the following keys into an initially empty binary search tree (BST): 40, 20, 60, 10, 30, 50, 70. Then list the nodes in pre‑order, in‑order, and post‑order traversal.

题目： 将以下键值依次插入一棵初始为空的二叉搜索树（BST）：40, 20, 60, 10, 30, 50, 70。然后分别列出先序、中序和后序遍历的节点顺序。

Insertion rule: smaller to left subtree, larger to right. The resulting BST has root 40, left child 20 (with left 10, right 30), right child 60 (with left 50, right 70).

Pre‑order (root, left, right): 40, 20, 10, 30, 60, 50, 70.

In‑order (left, root, right): 10, 20, 30, 40, 50, 60, 70 — sorted order.

Post‑order (left, right, root): 10, 30, 20, 50, 70, 60, 40.

插入规则：较小值进入左子树，较大值进入右子树。建成的 BST 根为 40，左子 20（左子 10，右子 30），右子 60（左子 50，右子 70）。

先序（根‑左‑右）：40, 20, 10, 30, 60, 50, 70。

中序（左‑根‑右）：10, 20, 30, 40, 50, 60, 70 — 恰好是升序排列。

后序（左‑右‑根）：10, 30, 20, 50, 70, 60, 40。

Tree traversals form the basis of expression evaluation, serialisation, and range queries. Make sure you can reconstruct the tree from two traversals.

树的遍历是表达式求值、序列化和范围查询的基础。务必确保能从两种遍历重建二叉树。

12. Ethical and Legal Issues in Computing | 计算中的伦理与法律问题

Question: Discuss the ethical implications of using facial recognition technology in public surveillance. Refer to relevant legislation such as GDPR and the concepts of data minimisation, consent, and profiling.

题目： 讨论在公共监控中使用面部识别技术所涉及的伦理问题。提及相关法规，如 GDPR，以及数据最小化、知情同意和用户画像等概念。

Facial recognition can enhance security but risks mass surveillance, bias, and erosion of privacy. Under GDPR, biometric data is 'special category' data requiring explicit consent. Data minimisation demands that only necessary data be collected; continuous public scanning often violates this principle. Profiling can lead to discrimination. Ethical design must balance public safety with individual rights.

面部识别可提升安全性，但存在大规模监控、偏见及侵蚀隐私的风险。根据 GDPR，生物特征数据属于“特殊类别”数据，需获取明确同意。数据最小化原则要求只收集必要数据，持续公共扫描常常违背此原则。用户画像可能导致歧视。伦理设计必须在公共安全与个人权利之间取得平衡。

Exam answers should demonstrate awareness of both technical capabilities and societal impact, citing principles from the Computer Science ethics framework.

考试答案应展现出对技术能力与社会影响的双重认识，并引用计算机科学伦理框架中的原则。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

A-Level Computer Science: Typical Example Questions Explained | A-Level 计算机：典型例题详解