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.

A | QUICK CHECKS

All 24 quick checks are HL-only. Select every correct option in each checkbox item. A complete correct set earns one point; extra or missing choices do not.

A1 | Which describe an ADT?

Select all correct answers. One point requires the complete correct set.

A2 | Which belong in a stack contract?

Select all correct answers. One point requires the complete correct set.

A3 | Which distinguish an ADT and an abstract class?

Select all correct answers. One point requires the complete correct set.

A4 | Which support representation independence?

Select all correct answers. One point requires the complete correct set.

A5 | Which linked-list evaluations are sound?

Select all correct answers. One point requires the complete correct set.

A6 | Which costs depend on references already available?

Select all correct answers. One point requires the complete correct set.

A7 | Which fit doubly linked lists?

Select all correct answers. One point requires the complete correct set.

A8 | Which fit circular lists?

Select all correct answers. One point requires the complete correct set.

A9 | Which insert X after A safely in a singly linked list?

Select all correct answers. One point requires the complete correct set.

A10 | Which must hold after a complete linear doubly linked update?

Select all correct answers. One point requires the complete correct set.

A11 | Which apply to deleting the only node of the lesson’s circular list?

Select all correct answers. One point requires the complete correct set.

A12 | Which support a first-match list API?

Select all correct answers. One point requires the complete correct set.

A13 | Which describe a strict unique-key BST?

Select all correct answers. One point requires the complete correct set.

A14 | Which BST statements are correct?

Select all correct answers. One point requires the complete correct set.

A15 | Which describe two-child deletion with a right-subtree successor?

Select all correct answers. One point requires the complete correct set.

A16 | Which complexity statements are accurate?

Select all correct answers. One point requires the complete correct set.

A17 | Which are set ADT properties?

Select all correct answers. One point requires the complete correct set.

A18 | Which set laws are correct?

Select all correct answers. One point requires the complete correct set.

A19 | Which inclusion statements are true?

Select all correct answers. One point requires the complete correct set.

A20 | Which API statements are correct?

Select all correct answers. One point requires the complete correct set.

A21 | Which collision statements are correct?

Select all correct answers. One point requires the complete correct set.

A22 | Which load-factor statements are sound?

Select all correct answers. One point requires the complete correct set.

A23 | Which describe correct probing after deletion?

Select all correct answers. One point requires the complete correct set.

A24 | Which Python/Java collection statements are correct?

Select all correct answers. One point requires the complete correct set.

B | APPLY YOUR KNOWLEDGE

Each item uses its stated fresh scenario. Do not carry additional changes from another answer. Draw references or show calculations in your book before entering the final answer. All items are HL-only.

S | STACK CONTRACT

A fresh unbounded-in-the-model LIFO stack starts empty. push adds, peek returns the top without removal, pop removes and returns the top. Perform push A, push B, push C, pop once, then peek once. Empty pop is specified to raise an exception without changing state.

L | LINEAR LIST MODEL

Unless a question says otherwise, linear singly and doubly lists maintain head and tail. A search by value starts at head. Treat link operations as unit cost. For L1, execute this full fragment once; b remains referenced by its variable even after it is detached.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

a, b, c = Node(10), Node(20), Node(30)
a.next, b.next = b, c
head, tail = a, c
x = Node(15, a.next)
a.next = x
x.next = b.next
b.next = None
T | BST MODEL

Insert 45, 25, 65, 15, 35, 55, 75, 60 into an ordinary unbalanced BST. Ignore duplicate insertions. Height counts edges. For two-child deletion use the minimum of the right subtree and remove its old occurrence.

Fresh BST for applied review items 15 25 35 45 55 60 65 75
Fresh BST for applied review items. The root is pink; absent children are omitted.
M | MEMBERSHIP MODEL

A = {1,2,3}, B = {3,4} and Team = {1,3}. Set equality compares membership; subset permits equality. Java containsAll is used on set inputs.

H | HASH-TABLE MODEL

Use non-negative integer keys and home index = key MOD capacity. Initially capacity is 7. Insert keys 12, 19 and 26 in that order. For chaining, keep all colliding pairs in a bucket. For linear probing, check successive slots with wraparound; NEVER USED terminates an absent search and DELETED does not. After removing 19 from the probing table, keep a tombstone. For the rehash question, use the same three keys in a chained table with capacity changed to 11.

B1 | S: which value does the pop return?
B2 | S: which value does the later peek return?
B3 | S: how many elements remain after both operations?
B4 | A second stack implementation returns the oldest item on pop. Does it satisfy S?
B5 | L: local insertion after an already known valid predecessor needs how much link work?
B6 | L: append in a singly linked list with maintained tail has what standard link-work cost?
B7 | L: arbitrary indexed access in a basic doubly linked list has which worst-case growth?
B8 | For 100 nodes, how many additional node link fields does a doubly linked form need compared with singly, excluding endpoint metadata?
B9 | L1: how many nodes are reachable by following next from head after the fragment?
B10 | L1: which node does x.next refer to at the end?
B11 | Fresh original A-B-C without the L1 edits: after removing head A, where should head refer?
B12 | A circular singleton uses tail.next as its derived head. After deleting its only node, what should tail be?
B13 | T: what is the third key in the inorder traversal, counting from one?
B14 | T: how many node keys are compared on a successful search for 60?
B15 | Fresh T: after deleting root 45 using the successor policy, what is the new root key?
B16 | T: what is the height in edges?
B17 | M: how many members are in A union B?
B18 | M: which is A minus B?
B19 | M: what does Java A.containsAll(Team) return?
B20 | M: is A a proper subset of itself?
B21 | H: what is the home index of key 19 in capacity 7?
B22 | H: where is key 26 stored after the three linear-probing insertions?
B23 | H: after 19 becomes DELETED, how many slots are inspected to find 26, including its matching slot?
B24 | H: after chained rehash to capacity 11, what is key 19’s new bucket?

CHECK SECTIONS A AND B

Unanswered items receive zero. Each checkbox item requires all correct choices and no incorrect extras. Written marks are separate. Changing an answer or level requires resubmission.

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.

C2 | 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.

C3 | 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.

C4 | 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.

C5 | 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.

C6 | 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.

C7 | 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.

C8 | 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.

C9 | 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.

C10 | 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.

C11 | 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.

C12 | 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.

C13 | 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.

C14 | 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.

CHECK 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.