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 3 Sept 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 select structures before implementing them.

By the end, you will be able to

  • map scenario operations to structure behaviour;
  • combine records, a queue and a hash table;
  • preserve structure invariants across operations;
  • justify alternatives using time, order and mutation needs.

Reactivate: choose from required operations, not topic keywords.

Scenario and stopping point

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 priority.

Minimum stopping point: design and implement the equipment lookup plus FIFO job queue. Extensions are optional.

Worked structure map

  • Item → record/object: named heterogeneous fields.
  • Equipment register → hash table by item ID: direct bucket lookup.
  • Job → record/dictionary.
  • Waiting jobs → queue: oldest request processed first.

Invariant checks: every ID stored in its hash bucket; queue count/pointers describe logical membership; dequeue never occurs empty.

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 interfaces before code:

register_item(table,item)
find_item(table,item_id) → item or None
enqueue_job(queue,job)
next_job(queue) → oldest job or None

Use Python dictionaries/lists as implementation tools while retaining the abstract hash/queue behaviours.

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):
    pass

def next_job(queue):
    pass

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):
    pass
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 responses

Check every response against its command word and the supplied constraints. Strengthen unsupported answers with accurate method, mechanism, state or contextual consequence before submitting.