Community resourceWorksheet

OCR H446 1.4.2 Integrated data-structure implementation

Part 12 of 14 · H446 1.4.2 · Data structures

Most of H446 1.4.2 is taught one structure at a time, but questions combine them. A community-media studio that lends equipment and schedules editing jobs makes students select records, a queue and a hash table together, define the interfaces first, and only then write the code behind them.

Students will:

  • map the operations a scenario requires onto the behaviour of candidate structures
  • justify a combination of records, a queue and a hash table, rejecting one plausible alternative
  • define function interfaces before implementing anything behind them
  • implement a first in, first out job queue and build a register keyed by item ID with a stated duplicate policy
  • evaluate removing from the front of a Python list against a circular array or linked queue at scale

Inside: 8 explanation cells, 1 fill-in-the-blanks cell, 2 written answers and 2 Python tasks. 26 marks, about 55 to 70 minutes.

Series: H446 1.4.2 · Data structures, part 12 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.

Integrated data-structure implementation

A community-media studio lends equipment and schedules editing jobs. You will decide what each structure must do before selecting and implementing it. This prevents a familiar structure name from replacing a reasoned choice.

By the end, you will be able to

  • map required operations to structure behaviour;
  • combine records, a queue and key-based lookup;
  • preserve the rule that must remain true after each operation;
  • justify alternatives using access, order, scale and update needs.

Scenario

Equipment items have ID, name and available fields. Lookup by ID is frequent. Editing jobs must be processed in request order. Each job has requester, file name and priority note, but this basic system does not reorder jobs by priority.

You will design and implement both the equipment lookup and the FIFO job queue, then evaluate how the queue representation should change at larger scale.

Worked structure map

  • An item uses a record or object because its named fields have different meanings and types.
  • The equipment register uses a hash table keyed by item ID because exact lookup is frequent.
  • A job uses a record or dictionary to group its named fields.
  • Waiting jobs use a queue because the oldest ordinary request must be processed first.

An invariant is a rule that must remain true. Here, every ID must remain reachable through the bucket selected by the hash function, and the queue state must continue to describe its logical members in FIFO order.

Written answer7 marks

Justify all four structure choices and reject one plausible alternative for either the register or waiting jobs.

Use lookup, field meaning and order.

Students type their answer here.

Guided design

Define the operations before writing their code:

register_item(table, item)
find_item(table, item_id) returns an item or None
enqueue_job(queue, job)
next_job(queue) returns the oldest job or None

Python dictionaries and lists are implementation tools. A Python dictionary provides key-based lookup and hides its internal hash-table buckets and collision handling. Your explanation must still refer to the abstract behaviour required by the scenario.

Independent transfer: implement FIFO job queue

Implement add_job(queue,job) and next_job(queue). add_job appends; next_job returns/removes oldest or None. The queue is a Python list for this small model.

Coding task6 marks
def add_job(queue, job):
    # Add at the rear and return the updated queue.
    ...
    return queue

def next_job(queue):
    if len(queue) == 0:
        return None
    # Remove and return the oldest job.
    return ...

Continue: equipment lookup

Implement build_register(items) returning a dictionary keyed by item['id']. Later duplicates replace the previous record under the same ID; state this policy.

Coding task4 marks
def build_register(items):
    table = {}
    for item in items:
        item_id = ...
        table[item_id] = ...
    return table
Written answer5 marks

For a much larger queue, evaluate using list pop(0) versus a circular array or linked queue.

Consider item movement, pointer updates and implementation complexity.

Students type their answer here.

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
Named heterogeneous fields form a completion 1. Oldest-request-first behaviour needs a completion 2. Fast exact lookup by ID can use a completion 3 table. A large array queue avoids item shifting by updating circular completion 4.

Review your work

Check that the Python implementation preserves the FIFO and lookup behaviours chosen in the design.