Graph traversal practice for AQA A Level Computer Science (7517): twenty
different worksheets on breadth-first and depth-first search, each with a
complete answer key.

Every worksheet is built on a different graph. That is the point of the pack:
you can set one sheet in class, a second for homework and a third for a resit
without any two students ever holding the same questions, and without having
to invent new graphs yourself at eleven o’clock at night.

WHAT YOU GET

• 20 worksheets, 3 pages each, numbered 01 to 20
• 20 matching answer keys, 2 pages each
• A contents table listing the size and mark total of every sheet, so you can
  pick a short one for a cover lesson or a longer one for a full period

WHAT IS ON EVERY SHEET

Question 1 asks students to complete a trace table for a breadth-first
traversal: the node removed from the queue, the state of the queue after each
step, and the running visit order. Question 2 does the same for depth-first
search, including the backtracking steps that most students forget. Question 3
shows a piece of pseudocode and asks which traversal it implements, and for a
typical application of it.

The first row of each trace table is completed for students, which removes any
doubt about where the trace begins. Mark totals are printed at the top of each
sheet and beside every question.

WRITTEN FOR AQA, NOT ADAPTED FROM SOMEWHERE ELSE

The pseudocode uses the conventions that appear in real 7517 question papers:
the arrow assignment, SUBROUTINE and ENDSUBROUTINE, OUTPUT, FOR EACH … IN,
and adjacency written as ConnectedNodes[N]. Helper subroutines are declared in
prose before the code, exactly as AQA does. Question 3 asks for an application
of the traversal rather than its time complexity, because that is what
specification 4.3.1 actually requires.

THE ANSWER KEYS DO SOMETHING UNUSUAL

Textbooks disagree about how depth-first search is traced. These sheets use
the alphabetically-first convention that mark schemes normally show, and state
it plainly on the worksheet. But each answer key also lists the visit orders
produced by the other two conventions in common use, with a note telling you
to credit them in full. Whichever version your department teaches, you can
mark with these keys without arguing with them.

FORMAT

PDF, A4, print-ready. You do not need to edit these: there are twenty
genuinely different versions, so you already have a fresh sheet for every
class, every resit and every homework.

Licensed for the purchasing teacher and their own classes.