A-Level Computer Science: Algorithms and Data Structures

These are traces, not definitions. A stack takes six operations and you say what is left in it. A hash table with linear probing takes three keys that all collide and you say where the third one lands. A tree written out as a list of parent-to-child relationships is traversed in pre-order and you give the sequence. An array goes through one full pass of a bubble sort and you give the array. Every structure is written out inside its own question, so nothing depends on a diagram you cannot see.

One question is worth pointing out because it is the kind that usually has two right answers. Deleting the root of a binary search tree can promote either the largest value in the left subtree or the smallest in the right — both keep the tree ordered, and both are taught. So the question names which convention it wants, and the explanation says plainly that the other value would be correct under the other one. A question that quietly accepts one of two valid answers teaches the wrong lesson about what the algorithm requires.

The rest covers why binary search is logarithmic rather than merely fast, what actually happens when a recursion loses its base case, what a private field buys a class beyond secrecy, and the difference between a problem that is merely expensive to compute and one that no algorithm can decide at all.

Pseudocode is board-neutral: plain assignment, IF/THEN/ELSE, FOR and WHILE, and an OUTPUT statement. Boards set their own reference languages and none of them is assumed here.

Nothing is taken from any exam board specification, past paper, mark scheme or textbook.

Zestly is an independent study tool. It is not affiliated with any exam board and it is not an exam centre.

• Trace a sequence of stack operations and a linear-probing insertion to their final state
• Produce the output of a pre-order tree traversal and a breadth-first graph search from a structure given in text
• Say why binary search is logarithmic, and what distinguishes complexity from running time
• Give the state of an array after one full pass of a bubble sort
• Explain what a recursion's base case is for and what happens without it
• Say what encapsulation buys beyond hiding a field
• Distinguish an undecidable problem from one that is merely expensive to solve
• Delete the root of a binary search tree by the named convention and say why the other valid answer is not the one asked for

A binary search tree is built by inserting, in this order: 10, 5, 15, 3, 7. The root is now deleted and replaced by its IN-ORDER PREDECESSOR, that is, the largest value in its left subtree. Which node moves to the root, and what becomes of the place it came from? — one of ten traced questions written for this set.