AQA A-Level Computer Science Paper 1, June 2025: Question 1

✅ Acceptable Answers (Any 1)

• The hashing algorithm/function calculates/determines the exact memory location/index used directly.
• There is no need to search through or compare other records to find the required item (direct access / O(1) lookup).

🧠 Exam Technique

Highlight the contrast: sorted lists require sequential or divide-and-conquer comparisons (e.g. O(log n)), whereas a hash table uses key computation to jump directly to the slot without comparisons.

✅ 4-Step Process (1 mark per step)

1. Apply the hashing algorithm/function;
2. Apply it specifically to the unique/primary key of the record;
3. Insert/store the data at the calculated index (or address/memory location);
4. If the slot is already occupied (a collision), use a suitable method for collision handling (e.g., linear probing or rehashing).

❌ Common Errors

• Vague input: Saying "hash the data" instead of "hash the key / primary key" scores 0 for step 2.
• Omitting collision handling: Forgetting to describe what happens when a target slot is already filled.

✅ Acceptable Answers

• More collisions occur, meaning direct access will not happen as frequently / items will not be located at their initial hashed index.
• More collisions require collision resolution methods (such as linear probing/searching through synonym chains), which takes extra time.

❌ Examiner Pitfall

Writing only "more collisions occur" is Not Enough (NE). You must state the consequence: direct addressing fails, requiring searching/probing along collision paths.

✅ Acceptable Answers

• As the list increases in size, the maximum number of comparisons increases at the same rate (direct linear proportion).
• In the worst case, all n items must be examined/compared.

❌ Common Error

Stating simply "it takes n comparisons" is Not Enough (NE). You must qualify this as the worst-case scenario or explain the proportional growth rate.

✅ Acceptable Answers

• Each comparison halves the number of remaining items that need to be considered (or halves the remaining search space).
• As list size increases, the maximum number of comparisons increases at a decreasing rate (logarithmic growth).

💡 Key Knowledge

Because the search space is divided by 2 after each probe (repeated division), the number of steps required to reduce n items to 1 is log₂ n .

✅ Accepted Answer

It can be used on unsorted / unordered lists (data does not need to be sorted prior to searching).

🧠 Exam Technique

Binary search strictly requires pre-sorted data. Sorting an unsorted list takes at best O(n log n), making a one-off linear search (O(n)) far more efficient when data is unordered.

✅ Acceptable Answers (Any 1)

• Both have polynomial (or better) time complexity (e.g. O(n²) for bubble sort, O(n log n) for merge sort).
• Neither has exponential (or factorial) time complexity.
• As the size of the list grows, the increase in time taken is reasonable / solvable in polynomial time.

💡 Key Term: Tractability

A problem/algorithm is tractable if it can be solved within polynomial time, O(nᵏ) for some constant k . Intractable algorithms require exponential (e.g. O(2ⁿ) ) or factorial time.

📐 Calculation Steps

1. Let the number of items be n = 100 .
2. In each pass through the list, at least one item (the largest unsorted value) bubbles to its final correct position.
3. Once n - 1 items are placed in their correct positions, the final 1 item is naturally positioned correctly.
4. Number of passes = n - 1 = 100 - 1 = 99 .

✅ Final Answer

99

❌ Common Error

Answering 100. Remember that a list of n elements requires at most n - 1 complete passes.