B2.2.1 · Data structures
B2.2.1 · 数据结构
Comparing static and dynamic data structures
比较静态与动态数据结构
Every data structure makes the same promise: somewhere to keep a collection of values. The real difference is what happens to that promise the moment the collection needs to grow.
每一种数据结构都做出同样的承诺:提供一个地方来存放一组数值。真正的差异在于,当这组数值需要增长时,这个承诺会发生什么。
Explainer
讲解
Fairbridge Library has 30 numbered study desks, bolted down, the same 30 every single day of the year. The queue for the library's one copy of this term's set novel is nothing like that: some mornings it's empty, some afternoons it's eleven names long, and it never has a fixed length anyone agreed on in advance. Both are "a collection of things", but the desks and the queue are managed completely differently underneath, and that difference is exactly what this statement compares.
费尔布里奇图书馆有 30 张编号自习桌,固定在地上,一年到头都是同样的 30 张。图书馆本学期指定小说唯一一本副本的预约队列却完全不同:有些早晨空无一人,有些下午却排到十一个名字,而且它从来没有谁事先约定好的固定长度。两者都是"一组事物的集合",但桌子和队列在底层的管理方式却截然不同,而这正是本条考纲陈述所比较的内容。
A static data structure has a fixed size decided when it is created. That size never changes for as long as the structure exists, and its elements sit in one contiguous block of memory, reserved all at once.
静态数据结构的大小在创建时就已确定。只要该结构存在,这个大小就永远不会改变,其元素存放在一整块连续的内存空间中,一次性预留完成。
A dynamic data structure has no fixed size. It can grow or shrink while the program is running, and its elements are typically chained together in memory rather than sitting in one unbroken block.
动态数据结构没有固定的大小。它可以在程序运行期间增长或缩小,其元素通常在内存中以链接的方式相连,而不是存放在一整块连续的空间中。
Explainer
讲解
How memory is actually managed
内存究竟是如何管理的
The generator's own scope for this statement names two specific mechanisms, not just the two labels.
这条考纲陈述所界定的范围明确指出了两种具体机制,而不仅仅是这两个名称本身。
Memory allocation. A static structure reserves its entire block of memory upfront, at the moment it's created, all in one place, one after another. A dynamic structure allocates memory piece by piece, as each new element is added, and those pieces don't have to sit next to each other at all, they're linked by reference instead.
内存分配。静态结构在创建的那一刻就预先一次性保留其整块内存,所有空间连续排列在同一处。动态结构则是逐块分配内存,每添加一个新元素就分配一次,这些内存块完全不必彼此相邻,而是通过引用相互链接。
Resizing. A static structure cannot resize itself, full stop, it was given one size and that's permanent. A dynamic structure resizes by allocating a new piece of memory somewhere else and linking it in (or, in some implementations, allocating an entirely new larger block and copying everything across), which is real work the static structure never has to do.
调整大小。静态结构完全无法自行调整大小,它被赋予了一个大小,而这个大小是永久固定的。动态结构通过在别处分配一块新内存并将其链接进来(或者在某些实现中,分配一整块更大的新内存并将所有内容复制过去)来调整大小,这是静态结构从来不需要做的实际工作。
Fairbridge Library's desks make this concrete. Desk 12 sits at a fixed, calculable distance from desk 1, so a static array holding them can jump straight there with one calculation. The reservation queue has no such shortcut: it's chained together one link at a time, so finding the 12th name in it means following the chain from the front, checking each link in turn, there's no calculation that skips ahead.
费尔布里奇图书馆的自习桌让这一点变得具体。12 号桌与 1 号桌之间的距离是固定且可计算的,因此存放这些桌子的静态数组只需一次计算就能直接跳转过去。预约队列则没有这样的捷径:它是一节一节链接起来的,因此要找到队列中的第 12 个名字,就必须从队首开始沿着链条逐一查找,没有任何计算能够跳过中间的环节。
Explainer
讲解
Weighed on speed, memory usage and flexibility
从速度、内存使用与灵活性三方面权衡
These are the three factors the statement names explicitly. Neither structure wins on all three at once, that trade-off is the entire point of comparing them.
这是本条考纲陈述明确指出的三个因素。没有任何一种结构能同时在这三方面都占优,而这种取舍正是比较它们的意义所在。
Real example: Fairbridge Library's 30 study desks, the same fixed number all year round.
真实例子:费尔布里奇图书馆的 30 张自习桌,全年数量固定不变。
Advantage
优点
- Fast, direct access (jump straight to any element by one calculation, no following a chain)
- 快速、直接的访问 (通过一次计算就能直接跳转到任意元素,无需沿链查找)
- No resizing overhead (the structure never has to pause and reallocate memory mid-program)
- 无需调整大小的开销 (该结构在程序运行期间永远不需要暂停并重新分配内存)
Disadvantage
缺点
- Wasted or insufficient memory (guess too high and space sits unused; guess too low and there's nowhere left to put a new element)
- 内存浪费或不足 (预估过高,空间就会闲置浪费;预估过低,就没有空间存放新元素)
- No flexibility (the size decided at creation is the size for the structure's entire life)
- 缺乏灵活性 (创建时确定的大小,就是该结构一生的大小)
Real example: the reservation queue for the library's one copy of the set novel, some days empty, some days eleven names long.
真实例子:图书馆指定小说唯一一本副本的预约队列,有些天空无一人,有些天却排到十一个名字。
Advantage
优点
- Efficient memory use (only ever holds as much memory as it currently needs, nothing is reserved and left empty)
- 内存使用高效 (始终只占用当前实际需要的内存量,不会预留后闲置)
- Genuine flexibility (grows or shrinks freely as the real, unpredictable size becomes known)
- 真正的灵活性 (能随着实际、不可预测的大小逐渐明朗而自由增长或缩小)
Disadvantage
缺点
- Slower access (no direct jump to an arbitrary element, reaching it usually means following the chain from the start)
- 访问速度较慢 (无法直接跳转到任意元素,通常必须从头沿链查找才能到达)
- Resizing has a real cost (allocating new memory and linking or copying takes actual time, paid every time the structure grows)
- 调整大小有真实成本 (分配新内存并进行链接或复制需要实际耗费时间,每次结构增长都要付出这一代价)
Worked example
示例讲解
Two scenarios, two opposite verdicts
两个情境,两种相反的结论
The right structure is never fixed in the abstract, it depends entirely on what the situation actually needs. Two real cases, weighed on the same three factors, reaching opposite answers.
正确的结构选择从来不是抽象固定的,它完全取决于具体情境的实际需求。以下两个真实案例,用同样的三个因素来权衡,却得出了相反的结论。
An exam seating chart. A school hall seats exactly 120 students for a fixed exam session, no more, no fewer, and that number is confirmed the day before. Nobody is added mid-exam. Static is the right call: the size is known and fixed in advance, direct fast access matters (checking any seat instantly), and the "no flexibility" disadvantage costs nothing, because the size was never going to change anyway.
考场座位表。某学校礼堂在一场固定的考试中恰好容纳 120 名学生,不多也不少,这个数字在考前一天就已确认。考试过程中不会有人中途加入。选择静态结构才是正确的:大小在事前就已知且固定,快速的直接访问很重要(能立即查看任意座位),而"缺乏灵活性"这一缺点根本不构成任何代价,因为这个大小本来就不会改变。
A hospital's overnight A&E waiting list. Patients arrive at completely unpredictable times, all night, in numbers nobody can forecast in advance. Dynamic is the right call: guessing a fixed size upfront would mean either wasted memory reserved for patients who never arrive, or, far worse, no room left for a patient who does. The slower access cost is a fair trade against the alternative of the structure simply running out of room.
医院急诊室的通宵候诊名单。患者在整个夜间以完全无法预测的时间到达,人数也没有人能够提前预估。选择动态结构才是正确的:如果事先猜测一个固定大小,要么会为始终没有出现的患者浪费预留的内存,要么更糟,没有空间留给真正到来的患者。较慢的访问速度,相较于结构直接耗尽空间的后果,是一笔公平的代价。
Same three factors, speed, memory usage, flexibility, applied both times. The verdict flips because the real-world constraint flips: a truly fixed, known size favours static; a genuinely unpredictable, changing size favours dynamic.
同样的三个因素,速度、内存使用、灵活性,在两次情境中都被应用。结论之所以相反,是因为现实世界的约束条件相反了:真正固定、已知的大小有利于静态结构;真正不可预测、不断变化的大小则有利于动态结构。
Check your understanding
检验你的理解
A program needs to store an unknown, changing number of live sensor readings that arrive at random times throughout the day. Which structure fits, and why?
一个程序需要存储数量未知且不断变化的实时传感器读数,这些读数在一天中随机时间到达。哪种结构更合适,为什么?
Common pitfall
常见误区
RecurringThe most common confusion is treating "static" as meaning the VALUES cannot be changed. That's wrong: a static array's elements can be read from and written to freely, exactly like a dynamic one's. What's fixed in a static structure is only its size, the number of slots, never the content sitting in those slots.
反复出现最常见的混淆是把"静态"误解为数值不能改变。这是错误的:静态数组的元素可以像动态数组一样自由地读取和写入。静态结构中固定不变的只是它的大小,也就是槽位的数量,而绝不是这些槽位中存放的内容。
The second common gap is answering one-sided: naming only advantages for whichever structure feels more "modern" (usually dynamic), without weighing the genuine disadvantage each one carries. A comparison needs both directions, for both structures, or it isn't really a comparison.
第二个常见的欠缺是回答片面:只列出感觉更"现代"的那种结构(通常是动态结构)的优点,却不权衡每种结构各自真正存在的缺点。一个真正的比较需要兼顾两个方向、涵盖两种结构,否则就算不上真正的比较。
Answer frame that scores: name the actual mechanism (fixed vs growable memory allocation) → weigh at least one advantage AND one disadvantage per structure → tie the verdict to a stated real constraint (is the size actually known in advance, or not).
得分的作答框架:说明实际机制(固定内存分配 vs 可增长内存分配)→ 针对每种结构至少权衡一个优点和一个缺点 → 将结论与一个明确陈述的实际约束条件相联系(大小是否事先已知)。
What the confusion looks like: "A static array can't be changed once it's created." Its size can't change, but every value inside it can be freely reassigned at any time.
混淆的表现是这样的: "静态数组一旦创建就不能改变。" 它的大小不能改变,但其中的每一个数值都可以随时自由重新赋值。
What it should say: "A static array's SIZE is fixed once created; its individual elements can still be read and reassigned freely." Names precisely what is and isn't fixed.
应该这样说: "静态数组的大小一旦创建即固定不变;但其各个元素仍然可以自由读取和重新赋值。" 精确说明了什么是固定的、什么不是。
Revision questions
复习题
Past-paper style. Write an answer, then reveal the marking points and mark yourself.
采用历年真题风格。写下答案,然后展开评分要点给自己打分。
[2]Distinguish between a static and a dynamic data structure in terms of memory allocation.
[2]从内存分配的角度区分静态与动态数据结构。
Marking points
评分要点
- A static data structure has its size fixed when it is created; one contiguous block of memory is allocated up front and does not change.
- A dynamic data structure requests and releases memory piece by piece at run time, so it can grow or shrink as elements are added or removed.
- 静态数据结构在创建时大小固定;预先分配一个连续的内存块,且不改变。
- 动态数据结构在运行时按需一块块地申请和释放内存,所以它可以随元素的添加或移除而增大或缩小。
[4]A supermarket wants to store the till receipts printed during a single, fixed 8-hour shift, the maximum possible is known in advance. Compare a static and a dynamic structure for this purpose, and recommend one.
[4]某超市希望存储在一个固定的 8 小时班次内打印出的收银小票,可能的最大数量事先已知。请针对这一用途比较静态结构与动态结构,并推荐其中一种。
Marking points
评分要点
- The maximum number of receipts in a fixed 8-hour shift is known in advance, so a static structure can be sized exactly once.
- A static array gives fast direct indexed access to any receipt and has no per-element overhead for links.
- A dynamic structure would handle an unknown count but adds memory overhead per element and slower traversal, neither needed here.
- Recommend the static structure, because the size is bounded and known and indexed access is useful.
- 固定的 8 小时班次内小票的最大数量事先已知,所以静态结构可以一次性精确确定大小。
- 静态数组对任意小票提供快速的直接索引访问,且没有每个元素用于链接的开销。
- 动态结构可以应对未知的数量,但每个元素增加内存开销且遍历较慢,这里都不需要。
- 推荐静态结构,因为大小有界且已知,并且索引访问有用。
[3]Explain why direct access is possible for a static structure but not, in general, for a dynamic one.
[3]解释为什么静态结构可以实现直接访问,而动态结构一般来说不能。
Marking points
评分要点
- A static structure stores its elements in one contiguous block, so the address of element i can be calculated directly from the start address and i.
- A dynamic structure stores elements separately, linked by references, so there is no formula for the address of element i.
- Reaching the nth element means starting at the first and following n links in turn, which is not direct access.
- 静态结构把元素存储在一个连续块中,所以元素 i 的地址可以直接由起始地址和 i 计算出来。
- 动态结构把元素分开存储,由引用相连,所以没有计算元素 i 地址的公式。
- 到达第 n 个元素意味着从第一个开始依次跟随 n 个链接,这不是直接访问。
Flashcards
记忆卡片
Active recall for this statement’s key terms.
针对本条考纲陈述关键术语的主动回忆练习。
Keep this statement’s practice with you
把这条考纲陈述的练习保存下来
Free account: unlock every revision question and flashcard for B2.2.1, and every other IB CS 2027 statement.
免费账户:解锁 B2.2.1 以及所有其他 IB CS 2027 考纲陈述的全部复习题和记忆卡片。