IB COMPUTER SCIENCE | B4 ASSESSMENT
ABSTRACT DATA TYPES: END OF TOPIC REVIEW
Assess ADT contracts, linked lists, binary search trees, sets and hash tables through scored checks, applied diagrams and developed written responses. All B4 content is HL-only.
BEFORE YOU BEGIN | HL ONLY
This review covers all six B4 objectives. Use several sessions if needed: Section A checks core ideas, Section B applies them to fresh scenarios and Section C develops construction, explanation and evaluation. All questions are HL-only.
Sections A and B award one point per fully correct item, with no partial credit within an item. Section C has separately suggested content marks. These are original practice questions, not an official IB paper or markscheme.
Write diagrams, traces, calculations and Section C answers in your exercise book before revealing guidance. Answers remain only while this page is open.
Automatic total: 48 points. Suggested written total: 84 marks, assessed separately.
C | WRITTEN COMMUNICATION AND SUBJECT KNOWLEDGE
Write in your exercise book before revealing the guidance. The table gives practical guidance based on the IB command terms supplied in the guide; it is not the Cambridge command-word table.
In particular, IB compare focuses on similarities, while distinguish asks for differences. If you need to address both, the question can request each separately. All main commands below are highlighted.
| IB command term | What to provide here | Practical approach |
|---|---|---|
| Compare | Similarities, referring to both throughout | Use both to identify a shared property. |
| Suggest | A possible answer or solution | Apply relevant knowledge to propose a suitable test or approach. |
| Construct | Information in diagrammatic or logical form | Supply complete code/algorithm, including initialization, stopping and failure paths. |
| Trace | Follow and record actions of an algorithm | Separate arguments, variables, decisions, outputs and returned results. |
| Calculate | A numerical result with relevant working | Show counts or formula stages before the answer. |
| Describe | A detailed account | Give relevant features and an ordered process where useful. |
| Explain | A detailed account including reasons or causes | Link correct ideas using because, therefore, resulting in or leading to. |
| Compare and contrast | Similarities and differences, referring to both throughout | Use both for shared properties and whereas for differences. |
| Distinguish | Clear differences | State how roles or behaviours differ. |
| Evaluate | An appraisal weighing strengths and limitations | Connect trade-offs to the scenario and support the conclusion. |
A connective earns no automatic mark by itself: it must express an accurate relationship. For example, “a tombstone does not terminate a probe search, therefore a displaced colliding key remains findable after an earlier removal” explains a mechanism and consequence. Suggested marks reward subject content, not extra unofficial grammar marks.
C1 | SPECIFY A BOUNDED QUEUE ADT
6 suggested marks | HL ONLY
Construct a high-level contract for a help-desk FIFO queue with capacity 3. Include initial state, add, remove, inspect, size and invalid-operation policies. Avoid choosing array indexes or links.
A new queue is empty. enqueue adds a permitted task at the rear unless size is 3. dequeue removes and returns the earliest remaining task; front returns it without removal. Both reject an empty queue using a specified exception and preserve state. Enqueue on full also rejects without mutation. size reports count, with invariant 0 ≤ size ≤ 3.
SUGGESTED MARKING POINTS
- State empty construction and permitted task values or a clear type assumption.
- Specify rear addition and FIFO ordering.
- Specify removal and returned earliest value.
- Specify front inspection without removal.
- Specify count and bounded-size invariant.
- Specify full and empty rejection without corruption.
Writing focus: Describe what callers observe; do not replace the contract with a particular storage algorithm.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC2 | EXPLAIN REPRESENTATION INDEPENDENCE
6 suggested marks | HL ONLY
Explain how an array-backed stack and a linked stack can satisfy the same ADT. Include operations, a failure policy and an implementation change that would break compatibility.
Both can implement push, pop, peek and size with LIFO semantics. Their top may be a final array position or a first node, but the caller uses the same operations. If empty pop raises the agreed exception and peek preserves state, results remain compatible. Changing one implementation to silently discard old entries when full could break an unbounded-in-the-model contract. Thus representation independence preserves agreed behaviour, not merely names.
SUGGESTED MARKING POINTS
- Identify a common stack operation set.
- Explain LIFO semantics in both.
- Separate top representation from logical behaviour.
- Include a compatible inspection or size rule.
- Include the agreed empty failure policy.
- Explain a specific incompatible change and its effect.
Writing focus: Use because and therefore to link the interface to unchanged caller behaviour.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC3 | EVALUATE A CURSOR-BASED EDITOR
6 suggested marks | HL ONLY
Evaluate singly linked, doubly linked and array-backed storage for an editor that holds a current-node reference, makes frequent nearby insertions/deletions and moves backwards and forwards. Random indexed jumps are rare.
A doubly linked list offers direct neighbours and constant-size local link updates near the cursor, so it suits the frequent edits and backward movement. A singly linked form needs fewer link fields but lacks a direct predecessor route. An array-backed sequence offers indexed access and useful locality but usually shifts a suffix for middle edits. Extra links and update complexity are a cost of the doubly linked design. Given the stated workload it is reasonable, subject to practical memory and timing measurements.
SUGGESTED MARKING POINTS
- Relate known cursor references to local update cost.
- Explain direct backward navigation in the doubly linked choice.
- Identify singly linked predecessor limitations.
- Discuss array shifting alongside indexing or locality.
- Identify extra memory/update complexity.
- Give a supported workload-specific judgement.
Writing focus: Weigh alternatives in context instead of claiming one structure is universally fastest.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC4 | SEPARATE SEARCH AND UPDATE COSTS
6 suggested marks | HL ONLY
Distinguish local splice work from a public insert-after-value operation. Explain memory trade-offs between linked nodes and resizable arrays, using explicit assumptions.
A splice after an already-known valid predecessor changes a fixed number of links, so its local link work is O(1). An insert-after-value first searches and can take O(n), making the whole method O(n) worst case. Linked nodes require references and allocation overhead; doubly linked nodes add prev. Resizable arrays may reserve spare slots and occasionally rebuild. These are structural comparisons rather than exact byte totals, and practical locality and runtime layout also matter.
SUGGESTED MARKING POINTS
- State the known-predecessor assumption.
- Explain constant-size local link work.
- Explain the separate linear search and total cost.
- Identify node/link allocation overhead.
- Identify spare capacity or resizing for arrays.
- Qualify byte/performance claims using runtime or locality assumptions.
Writing focus: State what is known before quoting complexity; do not equate Big O with exact elapsed time.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC5 | CONSTRUCT AND TRACE A SINGLY LINKED EDIT
6 suggested marks | HL ONLY
Construct the reference updates inserting X(15) between A(10) and B(20) in a linear A-B-C chain. Then remove B. Trace the final links and explain why head and tail remain valid.
# A, B, C and X are distinct nodes; C.next is None.
X.next = A.next
A.next = X
X.next = B.next
B.next = None
The active sequence is A, X, C, with X.next referring to C. Head remains A and tail remains C. Preserve the old successor before redirecting A. A reference to B can keep that detached object reachable, but it no longer belongs to the chain.
SUGGESTED MARKING POINTS
- Preserve A’s original successor in X.next.
- Redirect A.next to X.
- Bypass B through X.next = B.next.
- Detach B or clearly state its removal from the active chain.
- Give final reachable order A,X,C.
- Explain unchanged valid head A and tail C.
Writing focus: Label node identity separately from stored values and state which incoming link changes.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC6 | CIRCULAR BOUNDARIES AND STOPPING RULES
6 suggested marks | HL ONLY
Explain insertion and deletion for the circular singly linked representation storing tail and size, with head derived as tail.next. Include empty, one-node and multi-node cases and traversal termination.
Empty state has tail None and size zero. The first node points to itself and becomes tail. For non-empty insertion between tail and head, append moves tail to the new node while prepend keeps the old tail. Deletion bypasses through the predecessor, updates tail if required and decrements size; removing the only node sets tail None. Traversal can visit size nodes or stop on return to the starting identity, with an empty check. Repeated data values are not a valid stop condition.
SUGGESTED MARKING POINTS
- Specify empty metadata and derived head behaviour.
- Specify the singleton self-link on first insertion.
- Distinguish non-empty append and prepend tail updates.
- Explain bypass and endpoint handling for a multi-node removal.
- Explain returning to valid empty state on singleton removal.
- Give a correct identity/size stopping rule with empty handling.
Writing focus: Connect each boundary branch to the structural invariant it preserves.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC7 | CONSTRUCT AND TRAVERSE THE BST
6 suggested marks | HL ONLY
Construct a BST from T’s insertion order. Trace search for 60 and give the inorder sequence. State the duplicate policy and apply ancestor bounds.
Root is 45. Its left subtree is 25 with 15 and 35; its right subtree is 65 with left 55 and right 75, and 55 has right child 60. Search visits 45,65,55,60. Inorder is 15,25,35,45,55,60,65,75. Duplicate insertions are ignored. Every descendant must respect its relevant ancestor bounds.
SUGGESTED MARKING POINTS
- Place root 45 and first-level children correctly.
- Construct the 25 subtree with 15 and 35.
- Construct the 65 subtree with 55,75 and right child 60 of 55.
- Give the successful search path.
- Give the complete inorder result.
- State duplicate handling and the subtree-wide ordering requirement.
Writing focus: Draw each one-child node on the correct side; do not rely only on a sorted list.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC8 | DELETE A TWO-CHILD ROOT
6 suggested marks | HL ONLY
Explain deletion of root 45 from a fresh T using its inorder successor. The successor has a right child: show how that child remains and give the final inorder sequence.
The successor is 55, the minimum of the right subtree. Copy its key into the root position, then remove the original 55 by reconnecting 65.left to 60. Final inorder is 15,25,35,55,60,65,75. Key 45 disappears, 55 appears once and 60 stays correctly inside the right subtree. Assign returned subtree roots back into the affected links.
SUGGESTED MARKING POINTS
- Identify the two-child case.
- Select successor 55 through the right-subtree minimum rule.
- Explain replacement at the root position.
- Remove the old successor occurrence and reconnect 60.
- Give the complete final inorder sequence.
- Explain preserved ordering and reassigned subtree-root links.
Writing focus: Use a complete chain of reasons; “replace with successor” alone omits the important reconnection.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC9 | APPLY SET ALGEBRA AND INCLUSION
6 suggested marks | HL ONLY
Construct Python or Java expressions for M’s union, intersection, both differences, Team subset of A and A as a proper subset of itself. Give every result and preserve input sets.
a = {1, 2, 3}
b = {3, 4}
team = {1, 3}
assert a | b == {1, 2, 3, 4}
assert a & b == {3}
assert a - b == {1, 2}
assert b - a == {4}
assert team <= a
assert not (a < a)
Python’s expressions create new results. An equivalent Java solution should copy before the mutating addAll/retainAll/removeAll operations and use A.containsAll(Team) for inclusion.
SUGGESTED MARKING POINTS
- Correct union expression and four-member result.
- Correct intersection expression and shared result.
- Correct A-minus-B direction and result.
- Correct B-minus-A direction and result.
- Correct subset direction and True result.
- Correct proper-self-subset False result with inputs preserved.
Writing focus: Identify whether the question asks for an element test, relation or new set result.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC10 | PRESERVE MEMBERSHIP INPUTS IN JAVA
6 suggested marks | HL ONLY
Construct Java statements producing A intersection B and A minus B without changing A or B. Explain equality versus identity and why sets are unsuitable for preserving repeated scan events.
Set<Integer> both = new HashSet<>(a);
both.retainAll(b);
Set<Integer> onlyA = new HashSet<>(a);
onlyA.removeAll(b);
Assume a and b are the input sets and the relevant java.util types are imported. equals compares set membership; == compares whether references reach the same object. A set collapses repeated equal scan IDs and has no intrinsic event-order contract, so preserve a separate event sequence if those details matter.
SUGGESTED MARKING POINTS
- Create a separate copy for the intersection.
- Use retainAll with the second input.
- Create a separate copy for A-minus-B.
- Use removeAll with the correct direction.
- Distinguish Java equals from reference identity.
- Explain loss of repetitions/order and a suitable separate event representation.
Writing focus: Name which object each mutating call changes, rather than only stating that copies are good.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC11 | TRACE HASHING AND LOAD
6 suggested marks | HL ONLY
Calculate H’s home indices and current load after the three insertions. Trace their placement under chaining and linear probing. Distinguish current load from a resizing threshold.
| Key | MOD 7 | Chained bucket | Linear-probed slot |
|---|---|---|---|
| 12 | 5 | 5 | 5 |
| 19 | 5 | 5 | 6 |
| 26 | 5 | 5 | 0 |
All three collide at home 5. Chaining preserves the pairs in bucket 5; probing wraps from 6 to 0. Current live load is 3/7 ≈ 0.429. A threshold such as 0.75 is a growth policy, not that current ratio and not a collision count.
SUGGESTED MARKING POINTS
- Show the home-index calculation for all three keys.
- Preserve all unequal keys in the chained bucket.
- Place the first two probed entries at 5 and 6.
- Wrap the third to slot 0.
- Calculate current load 3/7 correctly.
- Distinguish load from a policy threshold or collision count.
Writing focus: Label capacity, index range and wraparound, and show numerical working.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC12 | TOMBSTONES AND REHASHING
6 suggested marks | HL ONLY
Explain lookup for 26 after key 19 becomes DELETED in H’s probed table. Then explain how an insertion of existing 26 avoids duplication, and rehash H’s keys into 11 chained buckets.
Lookup checks slot 5, continues past tombstone 6 and finds 26 at 0. A never-used marker at 6 would incorrectly stop the search. Inserting 26 can remember the tombstone but must continue to its existing entry and update it. With capacity 11, the keys 12,19,26 have indices 1,8,4. Reinsert under the new rule while preserving mappings; changing capacity without moving entries can make later lookup miss them.
SUGGESTED MARKING POINTS
- Give the probe route 5,6,0.
- Explain why DELETED does not prove absence.
- Explain remembering but not immediately using the tombstone for an equal key.
- Calculate new MOD-11 indices 1,8,4.
- Explain rebuilding/repositioning under the new capacity.
- Link correct relocation to mapping preservation and later lookup.
Writing focus: Connect marker meaning and index rules to a specific lookup failure they prevent.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC13 | EVALUATE A STUDENT RESOURCE PORTAL
6 suggested marks | HL ONLY
Evaluate representations for three portal tasks: distinct check-ins, ordered catalogue searches and frequent local edits near a known two-way cursor. Include a suitable ADT, a representation and a relevant limitation for each.
A set suits distinct check-ins; a hash-based implementation can offer expected short membership routes, but does not preserve repeated events and depends on suitable hashing. An ordered catalogue can use a BST-based structure, though the ordinary unbalanced form can degrade to a chain. A list with doubly linked nodes can support local edits and two-way cursor movement, at the cost of extra link storage and poor arbitrary indexing. Choose according to workload and any ordering requirements rather than claim one representation is best for all three.
SUGGESTED MARKING POINTS
- Choose set membership for distinct check-ins.
- Qualify its event-loss or hashing/performance limitation.
- Choose an ordered tree-based approach for catalogue keys.
- Qualify basic BST balance/height limitations.
- Relate doubly linked local edits to a known cursor.
- Weigh link/index costs and give context-specific supported choices.
Writing focus: Keep logical ADT choice separate from representation and qualify the performance assumptions.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentC14 | CONSTRUCT A STRUCTURAL VALIDATION PLAN
6 suggested marks | HL ONLY
Construct a test and validation plan for linked lists, BSTs and hashed sets/maps. Include a BST bound-checking algorithm, an important linked boundary and a collision case that output-only testing could miss.
def valid_bst(node, lower=float("-inf"), upper=float("inf")):
if node is None:
return True
return (lower < node.key < upper
and valid_bst(node.left, lower, node.key)
and valid_bst(node.right, node.key, upper))
This validator assumes an acyclic numeric-key tree. Pair it with an independent expected key set and identity/cycle checks where corruption is being tested. For lists, check only-node deletion and circular closure or reciprocal links. For hashing, remove a collided entry, search beyond the marker, update an equal key beyond a tombstone and rehash without losing mappings.
SUGGESTED MARKING POINTS
- Carry inherited bounds rather than only local comparisons.
- Handle an absent subtree and apply strict ordering recursively.
- Pair structure checks with independently expected membership/results.
- Check a relevant linked boundary and endpoint invariant.
- Test collision deletion or equal-key update beyond a tombstone.
- Test rehash preservation and state assumptions such as valid acyclic input.
Writing focus: Give expected structural outcomes and assumptions, not just a list of test names.
Equivalent accurate wording and methods can be valid. Use the points as self-assessment guidance, not an official IB markscheme.
Revisit related contentCHECK THE QUALITY OF YOUR WRITING
Did you answer the command? For explain, check the reason or cause; for compare, address both items through similarities; for compare and contrast, include differences too; for discuss, balance relevant factors in context; for distinguish, make the differences explicit; for evaluate, weigh strengths and limitations and support your conclusion.
For construct, check labels, connections and completeness. For calculate, show enough working to follow your method and label units. Select two weak responses and rewrite them after revising. Keep the written total separate from your automatic result.
YOUR NEXT REVISION STEP
Submit the automatic sections for targeted revision links.
Record your own written marks using the suggested points. Choose two weaknesses and attempt new examples after revising. Use the B4 revision page for worked content and a personal flashcard list, or return to the IB course index.