📚 Core Knowledge Points for Year 13 AQA Computer Science | Year 13 AQA 计算机：核心知识点梳理
Year 13 of the AQA A-level Computer Science course demands a deep and integrated understanding of both theoretical concepts and practical programming skills. This revision guide distils the essential knowledge across all major topics, from advanced data structures to the theory of computation, to help you consolidate your learning and prepare effectively for your examinations.
AQA A-level 计算机科学课程的 Year 13 阶段要求学生对理论概念和实践编程技能有深入且综合的理解。这份复习指南提炼了从高级数据结构到计算理论等所有主要主题的核心知识，帮助你巩固学习并为考试做好有效准备。
1. Advanced Data Structures | 高级数据结构
Efficient data organisation underpins algorithm performance. Key abstract data types (ADTs) include stacks, queues, trees, graphs and hash tables, each with distinct behaviours and use cases.
高效的数据组织是算法性能的基础。关键抽象数据类型（ADT）包括栈、队列、树、图和哈希表，每种都有独特的行为和用例。
Stacks operate on a Last-In-First-Out (LIFO) principle. They are implemented using arrays or linked lists and are fundamental for managing function calls, undo mechanisms, and depth-first traversals.
栈以后进先出（LIFO）原则运行。它们用数组或链表实现，是管理函数调用、撤消机制和深度优先遍历的基础。
Queues follow a First-In-First-Out (FIFO) model. Circular queues optimise memory in array-based implementations, and priority queues ensure that higher-priority items are dequeued before others, often used in CPU scheduling.
队列遵循先进先出（FIFO）模型。环形队列在基于数组的实现中优化内存，而优先级队列确保高优先级项先出队，常用于 CPU 调度。
Trees, especially binary search trees, allow logarithmic average-case lookup, insertion and deletion. Balancing mechanisms, such as AVL trees, maintain height to prevent degradation to O(n) performance.
树，尤其是二叉搜索树，可实现对数平均情况下的查找、插入和删除。AVL 树等平衡机制维持树的高度，防止性能降级为 O(n)。
Graphs represent relationships through vertices and edges, either directed or undirected. They are stored as adjacency matrices or adjacency lists and are essential for modelling networks, maps and dependencies.
图通过顶点和边表示关系，可分为有向或无向。它们存储为邻接矩阵或邻接表，是建模网络、地图和依赖关系所必不可少的。
Hash tables map keys to array indices via a hash function, offering O(1) average access time. Collision resolution strategies include separate chaining (using linked lists) and open addressing (linear probing).
哈希表通过哈希函数将键映射到数组索引，提供平均 O(1) 的访问时间。冲突解决策略包括分离链接（使用链表）和开放寻址（线性探测）。
2. Graph Traversal and Shortest Path Algorithms | 图遍历与最短路径算法
Graph algorithms are central to solving real‑world problems like route planning and web crawling. Depth‑first search (DFS) uses a stack (or recursion) to explore as far along a branch as possible before backtracking.
图算法是解决路线规划和网络爬虫等现实问题的核心。深度优先搜索（DFS）使用栈（或递归）在回溯前先尽可能地沿着一个分支深入探索。
Breadth‑first search (BFS) employs a queue to visit all neighbours of a vertex before moving to the next level, guaranteeing the shortest path in unweighted graphs.
广度优先搜索（BFS）使用队列，先访问顶点的所有邻居再转到下一层，保证在无权重图中找到最短路径。
Dijkstra's algorithm computes the shortest path from a single source to all other vertices in a weighted graph with non‑negative edges. It uses a priority queue to repeatedly select the vertex with the smallest tentative distance.
Dijkstra 算法计算非负边加权图中从单源到所有其他顶点的最短路径。它使用优先级队列反复选出试探距离最小的顶点。
The A* algorithm enhances Dijkstra by adding a heuristic estimate of the distance to the target, reducing the number of vertices explored. It is widely used in gaming and navigation if the heuristic is admissible (never overestimates).
A* 算法通过增加到目标的启发式估计距离来增强 Dijkstra，减少了探索的顶点数。如果启发式是可接受的（从不估计过高），它被广泛应用于游戏和导航。
3. Complexity Analysis and Comparison of Algorithms | 算法复杂度分析与比较
Big‑O notation describes the limiting behaviour of time or space complexity as input size n grows. Common classes include O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ).
Big‑O 表示法描述了随着输入规模 n 增长，时间或空间复杂度的极限行为。常见类别包括 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 和 O(2ⁿ)。
Searching algorithms illustrate these differences: linear search is O(n) while binary search on a sorted array is O(log n). Binary search repeatedly halves the search interval.
搜索算法体现了这些差异：线性搜索是 O(n)，而在已排序数组上的二分搜索是 O(log n)。二分搜索反复将搜索区间减半。
Sorting algorithms highlight trade‑offs. Merge sort guarantees O(n log n) time but requires O(n) extra space. Quick sort is usually O(n log n) in practice but degrades to O(n²) if a poor pivot is chosen. Insertion sort is O(n²) but efficient for small or nearly sorted data sets.
排序算法突显了权衡。归并排序保证 O(n log n) 时间，但需要 O(n) 额外空间。快速排序在实践中通常是 O(n log n)，但如果选错枢轴会退化为 O(n²)。插入排序是 O(n²)，但对小规模或近乎排序的数据集效率高。
4. Object‑Oriented Programming Principles | 面向对象编程原则
Encapsulation bundles data (attributes) and the methods that operate on them within a class, restricting direct access via access modifiers (private, public). This protects an object's integrity and hides implementation details.
封装将数据（属性）和操作它们的方法捆绑在类中，通过访问修饰符（私有、公有）限制直接访问。这保护了对象的完整性并隐藏了实现细节。
Inheritance allows a subclass to derive properties and behaviours from a superclass, promoting code reuse and establishing “is‑a” relationships. Multiple inheritance can lead to ambiguity and is often replaced by interfaces in many languages.
继承允许子类从超类派生属性和行为，促进代码重用并建立“是一个”的关系。多重继承可能导致歧义，在许多语言中常被接口替代。
Polymorphism enables a single interface to represent different underlying data types. Method overriding lets a subclass provide a specific implementation of a method already defined in its superclass. Method overloading allows multiple methods with the same name but different parameters within a class.
多态性使单一接口能表示不同的底层数据类型。方法重写让子类提供已在超类中定义的方法的特定实现。方法重载允许一个类中存在名称相同但参数不同的多个方法。
Association, aggregation and composition model relationships. Composition implies a strong “part‑of” relationship where the part cannot exist independently of the whole, while aggregation is a weaker “has‑a” relationship.
关联、聚合和组合建模关系。组合意味着强的“部分–整体”关系，部分不能独立于整体存在，而聚合是较弱的“有一个”关系。
5. Functional Programming Paradigm | 函数式编程范式
Functional programming treats computation as the evaluation of mathematical functions, avoiding mutable data and side effects. First‑class functions are treated as values: they can be passed as arguments, returned from functions, and assigned to variables.
函数式编程将计算视为数学函数的求值，避免可变数据和副作用。一等函数被视为值：可以作为参数传递、从函数返回、赋值给变量。
Higher‑order functions either take functions as parameters or return functions as results. Common higher‑order functions are map (apply a function to each element of a list), filter (select elements that satisfy a predicate), and reduce (or fold, combine elements using a binary operation).
高阶函数要么接受函数作为参数，要么返回函数作为结果。常见的高阶函数有 map（对列表的每个元素应用函数）、filter（选择满足谓词的元素）和 reduce（或 fold，使用二元运算组合元素）。
Function composition combines two or more functions to produce a new function: (f ◦ g)(x) = f(g(x)). It builds complex operations from simple, reusable pieces.
函数组合将两个或更多函数组合成一个新函数：(f ◦ g)(x) = f(g(x))。它用简单、可重用的部件构建复杂操作。
Recursion replaces iterative loops. A base case prevents infinite recursion. Pattern matching and list comprehensions are also widely used to express declarative logic.
递归取代迭代循环。基例防止无限递归。模式匹配和列表解析也广泛用于表达声明式逻辑。
6. Boolean Algebra and Digital Logic | 布尔代数与数字逻辑
ore operations are NOT, AND, OR and XOR. De Morgan’s laws relate AND and OR with negation: ¬(A ∧ B) = ¬A ∨ ¬B and ¬(A ∨ B) = ¬A ∧ ¬B.
布尔代数是数字电路设计的基础。变量取值为 TRUE(1) 或 FALSE(0)。核心运算是非、与、或和异或。德摩根定律将合取和析取与否定联系起来：¬(A ∧ B) = ¬A ∨ ¬B 和 ¬(A ∨ B) = ¬A ∧ ¬B。
Karnaugh maps simplify Boolean expressions up to four variables by grouping adjacent ones in powers of two, minimising the number of logic gates required.
卡诺图通过将相邻的 1 按 2 的幂次分组，简化最多四个变量的布尔表达式，从而最小化所需的逻辑门数量。
Combinational logic circuits, such as half‑adders and full‑adders, perform arithmetic. A full‑adder takes three inputs (A, B, carry‑in) and outputs sum and carry‑out. D‑type flip‑flops are sequential circuits that store a single bit and form the basis of registers and memory.
组合逻辑电路，如半加器和全加器，执行算术运算。一个全加器接收三个输入（A、B、进位输入）并输出和与进位输出。D 型触发器是存储单个位的时序电路，构成寄存器和存储器的基础。
7. Computer Architecture and Organisation | 计算机体系结构与组成
The Central Processing Unit (CPU) fetches, decodes and executes instructions. The Von Neumann architecture stores both data and instructions in the same memory, while Harvard architecture separates them, allowing simultaneous access.
中央处理器（CPU）执行取指、译码和执行指令。冯·诺依曼架构将数据和指令存储在同一内存中，而哈佛架构将它们分开，允许同时访问。
Pipelining increases throughput by overlapping the execution of multiple instructions, but hazards (data, control, structural) can cause stalls. CISC (Complex Instruction Set Computer) provides many powerful instructions, whereas RISC (Reduced Instruction Set Computer) uses a smaller, highly optimised set for faster execution.
流水线通过重叠执行多条指令来提高吞吐量，但冒险（数据、控制、结构）可能导致停顿。CISC（复杂指令集计算机）提供许多功能强大的指令，而 RISC（精简指令集计算机）使用更小、高度优化的指令集以实现更快执行。
Memory hierarchy balances speed and cost. Registers are fastest; cache (L1, L2, L3) holds frequently used data; RAM provides main working memory; secondary storage (HDD, SSD) offers non‑volatile capacity. Virtual memory uses a portion of the disk as an extension of RAM, managed by paging and segmentation.
存储器层级结构平衡了速度和成本。寄存器最快；高速缓存（L1、L2、L3）保存常用数据；RAM 提供主工作内存；辅助存储（HDD、SSD）提供非易失容量。虚拟内存使用磁盘的一部分作为 RAM 的扩展，通过分页和分段进行管理。
8. Operating Systems | 操作系统
The operating system manages hardware resources and provides services for application programs. Core functions include memory management, process scheduling, file system management and input/output handling.
操作系统管理硬件资源并为应用程序提供服务。核心功能包括内存管理、进程调度、文件系统管理和输入/输出处理。
Paging divides memory into fixed‑size pages and frames, eliminating external fragmentation and enabling efficient virtual memory. A page table maps virtual pages to physical frames.
分页将内存划分为固定大小的页面和页框，消除了外部碎片并使虚拟内存高效。页表将虚拟页面映射到物理页框。
Segmentation divides memory into variable‑sized logical segments (code, data, stack), reflecting the programmer's view. Combined paged segmentation offers flexibility and efficiency.
分段将内存划分为可变大小的逻辑段（代码、数据、栈），反映程序员的视角。结合分页的分段提供了灵活性和效率。
Scheduling algorithms determine the order processes are executed: First‑Come‑First‑Served (FCFS), Shortest Job First (SJF), Round Robin (RR) and Multi‑level Feedback Queues. Goals include maximising throughput, minimising turnaround time and ensuring fairness.
调度算法决定进程的执行顺序：先来先服务（FCFS）、最短作业优先（SJF）、轮转（RR）和多级反馈队列。目标包括最大化吞吐量、最小化周转时间和确保公平。
9. Communication and Networking | 通信与网络
The TCP/IP protocol stack comprises four layers: Application, Transport, Internet and Network Access. Each layer uses specific protocols—HTTP, FTP, SMTP at Application; TCP and UDP at Transport; IP at Internet—and encapsulates data as it passes down the stack.
TCP/IP 协议栈包含四层：应用层、传输层、互联网层和网络访问层。每一层使用特定的协议——应用层的 HTTP、FTP、SMTP；传输层的 TCP 和 UDP；互联网层的 IP——并在数据向下传递时进行封装。
TCP provides reliable, connection‑oriented delivery with acknowledgements, retransmissions and flow control. UDP is connectionless and faster, suitable for real‑time applications where occasional packet loss is acceptable.
TCP 提供可靠的、面向连接的交付，具有确认、重传和流量控制。UDP 是无连接且更快的，适用于偶尔丢包也可接受的实时应用。
IPv4 addresses are 32‑bit and running out; IPv6 uses 128‑bit addresses. Subnetting divides a network into smaller logical sub‑networks using a subnet mask, improving security and traffic management. Network Address Translation (NAT) allows multiple devices on a private network to share a single public IP.
IPv4 地址是 32 位的，已接近枯竭；IPv6 使用 128 位地址。子网划分使用子网掩码将网络分成更小的逻辑子网络，提高安全性和流量管理。网络地址转换（NAT）允许专用网络上的多个设备共享一个公共 IP。
Firewalls filter incoming and outgoing traffic based on predefined rules, while symmetric and asymmetric encryption (e.g., RSA) protect data confidentiality. Digital signatures and certificates provide authentication and non‑repudiation.
防火墙根据预定规则过滤传入和传出的流量，而对称和非对称加密（如 RSA）保护数据机密性。数字签名和证书提供身份验证和不可否认性。
10. Databases, SQL and Big Data | 数据库、SQL 与大数据
Relational databases store data in tables linked by primary and foreign keys. Normalisation (1NF, 2NF, 3NF) removes data redundancy and update anomalies by organising attributes into appropriately related tables.
关系数据库将数据存储在由主键和外键链接的表中。规范化（1NF、2NF、3NF）通过将属性组织到适当相关的表中来消除数据冗余和更新异常。
SQL (Structured Query Language) enables data definition and manipulation. Key commands: SELECT ... FROM ... WHERE ... JOIN ... GROUP BY ... HAVING ... ORDER BY. Indexes speed up queries but slow down writes and require storage.
SQL（结构化查询语言）支持数据定义和操作。关键命令：SELECT ... FROM ... WHERE ... JOIN ... GROUP BY ... HAVING ... ORDER BY。索引可加快查询速度，但会减慢写入速度并占用存储空间。
Big Data is characterised by the three Vs: Volume (vast amounts), Velocity (speed of generation), and Variety (structured, semi‑structured, unstructured data). Traditional relational databases may be insufficient; distributed file systems and MapReduce frameworks process data across clusters of commodity hardware.
大数据以三个 V 为特征：Volume（海量）、Velocity（生成速度）和 Variety（结构化、半结构化和非结构化数据）。传统关系数据库可能不够；分布式文件系统和 MapReduce 框架在商用硬件集群上处理数据。
11. Theory of Computation | 计算理论
Finite State Machines (FSMs) model systems with a fixed number of states. A deterministic FSM has exactly one transition for each input in each state; a non‑deterministic FSM may have multiple transitions. FSMs are used in lexical analysis and protocol design.
有限状态机（FSM）对具有固定数量状态的系统建模。确定性 FSM 在每个状态下对每个输入恰好有一个转换；非确定性 FSM 可能有多个转换。FSM 用于词法分析和协议设计。
Turing machines are abstract computational models consisting of an infinite tape, a head that reads/writes symbols, and a set of states with transitions. They formalise the notion of an algorithm and define what is computable.
图灵机是抽象的计算模型，由无限长的带、读写符号的磁头和一组带转换状态组成。它们形式化了算法的概念并定义了什么是可计算的。
Regular expressions describe sets of strings (regular languages) and can be recognised by finite state machines. They use operators like concatenation, alternation (|) and Kleene star (*) to define patterns.
正则表达式描述字符串的集合（正则语言），并可由有限状态机识别。它们使用连接、选择 (|) 和克莱尼星号 (*) 等运算符来定义模式。
The Halting Problem proves that there is no universal algorithm that can decide whether any given program will halt on a given input. This establishes fundamental limits of computation.
停机问题证明不存在通用的算法能够判定任意给定程序在给定输入上是否会停机。这确立了计算的基本极限。
12. Legal, Ethical and Environmental Implications | 法律、伦理与环境影响
The Data Protection Act 2018 (UK GDPR) governs the collection, storage and processing of personal data, granting rights to data subjects and imposing obligations on data controllers. Privacy by design and data minimisation are core principles.
《2018 年数据保护法》（英国 GDPR）规范个人数据的收集、存储和处理，赋予数据主体权利并对数据控制者施加义务。设计默认隐私和数据最小化是核心原则。
The Computer Misuse Act 1990 criminalises unauthorised access to computer material, unauthorised access with intent to commit further offences, and unauthorised acts with intent to impair the operation of a computer. The Regulation of Investigatory Powers Act 2000 (RIPA) allows lawful surveillance.
《1990 年计算机滥用法》将未经授权访问计算机材料、意图犯罪而未经授权访问以及意图损害计算机运行的未经授权行为定为犯罪。《2000 年调查权力规范法》（RIPA）允许合法监控。
Ethical frameworks guide decision‑making in computing. The BCS Code of Conduct demands public interest, professional competence, integrity and respect for others. Ethical considerations in AI and autonomous systems include bias, accountability and transparency.
伦理框架指导计算领域的决策。BCS 行为准则要求符合公共利益、专业能力、诚信并尊重他人。人工智能和自主系统中的伦理考量包括偏见、问责和透明度。
Environmental impact of computing includes energy consumption by data centres, e‑waste, and carbon footprint of cloud services. Sustainable practices involve virtualisation, efficient cooling, and circular economy principles for hardware.
计算的环境影响包括数据中心的能耗、电子废弃物以及云服务的碳足迹。可持续实践包括虚拟化、高效冷却以及硬件的循环经济原则。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图