B4 Abstract data types: stacks, queues, linked lists, trees (HL) – IB Computer Science exam questions with mark scheme

1Core4 marks

The diagram shows the initial contents of a stack, with 5 at the top.

The following operations are performed in order: push(6), pop(), pop(), push(1), peek().

(a) State the values returned by the two pop() operations. [1]

(b) State the value returned by peek(). [1]

(a) 6 then 5(1)
(b) 1(1)
(c) Final contents bottom to top: 8, 3, 1(1)
3 items(1)
Answer: (a) 6, 5 (b) 1 (c) 8, 3, 1 – three items
Examiner tip: A stack is last-in first-out: the first pop returns the value just pushed (6), not the original top.

2StandardHL only4 marks

A singly linked list stores the nodes A, B, C and D as shown. Each node contains a data value and a pointer to the next node, and head points to node A.

(a) Describe the steps required to delete node C from the list. [3]

(b) State one advantage of a linked list over an array when many deletions and insertions are needed. [1]

(a) Traverse the list from head, following the pointers, until the node before C (node B) is found (allow: traverse to C while keeping a pointer to the previous node)(1)
Set the pointer of B to the pointer of C (so B points to D)(1)
C is now unreachable (no pointer refers to it) so it is removed from the list and its memory can be reclaimed; the list now reads A → B → D(1)
(b) Items do not need to be shifted along in memory when one is added or removed (only pointers change) (allow: the list grows and shrinks dynamically, so no fixed size has to be declared and no space is pre-allocated)(1)
Answer: (a) find B, set B.next = C.next (D), C is dereferenced (b) no shifting of elements
Examiner tip: The key mark is re-pointing the previous node; just 'remove C' scores nothing.

3HardHL only5 marks

The binary search tree shown was built by inserting the values 50, 30, 70, 20, 40, 60, 80 and 35 in that order.

(a) Write down the sequence of values produced by an in-order, a pre-order and a post-order traversal. [3]

(b) State the number of nodes examined (including the node holding 35) when searching for the value 35, starting at the root. [1]

(a) In-order: 20, 30, 35, 40, 50, 60, 70, 80(1)
Pre-order: 50, 30, 20, 40, 35, 70, 60, 80(1)
Post-order: 20, 35, 40, 30, 60, 80, 70, 50(1)
(b) 4 nodes examined (50, 30, 40, 35)(1)
(c) In-order traversal(1)
Answer: (a) In: 20 30 35 40 50 60 70 80; Pre: 50 30 20 40 35 70 60 80; Post: 20 35 40 30 60 80 70 50 (b) 4 (c) in-order
Examiner tip: Pre-order visits the node first, post-order last; write the node's position relative to its subtrees before listing.

4Standard5 marks

A stack is used to evaluate the postfix (reverse Polish) expression 5 3 + 2 * 4 -. Operands are pushed; when an operator is read, two values are popped, the operation is applied and the result is pushed.

(a) Show the contents of the stack after the token + and after the token * has been processed. [2]

(b) State the final result. [1]

(c) When the operator - is processed, state the two values popped, in the order they are popped, and identify which of them is the left-hand operand of the subtraction. [2]

(a) After +: stack contains 8(1)
After *: stack contains 16(1)
(b) 12 (16 − 4)(1)
(c) Values popped in the order 4 then 16(1)
The second value popped (16, pushed first) is the left-hand operand and the first value popped (4) is the right-hand operand, so the calculation is 16 − 4(1)
Answer: (a) [8], then [16] (b) 12 (c) popped 4 then 16; left operand 16 (second popped), so 16 − 4
Examiner tip: The first value popped is the right operand; swapping them is the commonest error with - and ÷.

5Hard6 marks

Write a Python class Stack that implements a stack of fixed maximum size using a list and an integer top. It must include:

a constructor taking the maximum size;
methods is_empty() and is_full();
a method push(item) that raises an error if the stack is full;
a method pop() that returns the top item and raises an error if the stack is empty.

[6]

Constructor creates a list of the given size (e.g. [None] * size)(1)
Initialises the top pointer to −1 (empty stack) (allow top = 0 used consistently as the next free index / item count)(1)
is_empty and is_full return correct Boolean tests (top == −1; top == size − 1; or top == 0; top == size if top starts at 0)(1)
push checks for a full stack and raises an error (overflow) before storing anything(1)
push increments top and stores the item at data[top] (allow store then increment if top starts at 0)(1)
pop checks for empty (underflow), then returns data[top] and decrements top (allow decrement then return if top starts at 0)(1)

Answer:

class Stack:
    def __init__(self, size):
        self.data = [None] * size
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == len(self.data) - 1

    def push(self, item):
        if self.is_full():
            raise OverflowError("stack full")
        self.top += 1
        self.data[self.top] = item

    def pop(self):
        if self.is_empty():
            raise IndexError("stack empty")
        item = self.data[self.top]
        self.top -= 1
        return item

Examiner tip: Check for overflow/underflow before changing top; increment before storing in push, decrement after reading in pop.

Still losing marks on this topic?

Book a free introductory session and we'll find exactly which step is costing you.

Book a free intro