A Level19Paper 4 — Practical

Computational Thinking and Data Structures

Recursion, and the classic structures: stacks, queues, linked lists and trees.

YOU SHOULD BE ABLE TO

Explain recursion, identifying the base case and general case.
Trace a recursive algorithm and explain the role of the call stack.
Describe and implement a stack, queue, linked list and binary tree.
Write algorithms to insert into and delete from each structure.
Traverse a binary tree in pre-order, in-order and post-order.
Compare the efficiency of searching and sorting algorithms using Big O.

RUN THE PSEUDOCODE

Write the pseudocode your syllabus uses and press Run. Assignment is the arrow — type <- and it works the same as ←. Both syllabuses are accepted, so OUTPUT and PRINT both work; where a word differs from the one the exam prints, the runner says so.

PROGRAM

DECLARE Name : STRING
DECLARE Age : INTEGER

Name <- "Bat"
Age <- 14

OUTPUT "Hello ", Name
OUTPUT "Next year you are ", Age + 1

INPUT — ONE VALUE PER LINE

OUTPUT

Press Run to see what it does

TRACE TABLE

Total ← 0
FOR Count ← 1 TO N
    Total ← Total + Count
NEXT Count
OUTPUT Total

STARTN = 5

Count	Total	OUTPUT

One row per pass through the loop. Leave a cell blank if it does not change on that pass.

//Every recursive solution needs exactly two things

A base case that stops it, and a general case that calls itself with a SMALLER problem. If the base case is missing or unreachable, the calls never stop and the call stack fills up — a stack overflow. Say precisely that if asked.

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
   IF n = 0 THEN
      RETURN 1                      // base case
   ELSE
      RETURN n * Factorial(n - 1)   // general case
   ENDIF
ENDFUNCTION

Factorial(3)
 = 3 × Factorial(2)
 = 3 × 2 × Factorial(1)
 = 3 × 2 × 1 × Factorial(0)
 = 3 × 2 × 1 × 1  =  6

//Stack and queue

A stack is last in, first out — push and pop at the same end. Used for undo, for reversing, and by the processor to store return addresses. A queue is first in, first out — join at the rear, leave from the front. Used for print jobs, keyboard buffers and scheduling.

STACK               QUEUE
push 1,2,3          enqueue 1,2,3
pop -> 3            dequeue -> 1
pop -> 2            dequeue -> 2

//Linked list

Each node holds data plus a pointer to the next node. Inserting or deleting means changing pointers rather than shifting every element, which beats an array when the data changes often. The cost is that you cannot jump straight to the nth item — you must follow the chain. A null pointer marks the end.

//Binary tree traversals

In-order on a binary search tree produces the values in sorted order — that is the most examined fact here.

        50
       /  \
     30    70
    /  \
  20    40

pre-order  (Node,Left,Right): 50 30 20 40 70
in-order   (Left,Node,Right): 20 30 40 50 70  <- sorted
post-order (Left,Right,Node): 20 40 30 70 50

//Big O — comparing algorithms

Big O describes how the work grows as the data grows, ignoring constants.

O(1)        constant     – array access by index
O(log n)    logarithmic  – binary search
O(n)        linear       – linear search
O(n log n)  good sorts   – merge sort, quicksort (average)
O(n²)       quadratic    – bubble, insertion, selection sort

IN THE EXAM

For a recursion trace, write each call on its own line and unwind from the base case upward.
Binary search is O(log n) only because the data is sorted — always state the precondition.

CHECK YOURSELF

1.What happens if a recursive function has no reachable base case?

2.Which traversal of a binary search tree gives the values in sorted order?

3.A stack is:

4.What is the Big O complexity of a binary search?

Artificial Intelligence Further Programming

A Level