Data Structures Core Concepts & Common Exam Questions | 数据结构核心要点与常见题型

📚 Data Structures Core Concepts & Common Exam Questions | 数据结构核心要点与常见题型

Data structures are the backbone of computer science. They define how data is organised, stored, and manipulated in memory, and every algorithm runs on top of some data structure. This article covers the essential data structures you need to master for your A Level or IGCSE Computer Science exam, along with typical exam questions and how to approach them.

数据结构是计算机科学的基石。它定义了数据在内存中如何组织、存储和操作，每一个算法都运行在某种数据结构之上。这篇文章将覆盖你在A Level或IGCSE计算机科学考试中必须掌握的核心数据结构，以及典型题型和解题思路。

1. What Is a Data Structure? | 什么是数据结构

A data structure is a systematic way of organising data so that it can be used efficiently. Different structures are suited to different tasks: some optimise for fast searching, others for quick insertion or deletion. Understanding the strengths and trade-offs of each structure is a key exam skill.

数据结构是系统地组织数据以便高效使用的方式。不同的结构适合不同的任务：有些优化快速查找，有些优化快速插入或删除。理解每种结构的优势和权衡是关键的考试技能。

Linear structures: arrays, linked lists, stacks, queues. | 线性结构：数组、链表、栈、队列。
Non-linear structures: trees, graphs. | 非线性结构：树、图。
Abstract data types (ADTs): a theoretical model defined by its behaviour, such as a stack or queue.

抽象数据类型（ADT）是由其行为定义的理论模型，例如栈或队列。ADT 关注”做什么”而不是”怎么做”，而具体的数据结构实现则关心”怎么做”。

2. Arrays | 数组

An array is a contiguous block of memory holding elements of the same type, each identified by an index. Random access is constant time O(1) because the memory address is computed directly from the index.

数组是一块连续的内存区域，存放相同类型的元素，每个元素由索引标识。因为内存地址可以直接从索引计算得出，所以随机访问的时间复杂度为常数时间 O(1)。

Address of element i = Base Address + i × Size of element

元素 i 的地址 = 基地址 + i × 元素大小。这一公式在考试中常用于计算数组元素的内存位置。

Advantages: fast access, cache-friendly, low memory overhead. | 优点：访问快、缓存友好、内存开销低。
Disadvantages: fixed size, expensive insertion/deletion in the middle. | 缺点：大小固定，中间插入/删除开销大。

Common exam question: A 1D array of 20 integers starts at memory address 1000. Each integer occupies 4 bytes. What is the address of the 15th element?

常见题型：一个包含20个整数的数组从内存地址1000开始，每个整数占4字节。第15个元素的地址是多少？

1000 + 14 × 4 = 1056. (Index 14 because arrays are 0-based.)

1000 + 14 × 4 = 1056。（因为数组从0开始编号，所以是第14个索引。）

3. Linked Lists | 链表

A linked list is a linear data structure where each node contains data and a pointer (reference) to the next node. Nodes are not stored contiguously; they are scattered in memory and linked by pointers.

链表是一种线性数据结构，每个节点包含数据和指向下一个节点的指针（引用）。节点不连续存储，而是分布在内存各处，通过指针连接起来。

Singly linked list: each node has one ‘next’ pointer. | 单向链表：每个节点有一个”下一个”指针。
Doubly linked list: each node has both ‘next’ and ‘previous’ pointers. | 双向链表：每个节点有”下一个”和”上一个”指针。
Circular linked list: the last node points back to the first. | 循环链表：最后一个节点指向第一个节点。

Insertion and deletion at the head of a linked list are O(1). Searching and accessing an element by index are O(n) because you must traverse from the head.

在链表头部插入和删除是 O(1) 时间。按索引搜索和访问元素是 O(n) 时间，因为必须从头开始遍历。

Common exam question: Draw a diagram to show the effect of inserting a new node X between nodes A and B in a singly linked list. State which pointers are changed.

常见题型：画出在单向链表中节点 A 和 B 之间插入新节点 X 的示意图，并指出哪些指针发生了改变。

Solution: ① Point X.next to B. ② Point A.next to X. The order matters: if you change A.next first, you lose the reference to B.

解答：① 将 X.next 指向 B。② 将 A.next 指向 X。顺序很重要：如果先改 A.next，就会丢失对 B 的引用。

4. Stacks | 栈

A stack is a Last-In-First-Out (LIFO) structure. The last element added is the first to be removed. Core operations are push (add to top) and pop (remove from top), plus peek (view the top without removing).

栈是一种后进先出（LIFO）结构。最后添加的元素最先被移除。核心操作是 push（压入栈顶）和 pop（弹出栈顶），以及 peek（查看栈顶但不移除）。

Time complexity: push O(1), pop O(1), peek O(1)

时间复杂度：push O(1)、pop O(1)、peek O(1)

Real-world applications: undo/redo in editors, browser back buttons, function call stacks.
实际应用：编辑器中的撤销/重做、浏览器的后退按钮、函数调用栈。

Common exam question: A stack initially contains [5, 2, 8] (8 is at the top). Perform: pop, push 3, pop, push 9. What is the final content of the stack?

常见题型：栈初始内容为 [5, 2, 8]（8在栈顶）。执行：pop、push 3、pop、push 9。栈的最终内容是什么？

Solution: After pop → [5, 2]. Push 3 → [5, 2, 3]. Pop → [5, 2]. Push 9 → [5, 2, 9]. Final stack: [5, 2, 9] with 9 at the top.

解答：pop后 → [5, 2]。push 3 → [5, 2, 3]。pop → [5, 2]。push 9 → [5, 2, 9]。最终栈：[5, 2, 9]，9在栈顶。

5. Queues | 队列

A queue is a First-In-First-Out (FIFO) structure. Elements are added at the rear (enqueue) and removed from the front (dequeue). This models real-world waiting lines.

队列是一种先进先出（FIFO）结构。元素从队尾加入（入队 enqueue），从队首移除（出队 dequeue）。这模拟了现实世界中的排队场景。

“Static queue” implemented with an array has a problem: as elements are dequeued from the front, the empty spaces cannot be reused unless you shift all elements. A circular queue solves this by wrapping around to the front of the array.

用数组实现的”静态队列”有一个问题：当元素从队首出队后，空出的位置无法复用，除非将所有元素前移。循环队列通过回绕到数组前端来解决这个问题。

Applications: print job scheduling, CPU process scheduling, buffering in networking.
应用：打印任务调度、CPU进程调度、网络中的缓冲处理。

Common exam question (circular queue): A circular queue of size 6 uses two pointers: front = 2 and rear = 4. Enqueue 3 more elements. Show the queue state and state whether the queue is full.

常见题型（循环队列）：大小为6的循环队列，front = 2，rear = 4。再入队3个元素。画出队列状态并判断队列是否已满。

Solution: Enqueue 1st → rear = 5. Enqueue 2nd → rear = 0. Enqueue 3rd → rear = 1. Now front = 2, rear = 1. The queue has 5 elements (indices 2,3,4,5,0). Not yet full. The full condition for a circular queue with one empty slot reserved is rear + 1 = front (mod size), i.e., if another enqueue occurs, rear would become 2 = front, meaning full.

解答：入队第1个 → rear = 5。入队第2个 → rear = 0。入队第3个 → rear = 1。此时 front = 2，rear = 1，队列中有5个元素（索引2,3,4,5,0），尚未满。循环队列预留一个空位的满条件为 rear + 1 = front（对size取模），即如果再入队一个元素，rear 变为 2 = front，即满。

6. Binary Trees | 二叉树

A binary tree is a hierarchical structure where each node has at most two children, called left and right. A binary search tree (BST) maintains ordering: the left subtree of a node contains only values less than the node, and the right subtree only values greater than the node.

二叉树是一种层次结构，每个节点最多有两个孩子，称为左孩子和右孩子。二叉搜索树（BST）维持有序性：节点的左子树只包含小于该节点的值，右子树只包含大于该节点的值。

Traversal methods (遍历方法):

Method 方法	Order 访问顺序	Typical use 典型用途
Preorder 前序	Root → Left → Right 根→左→右	Copying a tree 复制树
Inorder 中序	Left → Root → Right 左→根→右	Output values in sorted order 按序输出BST值
Postorder 后序	Left → Right → Root 左→右→根	Deleting a tree 删除树

For a balanced BST, search, insertion and deletion are all O(log n). For a skewed BST (worst case, e.g., inserting sorted data), these degrade to O(n).

对于平衡BST，查找、插入和删除都是 O(log n)。对于倾斜BST（最坏情况，例如插入已排序的数据），这些操作退化为 O(n)。

Common exam question: Show the result of inserting values 40, 20, 60, 10, 30, 50, 70 into an empty BST, then perform an inorder traversal.

常见题型：将值 40, 20, 60, 10, 30, 50, 70 插入空BST中，然后进行中序遍历。

Solution: Inorder traversal of a BST always outputs values in ascending order: 10, 20, 30, 40, 50, 60, 70. No need to draw the tree if you know this property.

解答： BST的中序遍历总是按升序输出值：10, 20, 30, 40, 50, 60, 70。知道这条性质就无需画树。

7. Graphs | 图

A graph consists of a set of vertices (nodes) and a set of edges connecting pairs of vertices. Graphs can be directed or undirected, weighted or unweighted. The two main representations are the adjacency matrix and the adjacency list.

图由一组顶点（节点）和一组连接顶点对的边组成。图可以是有向或无向的、加权或无权重的。两种主要表示方式是邻接矩阵和邻接表。

Representation 表示法	Space 空间	Check edge 边查询	Find neighbours 找邻居
Adjacency matrix 邻接矩阵	O(V²)	O(1)	O(V)
Adjacency list 邻接表	O(V+E)	O(degree) O(度)	O(degree) O(度)

The adjacency matrix is better for dense graphs where edge checks are frequent; the adjacency list is more memory-efficient for sparse graphs.

邻接矩阵更适合需要频繁查边的稠密图；邻接表对稀疏图更节省内存。

Common exam question: Draw the adjacency matrix for the directed graph with edges: A→B, A→C, B→C, C→A.

常见题型：画出有向图 A→B、A→C、B→C、C→A 的邻接矩阵。

Solution (rows = source, columns = destination):

	A	B	C
A	0	1	1
B	0	0	1
C	1	0	0

解答：行表示起点，列表示终点，有边则填1，无边填0。

8. Sorting Algorithms | 排序算法

Sorting arranges elements in a defined order (ascending or descending). Exam boards commonly test bubble sort, insertion sort, and merge sort. You must know their time complexities and be able to trace them.

排序将元素按特定顺序排列（升序或降序）。考试局常考冒泡排序、插入排序和归并排序。你必须知道它们的时间复杂度并能够手动追踪执行过程。

Algorithm 算法	Best 最优	Average 平均	Worst 最差	Stable 稳定?
Bubble sort 冒泡	O(n)	O(n²)	O(n²)	Yes 是
Insertion sort 插入	O(n)	O(n²)	O(n²)	Yes 是
Merge sort 归并	O(n log n)	O(n log n)	O(n log n)	Yes 是

A stable sort preserves the relative order of equal elements. Merge sort requires O(n) additional space for merging; bubble and insertion sort sort in place.

稳定排序保持相等元素的相对顺序。归并排序需要 O(n) 的额外空间用于合并；冒泡排序和插入排序是原地排序。

Common exam question: Trace two passes of bubble sort on the array [7, 2, 9, 1, 5].

常见题型：对数组 [7, 2, 9, 1, 5] 手动追踪冒泡排序的前两趟。

Solution: Pass 1: compare 7 & 2 → swap [2,7,9,1,5]; 7 & 9 no swap; 9 & 1 → swap [2,7,1,9,5]; 9 & 5 → swap [2,7,1,5,9]. Pass 2: 2 & 7 no swap; 7 & 1 → swap [2,1,7,5,9]; 7 & 5 → swap [2,1,5,7,9].

解答：第1趟：比较7和2 → 交换得 [2,7,9,1,5]；7和9不交换；9和1 → 交换得 [2,7,1,9,5]；9和5 → 交换得 [2,7,1,5,9]。第2趟：2和7不交换；7和1 → 交换得 [2,1,7,5,9]；7和5 → 交换得 [2,1,5,7,9]。

9. Searching Algorithms | 查找算法

Linear search and binary search are the two most commonly examined searching algorithms. Linear search scans every element from start to finish; binary search repeatedly halves a sorted array.

线性查找和二分查找是两个最常考的查找算法。线性查找从头到尾逐个扫描元素；二分查找反复对有序数组进行折半。

Linear search: O(n) time, works on unsorted arrays. | 线性查找：O(n) 时间，适用于未排序数组。
Binary search: O(log n) time, requires a sorted array. | 二分查找：O(log n) 时间，要求数组已排序。

Binary search pseudocode summary: set low = 0, high = n−1. While low ≤ high: calculate mid = (low + high) ÷ 2. If target = a[mid], return mid. If target < a[mid], set high = mid − 1. Otherwise set low = mid + 1.

二分查找伪代码摘要：令 low = 0，high = n−1。当 low ≤ high 时：计算 mid = (low + high) ÷ 2。如果目标等于 a[mid]，返回 mid。如果目标小于 a[mid]，令 high = mid − 1。否则令 low = mid + 1。

Common exam question: Use binary search to find the value 32 in the sorted array [2, 5, 9, 14, 21, 32, 47, 58]. List the mid indices checked.

常见题型：使用二分查找在有序数组 [2, 5, 9, 14, 21, 32, 47, 58] 中查找值32。列出每次检查的mid索引。

Solution: n = 8, initially low = 0, high = 7. mid = (0+7)÷2 = 3 → a[3] = 14, 32 > 14 → low = 4. mid = (4+7)÷2 = 5 → a[5] = 32, found! Indices checked: 3, 5.

解答： n=8，初始 low=0，high=7。mid=(0+7)÷2=3 → a[3]=14，32大于14 → low=4。mid=(4+7)÷2=5 → a[5]=32，找到了！检查的索引：3, 5。

10. Exam Strategy: Common Pitfalls | 应试策略：常见误区

Examiners repeatedly see the same mistakes in data structure questions. Avoiding these will earn you easy marks:

考官反复看到数据机构题目中的相同错误。避免这些错误可以轻松得分：

Forgetting that arrays are 0-indexed in most programming contexts (list indexing errors). | 忘记大多数编程场景中数组从0开始编号（导致索引错误）。
Using a queue algorithm on a stack problem, or vice versa (confusing FIFO with LIFO). | 在栈问题中使用队列算法，或反之（混淆FIFO与LIFO）。
Applying binary search to an unsorted array. | 对未排序数组使用二分查找。
Omitting the base case when tracing recursion on a tree. | 在树上做递归追踪时遗漏基本情况。
Confusing the time complexity of insertion for arrays vs linked lists: arrays O(n) for middle insertion due to shifting; linked lists O(1) if the position pointer is known.

混淆数组和链表插入的时间复杂度：数组在中间插入需要移动元素所以是O(n)；链表如果已知位置指针则是O(1)。

Always state the time complexity of the operation you implement, and justify your choice of data structure for a given scenario by mentioning the time complexity of key operations.

始终说明你实现的操作的时间复杂度，并通过提及关键操作的时间复杂度来证明在给定场景下选择某个数据结构的合理性。

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

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

Data Structures Core Concepts & Common Exam Questions | 数据结构核心要点与常见题型