Data Structures: Core Concepts and Common Question Types | 数据结构：核心概念与常见题型

📚 Data Structures: Core Concepts and Common Question Types | 数据结构：核心概念与常见题型

Data structures are the fundamental building blocks of computer science. They determine how data is stored, organized, and manipulated, which directly affects the efficiency of algorithms. Mastering core concepts such as arrays, linked lists, stacks, queues, trees, graphs, and hash tables is essential for solving both academic and real-world programming problems.

数据结构是计算机科学的基础构件。它们决定了数据如何存储、组织和操作，直接影响算法的效率。掌握数组、链表、栈、队列、树、图和哈希表等核心概念，对于解决学术题目和实际编程问题都至关重要。

---

1. Abstract Data Types and Data Structures | 抽象数据类型与数据结构

An abstract data type (ADT) is a high-level description of a set of operations on data, independent of how those operations are implemented. For example, a stack ADT specifies push, pop, and peek operations, but it does not dictate whether the stack is implemented using an array or a linked list. A data structure, on the other hand, is the concrete implementation of an ADT.

抽象数据类型（ADT）是对数据上一组操作的高层描述，与这些操作的具体实现方式无关。例如，栈 ADT 规定了 push（入栈）、pop（出栈）em> 和 peek（查看栈顶） 操作，但并不规定栈是用数组还是链表实现。而数据结构则是 ADT 的具体实现。

• ADT focuses on “what” operations are supported; a data structure focuses on “how” they are implemented.

  ADT 关注“支持什么”操作；数据结构关注“如何实现”这些操作。

• Common ADTs include list, stack, queue, priority queue, dictionary, and set.

  常见 ADT 包括列表、栈、队列、优先队列、字典和集合。

ADT = logical model + operations; Data Structure = physical storage + algorithms

ADT = 逻辑模型 + 操作；数据结构 = 物理存储 + 算法

---

2. Time and Space Complexity | 时间与空间复杂度

Complexity analysis estimates how the running time or memory usage of an algorithm grows with the input size n. Big-O notation is used to describe the worst-case upper bound. For example, accessing an array element by index is O(1), while searching an unsorted array is O(n).

复杂度分析用于估算算法运行时间或内存使用量随输入规模 n 增长的情况。大 O 符号用来描述最坏情况下的上界。例如，按索引访问数组元素是 O(1)，而搜索无序数组是 O(n)。

Common complexity orders are:

常见的复杂度级别有：

• O(1) – constant time: array indexing, hash table lookup in the average case.

  O(1) – 常数时间：数组索引，哈希表平均情况查找。

• O(log n) – logarithmic time: binary search in a sorted array.

  O(log n) – 对数时间：有序数组中的二分查找。

• O(n) – linear time: scanning a list, linear search.

  O(n) – 线性时间：遍历列表，线性查找。

• O(n log n) – linearithmic time: efficient sorting algorithms like mergesort and heapsort.

  O(n log n) – 线性对数时间：高效排序算法，如归并排序和堆排序。

• O(n²) – quadratic time: nested loops, simple sorting like bubble sort.

  O(n²) – 平方时间：嵌套循环，简单排序如冒泡排序。

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

---

3. Arrays and Strings | 数组与字符串

An array is a contiguous block of memory that stores elements of the same type. It supports random access via indexing, making the access time O(1). However, inserting or deleting an element inside an array requires shifting subsequent elements, giving O(n) time complexity. Strings are often implemented as character arrays, with the additional challenge of handling terminators or lengths.

数组是一块连续的内存区域，存储相同类型的元素。它通过索引支持随机访问，访问时间为 O(1)。然而，在数组中间插入或删除元素需要移动后续元素，时间复杂度为 O(n)。字符串通常实现为字符数组，并且需要额外处理终止符或长度信息。

• Static arrays have fixed size; dynamic arrays (e.g., Python list, Java ArrayList) grow automatically, but amortized insertion at the end is O(1).

  静态数组大小固定；动态数组（如 Python 的 list、Java 的 ArrayList）会自动扩容，但在末尾插入的摊还时间复杂度为 O(1)。

• String concatenation in a loop can be O(n²) if strings are immutable; use buffers or lists instead.

  如果字符串是不可变的，在循环中拼接字符串可能达到 O(n²)；应使用缓冲区或列表。

Common exam questions involve finding subarrays, two-pointer techniques, and rotating matrices.

常见题型包括查找子数组、双指针技巧和矩阵旋转。

---

4. Linked Lists | 链表

A linked list is a linear data structure where each node contains data and a reference (pointer) to the next node. Unlike arrays, linked lists do not require contiguous memory. Insertion and deletion at a known position are O(1) after updating pointers, but accessing an element by position requires traversal and therefore takes O(n).

链表是一种线性数据结构，每个节点包含数据和对下一个节点的引用（指针）。与数组不同，链表不需要连续内存。在已知位置插入和删除只需修改指针，时间复杂度为 O(1)；但按位置访问元素需要遍历，因此为 O(n)。

• Singly linked list: each node has a single next pointer.

  单链表：每个节点只有一个 next 指针。

• Doubly linked list: each node has both prev and next pointers, supporting easy reverse traversal.

  双链表：每个节点同时具有 prev 和 next 指针，便于反向遍历。

• Circular linked list: the last node points back to the head, creating a cycle.

  循环链表：最后一个节点指向头节点，形成环。

Common exam tasks: reverse a linked list, detect a cycle (Floyd’s tortoise and hare), and merge two sorted lists.

常见考题：反转链表、检测环（弗洛伊德龟兔算法）、合并两个有序链表。

---

5. Stacks and Queues | 栈与队列

Stacks and queues are restricted linear structures. A stack follows Last-In-First-Out (LIFO): push adds to the top, pop removes from the top. A queue follows First-In-First-Out (FIFO): enqueue adds to the rear, dequeue removes from the front. Both operations can be implemented in O(1) using arrays or linked lists.

栈和队列是受限的线性结构。栈遵循后进先出（LIFO）：push 在栈顶添加元素，pop 从栈顶移除元素。队列遵循先进先出（FIFO）：enqueue 在队尾添加元素，dequeue 从队头移除元素。这两种操作都可以用数组或链表在 O(1) 时间内实现。

• A stack is used in function call recursion, expression evaluation, and undo operations.

  栈用于函数调用的递归、表达式求值和撤销操作。

• A queue is used in breadth-first search (BFS), buffering, and scheduling tasks.

  队列用于广度优先搜索（BFS）、缓冲和任务调度。

• A deque (double-ended queue) allows insertion and deletion at both ends.

  双端队列（deque） 允许在两端进行插入和删除。

Stack: LIFO → top; Queue: FIFO → front + rear

栈：LIFO → 栈顶；队列：FIFO → 队头 + 队尾

Typical problems include checking balanced parentheses, implementing queues using stacks, and evaluating postfix expressions.

典型问题包括检查括号匹配、用栈实现队列、以及计算后缀表达式。

---

6. Trees and Binary Trees | 树与二叉树

A tree is a hierarchical structure with a root node and child nodes. A binary tree is a special tree where each node has at most two children. Binary trees are often represented using nodes with left and right pointers.

树是一种层级结构，由根节点和子节点组成。二叉树是一种特殊的树，其中每个节点最多有两个子节点。二叉树通常使用包含 left 和 right 指针的节点表示。

• Tree height: the number of edges on the longest root-to-leaf path.

  树的高度：从根到叶子最长路径上的边数。

• Full binary tree: every node has either 0 or 2 children.

  满二叉树：每个节点要么有 0 个要么有 2 个子节点。

• Complete binary tree: all levels are fully filled except possibly the last level, which is filled left to right.

  完全二叉树：除最后一层外，每一层都填满，且最后一层从左到右填充。

Common traversals are:

常见的遍历方式有：

• Preorder: root → left subtree → right subtree

  前序遍历：根 → 左子树 → 右子树

• Inorder: left subtree → root → right subtree (produces sorted order in a BST)

  中序遍历：左子树 → 根 → 右子树（在二叉搜索树中得到有序序列）

• Postorder: left subtree → right subtree → root

  后序遍历：左子树 → 右子树 → 根

Preorder: root → left → right; Inorder: left → root → right; Postorder: left → right → root

前序：根 → 左 → 右；中序：左 → 根 → 右；后序：左 → 右 → 根

---

7. Binary Search Trees and Heaps | 二叉搜索树与堆

A binary search tree (BST) is a binary tree where for each node, all nodes in the left subtree have smaller keys, and all nodes in the right subtree have larger keys. In a balanced BST, search, insertion, and deletion all run in O(log n) time. However, if the tree becomes skewed, these operations degrade to O(n).

二叉搜索树（BST）是一种二叉树，其中每个节点左子树中的所有节点键值较小，右子树中的所有节点键值较大。在平衡 BST 中，查找、插入和删除操作的时间复杂度均为 O(log n)。然而，如果树变得倾斜，这些操作会退化为 O(n)。

A heap is a complete binary tree that satisfies the heap property. In a max-heap, each node is greater than or equal to its children; in a min-heap, each node is smaller than or equal to its children. Heaps are used to implement priority queues.

堆是一种满足堆性质的完全二叉树。在最大堆中，每个节点都大于或等于其子节点；在最小堆中，每个节点都小于或等于其子节点。堆用于实现优先队列。

• BST inorder traversal yields sorted order.

  BST 的中序遍历可得到有序序列。

• Heap insertion: add at the end and bubble up; heap deletion: remove the root and bubble down; both O(log n).

  堆插入：在末尾添加并上浮；堆删除：移除堆顶并下沉；两者均为 O(log n)。

• The `Heap` data structure enables heap sort and a fast way to find k-largest or k-smallest elements.

  堆数据结构支持堆排序，并能快速查找第 k 大或第 k 小的元素。

---

8. Graphs | 图

A graph G = (V, E) consists of a set of vertices V and edges E. Graphs can be directed or undirected, weighted or unweighted. They are used to model networks, social connections, maps, and dependency relationships.

图 G = (V, E) 由顶点集合 V 和边集合 E 组成。图可以是有向或无向的，加权或无权重的。它们用于建模网络、社交关系、地图和依赖关系。

• Adjacency matrix: O(V²) space; fast edge lookup O(1).

  邻接矩阵：空间 O(V²)；边查找 O(1)。

• Adjacency list: O(V + E) space; efficient for sparse graphs; edge lookup O(degree).

  邻接表：空间 O(V + E)；适合稀疏图；边查找 O(度)。

Important algorithms include:

重要算法包括：

• Depth-First Search (DFS) – uses a stack (or recursion), explores as far as possible along each branch.

  深度优先搜索（DFS） – 使用栈（或递归），沿着每条分支尽可能深地探索。

• Breadth-First Search (BFS) – uses a queue, explores neighbor by neighbor; finds shortest path in unweighted graphs.

  广度优先搜索（BFS） – 使用队列，逐层探索邻居；在无权图中可找到最短路径。

• Dijkstra’s algorithm – for shortest paths in weighted non-negative graphs.

  Dijkstra 算法 – 用于非负权重图中的最短路径。

DFS = stack / recursion; BFS = queue

DFS = 栈 / 递归；BFS = 队列

Common exam tasks include detecting cycles, topological sorting, and computing connected components.

常见考题包括检测环、拓扑排序和计算连通分量。

---

9. Hash Tables | 哈希表

A hash table stores key-value pairs and provides O(1) average-time lookups. A hash function maps a key to an index in an array. Collisions, where two keys map to the same index, are resolved using chaining (linked list per bucket) or open addressing (probing).

哈希表存储键值对，平均时间复杂度为 O(1)。哈希函数将键映射到数组的某个索引。当两个键映射到同一个索引时发生冲突，解决方法包括链地址法（每个桶用链表）和开放寻址法（探测）。

• Good hash functions distribute keys uniformly to reduce collisions.

  好的哈希函数使键均匀分布以减少冲突。

• Load factor α = number of entries / table size. When α becomes too high, rehashing (resizing) is needed.

  装载因子 α = 条目数 / 表大小。当 α 过高时，需要重新哈希（扩容）。

• Worst-case time is O(n) when many collisions occur, but the average case is O(1).

  当发生大量冲突时，最坏情况时间为 O(n)，但平均情况为 O(1)。

Hash tables are ideal for dictionaries, caches, and membership testing.

哈希表非常适合实现字典、缓存和成员检查。

---

10. Sorting Algorithms and Their Complexity | 排序算法及其复杂度

Sorting is a classic topic in exams. You should know the time and space complexity of different sorting algorithms, as well as their stability and best-case behavior.

排序是考试中的经典主题。你应该知道不同排序算法的时间与空间复杂度，以及它们的稳定性和最坏情况表现。

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No (typically)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Mergesort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No (typically)
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	No

Quicksort is usually fastest in practice but has a worst-case of O(n²) when pivot choices are poor. Mergesort guarantees O(n log n) but uses extra space. Insertion sort is efficient for small or nearly sorted data.

快速排序在实践中通常最快，但若基准选择不佳，最坏情况为 O(n²)。归并排序保证 O(n log n) 但使用额外空间。插入排序对于小规模或近似有序的数据非常高效。

---

11. Common Exam Questions and Problem-Solving Strategies | 常见题型与解题策略

Exam questions on data structures often test both theoretical knowledge and coding ability. You may be asked to trace an algorithm, determine its complexity, implement a data structure, or solve a problem using an appropriate structure.

数据结构考题通常同时考查理论知识和编码能力。你可能会被要求模拟算法运行过程、确定复杂度、实现某种数据结构，或使用合适的数据结构解决问题。

• Identify the underlying structure: If the problem needs LIFO behavior, think of a stack; if FIFO, use a queue; if fast lookup, consider a hash table.

  识别底层结构： 如果问题需要后进先出行为，想到栈；如果是先进先出，用队列；如果需要快速查找，考虑哈希表。

• Analyze constraints: If n is large, an O(n²) solution may be too slow; aim for O(n log n) or O(n).

  分析约束： 如果 n 很大，O(n²) 解决方案可能太慢；应追求 O(n log n) 或 O(n)。

• Practice traversals and pointer operations: Linked lists and trees often require careful handling of pointers and recursive calls.

  练习遍历和指针操作： 链表和树通常需要仔细处理指针和递归调用。

• Use edge cases: Empty structures, single-element structures, and cyclic structures are common traps.

  考虑边缘情况： 空结构、单元素结构和循环结构是常见陷阱。

For example, to check balanced parentheses, use a stack: if a closing bracket does not match the stack top, the string is invalid. To merge two sorted linked lists, use a dummy head and a comparison pointer.

例如，检查括号匹配时使用栈：如果右括号与栈顶不匹配，则字符串无效。要合并两个有序链表，可以使用哑结点和比较指针。

Choose the right structure → analyze complexity → handle edge cases

选择合适结构 → 分析复杂度 → 处理边界情况

---

12. Study Tips for Data Structure Exams | 数据结构备考建议

To excel in data structure exams, you should not only memorize definitions but also practice writing code and tracing examples by hand. Understanding how data structures are implemented is as important as knowing when to use them.

要在数据结构考试中取得好成绩，你不仅需要记忆定义，还要练习手写代码和手动模拟示例。理解数据结构的实现方式与知道何时使用它们同样重要。

• Draw diagrams of linked lists, trees, and graph traversals to visualize the operations.

  画出链表、树和图遍历的图示，帮助可视化操作过程。

• Rewrite classic algorithms from memory, such as DFS, BFS, binary search, and sorting routines.

  凭记忆重写经典算法，例如 DFS、BFS、二分查找和排序例程。

• Solve past paper questions under time pressure and review your mistakes.

  在时间压力下完成历年真题，并复习你的错误。

• Learn to compare trade-offs between time complexity, space complexity, and ease of implementation.

  学会比较时间复杂度、空间复杂度和实现难度之间的权衡。

Master these core concepts and you will be well prepared for both multiple-choice and code-writing questions.

掌握这些核心概念后，你将为选择题和代码编写题做好充分准备。

---

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

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