Community resourceWorksheet

OCR H446 1.4.2 Data Structures consolidation

Part 13 of 14 · H446 1.4.2 · Data structures

This is the mixed revision set for H446 1.4.2, so no new structures appear. Contexts are interleaved deliberately, which forces students to diagnose the behaviour a requirement needs before naming a structure, starting from a closed-book retrieval section and ending in an integrated game-server design.

Students will:

  • recall structure choices from memory across contexts presented out of teaching order
  • diagnose the required behaviour, such as indexed shape or ordered removal, before choosing a structure
  • trace circular queue pointer updates and correct an unsafe linked-list insertion order
  • compare a directed graph with a tree, and a binary search tree with a hash table, for stated purposes
  • select and justify structures for six differing requirements in one game-server design

Inside: 4 explanation cells, 2 multiple-choice questions, 1 fill-in-the-blanks cell, 5 written answers and 1 trace table. 35 marks, about 60 to 75 minutes.

Series: H446 1.4.2 · Data structures, part 13 of 14.

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 60 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 1 Oct 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Data Structures consolidation

Complete the sections in order, beginning with closed-book retrieval and then applying the ideas in the integrated contexts. No new required knowledge is introduced.

This worksheet contains no new structures. Begin each problem by identifying the behaviour it requires: fixed indexed positions, named fields, last-in-first-out or first-in-first-out order, linked nodes, general connections, a hierarchy, ordered search or key-based lookup.

A reliable method

Before changing a structure, state the rule that must remain true. Draw the state before and after a pointer operation. When selecting a structure, connect one required operation to a consequence in the scenario.

Multiple choice1 mark

A parser must resolve the most recently opened unmatched bracket first. Which structure fits?

  • AStack
  • BQueue
  • CGraph
  • DHash table
Multiple choice1 mark

One sensor reading has timestamp, numeric value and valid flag. Which structure best groups these named fields?

  • A3D array
  • BRecord
  • CQueue
  • DBST
Trace table4 marks

Trace the circular pointer updates.

Enter a value only when it changes. Follow pointers and output in execution order.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. data = ["A", "B", "", ""]
  2. head = 0
  3. tail = 2
  4. count = 2
  5. for item in ["C", "D"]:
  6. data[tail] = item
  7. tail = (tail + 1) % 4
  8. count = count + 1
  9. print(tail)
  10. print(count)
Trace table with 6 columns
RowdataheadtailcountitemOutput
1
2
3
4
5
6
Written answer3 marks

A linked-list insertion performs previous.next = new before new.next is set. Explain the risk and give the safe update order.

Use orphan/reachability language.

Students type their answer here.

Written answer4 marks

Compare a directed graph and a tree for modelling course prerequisites. State when each is suitable.

Use multiple parents, cycles and hierarchy.

Students type their answer here.

Written answer6 marks

Compare a BST and hash table for exact student-ID lookup and sorted traversal.

Discuss both required operations and shape/collisions.

Students type their answer here.

Independent mixed design

A game server stores fixed 3D world cells, player records, undo history, incoming chat reports, friendships and ID lookup.

Written answer10 marks

Choose one structure for each of the six requirements and justify four choices.

Use each structure’s behaviour/property.

Students type their answer here.

Written answer6 marks

Choose three different structures from your design and describe one create/add, one traversal/search and one remove operation while preserving an invariant.

Name boundary cases.

Students type their answer here.

Final closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
A stack removes the most recent item; a queue removes the completion 1. A linked list preserves logical order with completion 2. A graph models general connections; a tree models a rooted completion 3. A BST orders keys, while a hash table computes a completion 4.

Review your work

Use your answers to identify one operation that needs another complete trace or implementation attempt.