Year 13 AQA Computer Science: Unit Test Mock Paper Walkthrough | AQA 计算机科学单元测试模拟卷精讲

📚 Year 13 AQA Computer Science: Unit Test Mock Paper Walkthrough | AQA 计算机科学单元测试模拟卷精讲

This article provides a detailed walkthrough of a typical Year 13 AQA Computer Science unit test mock paper, covering key topics from the A-level specification (7517). Each question is analysed with step-by-step solutions, highlighting common pitfalls and examiner expectations. The mock paper focuses on data structures, algorithms, object-oriented programming, database design, finite state machines and computational complexity. Use this walkthrough to consolidate your revision and sharpen your exam technique.

本文深入解析一份典型的 AQA A-level 计算机科学（7517）十三年级单元测试模拟卷，涵盖数据结构、算法、面向对象编程、数据库设计、有限状态机及计算复杂度等核心考点。每一题都配有分步解答，并指出常见错误与评分要点，帮助同学们巩固复习、提升应试能力。

1. Abstract Data Types and Stack Operations | 抽象数据类型与栈操作

Question: A stack abstract data type (ADT) supports push, pop, peek and isEmpty operations. The stack is implemented using a static array of size MAX. Trace the state of the stack after the following sequence of operations, starting from an empty stack: push(10), push(25), pop(), push(7), push(14), pop(), peek(). Assume no error occurs.

题目：栈（stack）抽象数据类型支持 push、pop、peek 和 isEmpty 操作。假设使用一个大小为 MAX 的静态数组实现栈。从空栈开始，跟踪以下操作执行后栈的状态：push(10)、push(25)、pop()、push(7)、push(14)、pop()、peek()。假设没有发生错误。

English solution: Begin with an empty stack. After push(10), the stack contains [10] (top). Push(25) ➔ [10, 25]. Pop() removes 25, stack ➔ [10]. Push(7) ➔ [10, 7]. Push(14) ➔ [10, 7, 14]. Pop() removes 14, stack ➔ [10, 7]. Peek() returns the top element, 7, without modifying the stack. The final stack remains [10, 7] with top pointer at index 1 (if zero-based). Common mistake: confusing the order of elements or forgetting that peek does not remove the item.

中文解答：初始为空栈。push(10) 后栈内容为 [10]（栈顶）。push(25) ➔ [10, 25]。pop() 移除 25，栈变为 [10]。push(7) ➔ [10, 7]。push(14) ➔ [10, 7, 14]。pop() 移除 14，栈变为 [10, 7]。peek() 返回栈顶元素 7，栈保持不变。最终栈为 [10, 7]，栈顶指针指向索引 1（基于零）。常见错误：混淆元素顺序或忘记 peek 不移除元素。

2. Recursive Algorithm and Trace Table | 递归算法与跟踪表

Question: Consider the following recursive function written in pseudocode. The function mystery takes two integer parameters a and b. Provide a trace table for the call mystery(4, 3) and state what the function computes.

function mystery(a, b):
if b == 0 then return 1
else return a * mystery(a, b – 1)

题目：考虑以下伪代码递归函数。函数 mystery 接受两个整数参数 a 和 b。为调用 mystery(4, 3) 提供跟踪表，并说明该函数的功能。

English solution: mystery(a, b) computes a^b (a raised to the power b). Trace for mystery(4,3): initial call a=4, b=3. b≠0, compute 4 * mystery(4,2). Recurse: mystery(4,2) ➔ 4 * mystery(4,1); mystery(4,1) ➔ 4 * mystery(4,0); mystery(4,0) returns 1. Unwind: mystery(4,1)=4*1=4; mystery(4,2)=4*4=16; mystery(4,3)=4*16=64. Return 64. The trace table should show call depth, parameters, return value at each step. Key marking points: clearly indicating base case and the multiplication step.

中文解答：mystery(a, b) 计算 a 的 b 次幂（a^b）。跟踪 mystery(4,3)：初始调用 a=4, b=3。b≠0，计算 4 * mystery(4,2)。递归：mystery(4,2) ➔ 4 * mystery(4,1)；mystery(4,1) ➔ 4 * mystery(4,0)；mystery(4,0) 返回 1。回溯展开：mystery(4,1)=4×1=4；mystery(4,2)=4×4=16；mystery(4,3)=4×16=64。返回 64。跟踪表应清晰展示调用深度、参数、每步返回值。得分要点：明确指出基础情形和乘法步骤。

3. Object-Oriented Design: Class Diagram and Inheritance | 面向对象设计：类图与继承

Question: A software system models vehicles. All vehicles have a registration number and a manufacturer. Cars have a number of doors, while motorcyles have an engine capacity. Both car and motorcyle classes should inherit from a base Vehicle class. Illustrate the class diagram, showing attributes and methods, and explain how polymorphism could be used for a method displayInfo().

题目：某软件系统对车辆建模。所有车辆都有车牌号和制造商。轿车有车门数量，摩托车有发动机排量。轿车和摩托车类都应继承自基类 Vehicle。画出类图，标出属性和方法，并说明如何利用多态性实现 displayInfo() 方法。

English solution: The Vehicle class has attributes regNumber: String, manufacturer: String. It declares an abstract or virtual method displayInfo(). Car inherits from Vehicle and adds doors: Integer, overriding displayInfo() to show reg, manufacturer and doors. Motorcycle inherits, adds engineCapacity: Real, overriding displayInfo() accordingly. Class diagram uses UML notation with inheritance arrow. Polymorphism allows a client to process a list of Vehicle references calling displayInfo() – each object uses its own overridden version, enabling code reusability and flexibility. Common error: forgetting to show the inheritance relationship correctly.

中文解答：Vehicle 类具有属性 regNumber: String、manufacturer: String，并声明抽象或虚方法 displayInfo()。Car 继承 Vehicle，添加 doors: Integer 属性，重写 displayInfo() 显示车牌、制造商和车门数。Motorcycle 继承 Vehicle，添加 engineCapacity: Real，相应重写 displayInfo()。类图使用 UML 符号，带上继承箭头。多态性允许客户端处理 Vehicle 引用列表，调用 displayInfo() 时每个对象使用自己的重写版本，实现代码复用与灵活性。常见错误：未正确表示继承关系。

4. Database Normalisation and SQL | 数据库规范化与 SQL

Question: Given the unnormalised table OrderDetails(OrderID, CustomerName, CustomerPhone, ProductID, ProductDescription, Quantity, UnitPrice), normalise it to third normal form. Then write an SQL query to find the total value of orders placed by a customer named ‘Smith’.

题目：给定非规范化表 OrderDetails(OrderID, CustomerName, CustomerPhone, ProductID, ProductDescription, Quantity, UnitPrice)，将其规范化到第三范式。然后编写 SQL 查询，找出名为 ‘Smith’ 的客户的总订单金额。

English solution: Step 1 – 1NF: ensure atomic values and a primary key (OrderID, ProductID). Step 2 – 2NF: remove partial dependencies; CustomerName, CustomerPhone depend only on OrderID, so create Orders(OrderID, CustomerName, CustomerPhone). The remaining attributes ProductDescription, Quantity, UnitPrice depend on the full key, they stay in OrderDetails. But ProductDescription depends on ProductID alone, so move to Products(ProductID, ProductDescription, UnitPrice). Now OrderDetails(OrderID, ProductID, Quantity). All tables in 3NF: no transitive dependencies (CustomerPhone depends on CustomerName? In practice further split if needed, assume CustomerName→CustomerPhone stable and customer table created.) SQL query: SELECT SUM(od.Quantity * p.UnitPrice) AS TotalValue FROM Orders o JOIN OrderDetails od ON o.OrderID = od.OrderID JOIN Products p ON od.ProductID = p.ProductID WHERE o.CustomerName = ‘Smith’;

中文解答：第一步 1NF：确保原子值，设定主键为 (OrderID, ProductID)。第二步 2NF：消除部分依赖；CustomerName、CustomerPhone 仅依赖于 OrderID，故创建 Orders(OrderID, CustomerName, CustomerPhone)。剩下的 ProductDescription、Quantity、UnitPrice 依赖于整个主键，留在 OrderDetails。但 ProductDescription 仅依赖于 ProductID，因此移至 Products(ProductID, ProductDescription, UnitPrice)。现在 OrderDetails(OrderID, ProductID, Quantity)。所有表达到 3NF：没有传递依赖（CustomerPhone 依赖于 CustomerName，实际中如需进一步拆分可创建单独的 Customer 表）。SQL 查询：SELECT SUM(od.Quantity * p.UnitPrice) AS TotalValue FROM Orders o JOIN OrderDetails od ON o.OrderID = od.OrderID JOIN Products p ON od.ProductID = p.ProductID WHERE o.CustomerName = ‘Smith’;

5. Finite State Machine with Output | 有限状态机与输出

Question: Design a Mealy machine that detects the pattern ‘101’ in a binary input stream, outputting ‘1’ when the pattern is recognised, else ‘0’. Overlap is allowed. Provide the state transition diagram and explain how it works.

题目：设计一个 Mealy 机，检测二进制输入序列中的模式 ‘101’，识别时输出 ‘1’，否则输出 ‘0’。允许重叠。给出状态转移图并解释其工作原理。

English solution: States: S0 (reset, initial), S1 (received ‘1’), S2 (received ’10’). Transitions: From S0, input ‘1’ → S1 / output ‘0’; ‘0’ → stay S0 / ‘0’. From S1, input ‘0’ → S2 / ‘0’; input ‘1’ → stay S1 / ‘0’. From S2, input ‘1’ → S1 / ‘1’ (pattern detected, overlapping allowed, so go to S1 as the ending ‘1’ can be start of next pattern); input ‘0’ → S0 / ‘0’. This design correctly outputs ‘1’ on input sequences like …10101…, producing an output ‘1’ for each overlapping pattern. Alternative Moore machine is also possible but Mealy produces faster output. Common exam mistake: failing to handle overlapping, e.g., going directly to S0 after detection, which would miss the second pattern in ‘10101’.

中文解答：状态：S0（复位，初始），S1（收到 ‘1’），S2（收到 ’10’）。转移：从 S0，输入 ‘1’ → S1 / 输出 ‘0’；输入 ‘0’ → 保持 S0 / ‘0’。从 S1，输入 ‘0’ → S2 / ‘0’；输入 ‘1’ → 保持 S1 / ‘0’。从 S2，输入 ‘1’ → S1 / ‘1’（识别到模式，允许重叠，因此转到 S1，因为末尾的 ‘1’ 可以成为下一个模式的开始）；输入 ‘0’ → S0 / ‘0’。该设计可正确地在序列如 10101 上输出两个 ‘1’。另一种 Moore 机也可行但输出延迟。常见错误：未处理重叠，例如检测后直接回 S0，导致在 ‘10101’ 中错过第二个模式。

6. Big-O Notation and Algorithm Analysis | 大 O 表示法与算法分析

Question: Two algorithms exist for searching an array of length n: Algorithm A uses linear search (O(n)) and Algorithm B uses binary search on a pre-sorted array (O(log n)). Explain the worst-case time complexity of each and discuss the practical trade-offs. Give an example where Algorithm A might be preferred despite its higher theoretical complexity.

题目：有两种搜索长度为 n 的数组的算法：算法 A 使用线性搜索（O(n)），算法 B 在预先排序的数组上使用二分搜索（O(log n)）。解释各自的最坏情况时间复杂度，讨论实际权衡，并举例说明尽管算法 A 理论复杂度更高但仍可能被优先选择。

English solution: Linear search checks each element sequentially, worst-case n comparisons ⟶ O(n). Binary search halves the search space each step, worst-case log₂ n comparisons ⟶ O(log n), but requires the array to be sorted. Practical trade-offs: Sorting costs O(n log n) or more, which must be amortised over many searches. For small n, the constant factors of binary search (midpoint calculation, loop overhead) can make linear search faster. Additionally, if the array is frequently modified, maintaining sorted order adds cost. Example: a small, frequently changing list where only a few searches are performed—linear search avoids sort overhead, providing better overall performance.

中文解答：线性搜索顺序检查每个元素，最坏情况需 n 次比较，O(n)。二分搜索每次将搜索空间减半，最坏情况约 log₂ n 次比较，O(log n)，但要求数组已排序。实际权衡：排序需 O(n log n) 甚至更多时间，必须通过大量搜索加以摊还。对于小规模 n，二分搜索的常数因子（中间点计算、循环开销）可能使线性搜索更快。此外，若数组频繁修改，维护有序性会增加额外成本。示例：一个较小且经常变动的列表，只进行少量搜索——线性搜索避免了排序开销，总体性能更优。

7. Recursive Tree Traversal and Expression Trees | 递归树遍历与表达式树

Question: The expression (3 + 5) * (7 – 2) is represented as a binary tree. Perform pre-order, in-order and post-order traversals, writing the output sequences. Relate each traversal to prefix, infix and postfix (Reverse Polish) notation.

题目：表达式 (3 + 5) * (7 – 2) 用二叉树表示。进行前序、中序和后序遍历，写出输出序列，并将每种遍历与前缀、中缀和后缀（逆波兰）记法联系起来。

English solution: The expression tree: root is ‘*’, left child is ‘+’ (with left 3, right 5), right child is ‘-‘ (with left 7, right 2). Pre-order traversal: root, left sub-tree, right sub-tree → * + 3 5 – 7 2 (prefix notation). In-order: left, root, right → 3 + 5 * 7 – 2 (infix, but without parentheses it is ambiguous; original parentheses required). Post-order: left, right, root → 3 5 + 7 2 – * (postfix/Reverse Polish Notation, no ambiguity). Students must carefully preserve correct child order. Common mistake: swapping left/right while traversing or forgetting the parentheses implication.

中文解答：表达式树：根为 ‘*’，左子节点为 ‘+’（左子 3，右子 5），右子节点为 ‘-‘（左子 7，右子 2）。前序遍历：根、左子树、右子树 → * + 3 5 – 7 2（前缀记法）。中序遍历：左、根、右 → 3 + 5 * 7 – 2（中缀记法，但缺少括号会导致歧义，原始表达式需要括号）。后序遍历：左、右、根 → 3 5 + 7 2 – *（后缀/逆波兰记法，无歧义）。学生必须注意保持正确的子节点顺序。常见错误：遍历时左右子节点弄反或忽略括号含义。

8. Network Protocols and the Four-Layer TCP/IP Model | 网络协议与TCP/IP四层模型

Question: Describe how data is transmitted from a web server to a client using the TCP/IP model, explaining the role of each layer. Include the encapsulation process and name at least one protocol at each layer relevant to web browsing.

题目：描述使用 TCP/IP 模型将数据从 Web 服务器传输到客户端的过程，解释每一层的作用。包括封装过程，并为每层命名至少一个与网页浏览相关的协议。

English solution: Four layers (from top): Application (HTTP/HTTPS) – the browser requests a web page. Transport (TCP) – segments data, adds sequence numbers, ensures reliable delivery via acknowledgements and retransmissions. Internet (IP) – encapsulates TCP segments into packets, adds source and destination IP addresses, routes across networks. Link/Network Access (Ethernet, Wi-Fi) – frames packets with MAC addresses for physical transmission over the local medium. Encapsulation: application data → TCP segment → IP packet → Ethernet frame. At the receiving end, the reverse process occurs (decapsulation). Exam tip: always mention the encapsulation hierarchy and specific protocol names.

中文解答：四层模型（自顶向下）：应用层（HTTP/HTTPS）——浏览器请求网页。传输层（TCP）——将数据分段，添加序列号，通过确认与重传机制保证可靠交付。网络层（IP）——将 TCP 段封装为数据包，添加源和目标 IP 地址，跨网络路由。链接层/网络接入层（以太网、Wi-Fi）——将数据包封装为帧，附加 MAC 地址，在本地介质上物理传输。封装过程：应用数据 → TCP 段 → IP 数据包 → 以太网帧。接收端进行相反的解封装。考试提示：始终提及封装层次结构和具体的协议名称。

9. Stack Frame and Subroutine Calls | 栈帧与子程序调用

Question: Explain how a stack is used to manage subroutine calls, including the storage of return addresses, parameters and local variables. Use a diagram to illustrate the stack frame structure for a factorial function.

题目：解释栈如何管理子程序调用，包括返回地址、参数和局部变量的存储。使用图表说明阶乘函数的栈帧结构。

English solution: When a subroutine is called, the processor pushes the return address onto the stack, then typically the old base pointer, creating a new stack frame. Parameters are pushed in reverse order before the call (depending on calling convention). Local variables are allocated below the base pointer. For a recursive factorial(n): each call pushes return address, then n, then local variables. On reaching base case (n=0), the stack unwinds, restoring the previous frame each time. Diagram: Stack grows downward; each frame contains [parameters][return address][old base pointer][local vars]. Marks awarded for clear explanation of stack pointer and base pointer roles.

中文解答：调用子程序时，处理器将返回地址压栈，然后通常保存旧的基址指针，创建新的栈帧。参数在调用前按逆序压栈（取决于调用约定）。局部变量在基址指针下方分配。对于递归 factorial(n)：每次调用压入返回地址，然后是 n，再是局部变量。到达基础情形（n=0）后，栈展开，每次恢复上一帧。图示：栈向低地址增长；每个帧包含 [参数][返回地址][旧基址指针][局部变量]。得分点在于清晰解释栈指针和基址指针的作用。

10. Computational Complexity Classes P and NP | 计算复杂度类 P 与 NP

Question: Define complexity classes P and NP. Describe the significance of the P vs NP problem. Provide an example of an NP-complete problem and explain what it means to be NP-complete.

题目：定义复杂度类 P 和 NP。描述 P vs NP 问题的意义。举一个 NP 完全问题的例子，并解释什么是 NP 完全。

English solution: P is the class of decision problems solvable in polynomial time by a deterministic Turing machine. NP is the class of decision problems for which a proposed solution can be verified in polynomial time by a deterministic Turing machine. The P vs NP problem asks whether P equals NP; if P = NP, all problems whose solutions can be verified quickly could also be solved quickly, which would have profound implications for fields like cryptography. An NP-complete problem is the hardest in NP: any NP problem can be reduced to it in polynomial time. Example: the Boolean satisfiability problem (SAT). A problem is NP-complete if it is in NP and all other NP problems are reducible to it. Understanding this hierarchy is crucial for algorithm design.

中文解答：P 类是能够在多项式时间内被确定性图灵机解决的判定问题集合。NP 类是能够在多项式时间内被确定性图灵机验证所提供解的正确性的判定问题集合。P vs NP 问题探询 P 是否等于 NP；若 P = NP，所有能够快速验证解的问题也能被快速求解，这将对密码学等领域产生深远影响。一个 NP 完全问题是 NP 类中最难的一种：任何 NP 问题都能在多项式时间内归约到它。例子：布尔可满足性问题（SAT）。一个问题称为 NP 完全，如果它属于 NP，且所有其他 NP 问题都可归约到它。理解这一层次结构对于算法设计至关重要。

11. Linked List Insertion and Deletion | 链表插入与删除

Question: Draw a singly linked list node structure and write pseudocode to delete a node with a given value from the list, considering edge cases (empty list, head deletion, value not found).

题目：画出单向链表节点结构，并编写伪代码删除具有给定值的节点，考虑边界情况（空链表、删除头节点、未找到值）。

English solution: A node has two fields: data and next (pointer). To delete a node with value v: if head is null, return (empty). If head.data = v, set head = head.next and return. Otherwise, set current = head. While current.next ≠ null and current.next.data ≠ v, move current = current.next. If current.next is null, value not found, return. Else, set current.next = current.next.next (bypass the node). Works in O(n) time. Key marking: handling head deletion separately, checking for null pointers, and updating the next pointer correctly.

中文解答：节点包含两个字段：data 和 next（指针）。删除值为 v 的节点：如果 head 为 null，返回（空链表）。如果 head.data = v，令 head = head.next 并返回。否则，设 current = head。当 current.next ≠ null 且 current.next.data ≠ v 时，current 后移。若 current.next 为 null，未找到值，返回。否则，令 current.next = current.next.next（绕过目标节点）。时间复杂度 O(n)。得分关键：单独处理删除头节点、检查空指针、正确更新 next 指针。

12. Hashing and Collision Resolution | 哈希与冲突解决

Question: A hash table of size 11 uses the hash function h(k) = k mod 11. Insert the keys: 15, 28, 39, 4, 5, 16 using linear probing. Show the final state of the table and explain the load factor and its effect on performance.

题目：一个大小为 11 的哈希表使用哈希函数 h(k) = k mod 11。使用线性探测插入键：15, 28, 39, 4, 5, 16。展示最终的表格状态，并解释负载因子及其对性能的影响。

English solution: Compute indices: 15 mod11=4, place at 4. 28 mod11=6, place at 6. 39 mod11=6 (collision), probe 7, place at 7. 4 mod11=4 (collision), probe 5, place at 5. 5 mod11=5 (collision), probe 6 occupied, 7 occupied, 8 free, place at 8. 16 mod11=5, probe sequence 6,7,8,9, place at 9. Final table: index 0-3 empty, 4:15, 5:4, 6:28, 7:39, 8:5, 9:16, 10 empty. Load factor = 6/11 ≈ 0.545. Higher load factor increases collisions and search time. For linear probing, performance degrades beyond 0.7–0.8 due to primary clustering. Students must show probing steps clearly.

中文解答：计算索引：15 mod 11=4，置于位置 4。28 mod 11=6，置于 6。39 mod 11=6（冲突），探测 7，置于 7。4 mod 11=4（冲突），探测 5，置于 5。5 mod 11=5（冲突），探测 6 已占，7 已占，8 空闲，置于 8。16 mod 11=5，探测序列 6,7,8,9，置于 9。最终表格：索引 0-3 空，4:15, 5:4, 6:28, 7:39, 8:5, 9:16, 10 空。负载因子 = 6/11 ≈ 0.545。较高的负载因子增加冲突和搜索时间。对于线性探测，负载因子超过 0.7–0.8 时性能因主聚类而下降。学生必须清晰展示探测步骤。

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

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

Year 13 AQA Computer Science: Unit Test Mock Paper Walkthrough | AQA 计算机科学单元测试模拟卷精讲