A-Level Computer Science: Queues, Linked Lists, Graphs and Tree Traversals

This material trains the data structures of A level Computer Science that are examined through traces: the student is given the state of a structure and has to say exactly what it looks like after a few operations. It is for Year 12 and Year 13 students who know what a stack and a queue are and need practice with the structures and traversals built on top of them.

The quiz has twelve questions. Three are about queues: why a linear queue in an array runs out of room, a Python circular queue whose pointers wrap round and which refuses an item when full, and the leaving order of a priority queue with a tie. Three use one linked list stored as indices and pointers: traversing it from the start pointer, inserting an item in alphabetical order, and deleting one with a single pointer change. Four are about graphs: turning an adjacency matrix into adjacency lists and spotting that the graph is directed, choosing between a matrix and a list for a sparse road network, finding the node that cannot be reached in a directed graph, and a depth-first traversal with the breadth-first order as the tempting wrong answer. The last two are tree traversals: post-order on a binary search tree and on an expression tree, which gives Reverse Polish notation.

Every explanation traces the structure step by step and says what the wrong options did, for example visiting neighbours in breadth-first order or moving data instead of pointers. The Python program is printed in a code block and its output was checked by running it.

The flashcards cover linear, circular and priority queues, detecting a full circular queue, linked lists with insertion and deletion, adjacency matrices and lists, directed and undirected graphs, depth-first and breadth-first traversal, and the three tree traversals with a use for each.

The written work has eight longer tasks to answer on paper: pseudo-code for a circular queue, two ways to build a priority queue, inserting and deleting in a linked list with a free list, writing a weighted graph as a matrix and a list, depth-first and breadth-first orders with their uses, three traversals of one tree, a queue built from a linked list, and inserting into and searching a binary search tree with a comparison against an unbalanced tree. Each task has a model answer and the points a marker would look for.

There is also a short oral practice with an examiner, who describes every structure in words, asks one question at a time and gives brief feedback at the end.

The content is based on the data structures and traversal algorithms of the A level specifications, for example OCR H446 sections 1.4.2 and 2.3.1 and AQA 7517 sections 4.2 and 4.3.

• Explain the limitation of a linear queue and trace a circular queue with wrap-around pointers
• Order the output of a priority queue, including ties
• Traverse, insert into and delete from a linked list stored in arrays
• Convert between adjacency matrices and adjacency lists and choose between them
• Trace depth-first and breadth-first traversals of a graph
• Carry out pre-order, in-order and post-order traversals of binary trees and expression trees

Practice material written by Zestly, based on the data structures and traversal content of the A level Computer Science specifications (for example OCR H446 sections 1.4.2 and 2.3.1, and AQA 7517 sections 4.2 and 4.3).