2025 OCR A-Level Computer Science - H446 模擬試題連答案詳解

Line 4: the array is zero-indexed, so the last valid index is scores.length - 1. The loop as written accesses scores[scores.length], which is out of bounds. Correct to: for i = 0 to scores.length - 1.

Line 5: the specification requires scores greater than or equal to limit, but the condition uses > and so omits scores equal to limit. Correct to: if scores[i] >= limit then.

Line 10: if no score qualifies, count is 0 and the division fails (division by zero). The function must return 0 in that case. Correct to: if count == 0 then return 0 else return total / count endif (or equivalent, placed in place of line 10).

1 mark per correct error identified AND corrected (max 3):
- Line 4: loop upper bound must be scores.length - 1 (e.g. for i = 0 to scores.length - 1). Allow scores.length - 1 expressed as a while loop with i < scores.length. DNA changing the start to 1.
- Line 5: comparison changed to >= (e.g. if scores[i] >= limit then). Allow NOT (scores[i] < limit).
- Line 10: guard against count being 0 so that 0 is returned, e.g. if count == 0 then return 0 else return total / count endif. Allow the check being inserted before line 10 provided line 10 only executes when count > 0. Allow count > 0 test.

The line number and a correct correction are both required for the mark. Award the mark for a correct correction if the line number is clearly implied by the position of the amendment. Do not award a mark where the correction is given for a line that was already correct. Max 3.

The counter must start at zero so that only readings above the limit are counted. The loop must visit every index from 0 to the last valid index, which is temps.length - 1 because the array is 0-indexed and the for loop is inclusive of both ends. The comparison must be strictly greater than, so the operator is >. The function returns the counter, count.

Completed function:

function highReadings(temps, limit)
count = 0
for i = 0 to temps.length - 1
if temps[i] > limit then
count = count + 1
endif
next i
return count
endfunction

1 mark per correct gap, maximum 4:
- (1) 0 [1]
- (2) temps.length - 1 [1]. Allow any equivalent expression, e.g. len(temps) - 1 or the literal final index if the array size is stated. Do not accept temps.length (it causes an out-of-range index) or temps.length - 2.
- (3) > [1]. Do not accept >=, < or ==.
- (4) count [1]. Do not accept i or temps[i].
Allow equivalent syntax from any high-level language. Each gap is marked independently; there is no follow through.

Line 4: the loop is inclusive of both ends, so scores[scores.length] is outside the array. The upper bound must be scores.length - 1.
Line 5: the specification says 'greater than or equal to', so > must become >=.
Line 10: if count is 0 the division fails (division by zero). A check is needed so that 0 is returned when no score qualifies.
Corrected code:
function averageAbove(scores, limit)
total = 0
count = 0
for i = 0 to scores.length - 1
if scores[i] >= limit then
total = total + scores[i]
count = count + 1
endif
next i
if count == 0 then
return 0
endif
return total / count
endfunction

Error 1 (2 marks):
- Identifies line 4 (1)
- Upper bound corrected to scores.length - 1 (or < scores.length with equivalent loop) (1)
Error 2 (1 mark):
- Line 5 comparison changed to >= (1) (identification and correction required together)
Error 3 (2 marks):
- Identifies line 10 / the division by count when count is 0 (1)
- Adds a selection that returns 0 when count == 0 (before the division) and otherwise returns total / count (1)
Allow the zero check placed before line 10 as a new line. Allow the identification mark for a correction placed at the correct location without the line number quoted. Do not accept changes that alter correct lines, or a correction that returns 0 after the division has been attempted. Maximum 5.

(a) The array has five elements, indexed 0 to 4, so the stack is full when top is 4. Pushing first increments top, then stores the item. Popping is not possible when top is -1 (empty stack). After reading the item, top is decremented.
(b) public function isEmpty()
return top == -1
endfunction

(a) One mark per correct gap:
- [A] 4 or items.length - 1 or items.length - 1 equivalent (1). Do not accept 5.
- [B] top + 1 (1). Allow top++ style equivalents only if the result is assigned correctly.
- [C] top == -1 (1). Allow top < 0, or a call to isEmpty() if consistent with (b).
- [D] top - 1 (1). Do not accept top = top - 1 written inside the gap if it duplicates the assignment on line 19 and makes the line invalid.
(b) 1 mark for a correctly formed method that returns true when top == -1 and false otherwise, e.g. return top == -1 (1). Allow an if/else version returning true/false. Do not accept a method that outputs rather than returns the value.
Maximum 5.

With byVal, the procedure receives a copy of the value 40. Changes to points affect only the copy, which is discarded when the procedure ends. The variable score therefore keeps its original value of 40. With byRef, the change would alter score itself.

- A copy of the value of score is passed to the procedure / the procedure works on a local copy (1)
- so score is not changed by the procedure / still holds 40 after the call (1)

Allow: the original variable is not altered.
Do not accept: 'the value is not passed' or 'the program crashes'.
Max 2.

Binary search compares the target with the middle item and discards one half of the list. This only works if the items are in order, so that the target must lie in the retained half. In an unsorted array the target could be in the discarded half, so the search could fail to find an item that is present.

- Binary search requires the data to be sorted / in order (1)
- because the midpoint comparison is used to discard half of the data; in unsorted data the item could be in the discarded half / the result would be unreliable (1)

Allow: a linear search would be needed instead (not credited alone).
Do not accept: 'binary search is slower' or 'the array is too large'.
Max 2.

The operating system reserves an area of secondary storage to act as additional memory. Sections (pages) of programs that are not currently in use are moved out of RAM to this area, freeing space in RAM. When a moved page is needed, it is swapped back into RAM, so only the parts of programs in use need to be in RAM at one time.

- Part of secondary storage / the hard disk is used as an extension of RAM (1)
- Pages / sections of programs not currently needed are swapped out of RAM and swapped back in when required (1)

Allow: 'swap space' or 'page file'.
Do not accept: 'RAM is made bigger' without reference to secondary storage.
Max 2.

First check top != -1, because popping an empty stack is an underflow error. Then copy the value held at index top in data, decrement top by 1 so that the next item becomes the top, and return the copied value.

- Check the stack is not empty / top is not -1 (1)
- Return the item at data[top] and decrement top by 1 (1)

Allow: steps in either order for the second point provided the item is read before it is lost.
Do not accept: setting top to 0 or deleting the whole array.
Max 2.

The parameter bonus is passed by value, so the procedure receives a copy of the value of extra. Setting bonus to 0 on line 03 changes only the copy, so extra is still 10 after the call. The parameter score is passed by reference, so it refers to the same memory location as total. Line 02 therefore changes total itself, and total is 50 after the call.

Award 1 mark for each point, maximum 3:
- By value: a copy of the value is passed to the procedure / the procedure works on its own copy (1)
- ...so changing it (bonus = 0) does not change the original variable; extra remains 10 (1)
- By reference: the address of / a pointer to the original variable is passed, so the parameter refers to the same memory location (1)
- ...so changes made in the procedure affect the original variable; total becomes 50 (1)

Allow 'alias' for reference. Do not accept 'by value cannot be changed' without reference to the original being unaffected. Do not accept answers that only define the terms without any reference to total or extra for the application mark; a maximum of 2 marks is available if neither variable is referred to.

Passing by value copies the value 50 into the local parameter score. The addition changes only the copy, which is discarded when the procedure ends. points stays 50. Passing by reference gives the procedure access to the original variable, so the change affects points and 60 is output.

(a) 50 (1)
(b) Max 2:
- The value of points (50) is copied into score (1)
- score becomes 60 / is changed, but only locally within the procedure (1)
- points is not altered / keeps the value 50 (1)
(c) Pass score by reference / declare the parameter as byRef score (1). Allow: returning the new value from a function and assigning it to points; making points global and modifying it directly. DNA: just 'use a different variable'.

Binary search repeatedly halves the search area by comparing the target with the midpoint of a sorted list. This needs at most about 10 comparisons for 1000 items, giving logarithmic complexity, O(log n).

(a) Max 3:
- Find the middle item of the (sorted) array (1)
- Compare the target with the middle item; if equal the item is found (1)
- If the target is smaller, discard the middle and everything above it / if larger, discard the middle and everything below it (1)
- Repeat with the remaining half until the item is found or no items remain (1)
(b) O(log n) (1). Allow O(log2 n). DNA O(n) or O(n log n).

A stack is last in, first out, so push adds at the top and pop removes the latest change. With a fixed-size array, pushing when full would exceed the array bounds, so the full condition must be tested first.

(a) Max 2:
- A change is pushed / added to the top of the stack (1)
- Undo pops / removes the item from the top, which is the most recent change (LIFO) (1)
(b) Max 2:
- Check whether the stack is full / top points to the last position of the array (1)
- To avoid stack overflow / an error from adding beyond the array bounds / overwriting data (1)
Allow: increment top then store the value as part of the push description.

Paging splits programs into equal-sized pages so only the needed pages sit in RAM, the rest being on disk as virtual memory. If too many programs compete for RAM, pages are repeatedly swapped in and out; because secondary storage is far slower than RAM, performance drops.

(a) Max 2:
- Memory / programs are divided into fixed-size blocks called pages (frames in RAM) (1)
- Pages not currently needed are stored on secondary storage and loaded into RAM when required (1)
(b) Max 2:
- There is not enough RAM, so pages are swapped between RAM and secondary storage frequently / thrashing (1)
- Secondary storage is much slower than RAM, so the processor spends time waiting for pages to load (1)
DNA: 'the CPU overheats'.

Pass 1: mid = 3, data[3] = 22 < 47, so low = 4.
Pass 2: low = 4, high = 7, mid = (4 + 7) DIV 2 = 5, data[5] = 38 < 47, so low = 6. found remains false.
Pass 3: low = 6, high = 7, mid = (6 + 7) DIV 2 = 6, data[6] = 47 == target, so found = true. The loop then ends.

| Pass | low | high | mid | data[mid] | found |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 22 | false |
| 2 | 4 | 7 | 5 | 38 | false |
| 3 | 6 | 7 | 6 | 47 | true |

- 1 mark: pass 2 low = 4, high = 7 and mid = 5 (all three correct)
- 1 mark: pass 3 low = 6, high = 7 and mid = 6 (all three correct)
- 1 mark: data[mid] and found correct in both rows 2 and 3 (38, false, 47, true)

Maximum 3.

Allow follow through (FT) from an incorrect mid in the data[mid] column, using the candidate's own mid value and the array above, and in the later low/high/found values where they follow correctly from the candidate's earlier values.
Accept 'F'/'T' or 0/1 for found.
Do not accept a row marked as correct if any of its three marked values is missing.

Iteration 1: low = 0, high = 8, mid = 8 DIV 2 = 4, stock[4] = 21. 21 < 26 so low = 5.
Iteration 2: low = 5, high = 8, mid = 13 DIV 2 = 6, stock[6] = 34. 34 > 26 so high = 5.
Iteration 3: low = 5, high = 5, mid = 5, stock[5] = 26. Equal, so found = true and the loop ends.
Final value of mid is 5.

- Iteration 1: mid = 4 and stock[mid] = 21 (1)
- Iteration 2: low = 5, high = 8 (1)
- Iteration 2: mid = 6 and stock[mid] = 34 (1)
- Iteration 3: low = 5, high = 5, mid = 5, stock[mid] = 26 AND final value of mid stated as 5 (1)

Allow follow through from an incorrect mid in a previous row for the following low/high/mid values, provided the algorithm is applied correctly. Do not accept the final answer given as 26 (this is the value, not the index). Max 4.

45 becomes the root. 28 < 45 goes left. 61 > 45 goes right. 33 < 45, > 28 so right child of 28. 17 < 28 so left child of 28. 52 > 45, < 61 so left child of 61. 70 > 61 so right child of 61.
Post-order visits left subtree, right subtree, then the node: left subtree of 28 gives 17, 33, 28; right subtree of 61 gives 52, 70, 61; then root 45.

(a)
- Root 45 with 28 as left child and 61 as right child (1)
- 17 and 33 as left and right children of 28, and 52 and 70 as left and right children of 61 (1)
Allow follow through for a tree with structure consistent with the BST rule if one value is misplaced (max 1).

(b)
- Left subtree visited before right subtree, with each node after its children (1)
- 17, 33, 28, 52, 70, 61, 45 (1)
Award follow through on the candidate's tree from (a) for a correct post-order traversal of that tree (1 mark for the correct method; 2 if fully correct). Max 4 in total.

mystery(0) = 0 (base case). mystery(1) = mystery(0) - 1 = -1. mystery(2) = 2 + mystery(1) = 1. mystery(3) = mystery(2) - 1 = 0. mystery(4) = 4 + mystery(3) = 4. mystery(5) = mystery(4) - 1 = 3. Output: 3.

- mystery(0) = 0 and mystery(1) = -1 (1)
- mystery(2) = 1 and mystery(3) = 0 (1)
- mystery(4) = 4 (1)
- mystery(5) = 3 and output stated as 3 (1)

Award follow through from an earlier incorrect value where the correct rule is applied to it. Max 4.

P is the NAND of A and B: 0 only when A and B are both 1, so 1,1,1,1,1,1,0,0. R is B OR C: 0,1,1,1,0,1,1,1. Q = P AND R row by row: 0,1,1,1,0,1,0,0.

- Column P fully correct: 1,1,1,1,1,1,0,0 (1)
- Column R fully correct: 0,1,1,1,0,1,1,1 (1)
- Column Q correct for P AND R: 0,1,1,1,0,1,0,0 (2); award 1 mark if only one or two rows are incorrect

Award follow through for Q from incorrect P or R columns. Max 4.

Recursive approach: a subroutine countExhibits(category) starts with the exhibits directly in the category and then calls itself for each sub-category, adding the returned totals. The base case is a category with no sub-categories, which returns its own exhibit count. Each call has its own local variables held on the call stack.

Iterative approach: a loop with an explicit stack or queue of categories still to be processed. Pop a category, add its exhibit count to a running total, push its sub-categories, and repeat until the stack is empty.

Benefits of recursion: matches the self-similar structure of the catalogue, so the code is short, easy to read and easier to maintain; depth need not be known in advance. Drawbacks: each call adds a stack frame, so a very deep catalogue could cause stack overflow; function call overhead makes it slower; it is harder to trace and debug.

Benefits of iteration: no risk of stack overflow from call depth, less memory overhead, usually faster. Drawbacks: needs an explicit stack structure, so the code is longer and harder to understand, and more likely to contain errors.

Conclusion: museum catalogues have limited depth, so recursion's drawbacks are small and its clarity is valuable; recursion is more suitable. A justified alternative is acceptable.

Level 3 (7-9 marks): Thorough knowledge of both recursion and iteration, accurately applied to the catalogue throughout. Benefits and drawbacks of both approaches are discussed in balance, with reasoned evaluation leading to a fully justified conclusion. Few or no errors.
Level 2 (4-6 marks): Good knowledge of both approaches with some application to the catalogue. Some benefits and drawbacks given, but evaluation may be unbalanced or the conclusion only partly justified.
Level 1 (1-3 marks): Basic knowledge of recursion and/or iteration, with little or no reference to the catalogue. Points listed, with no real evaluation or conclusion.
0 marks: No creditworthy response.

Indicative content (not exhaustive):
- Recursion: subroutine calls itself for each sub-category; base case is a category with no sub-categories; totals combined as calls return
- Iteration: loop with explicit stack/queue of unprocessed categories; running total
- Recursion matches the hierarchical structure / depth unknown; short and readable code
- Recursion: stack frames per call, risk of stack overflow for deep nesting; slower due to call overhead; harder to debug
- Iteration: less memory, no stack overflow, faster; but longer, more complex code needing an explicit stack
- Conclusion with justification linked to the expected depth of the catalogue, maintainability or memory
Allow either conclusion if justified. Do not accept a conclusion with no justification above Level 2. Missing base case described as 'recursion stops' alone should not be credited as a separate point.

Bubble sort: repeatedly compares adjacent items and swaps them if out of order, making passes until a pass has no swaps. Time \(O(n^2)\) in the worst case, space \(O(1)\). For 2 000 000 items this is of the order of \(4 \times 10^{12}\) operations, which is impractical.

Merge sort: divide and conquer. The array is repeatedly split in half until single items remain, then the sublists are merged in order. Time \(O(n \log n)\), about 42 000 000 operations for this data. Space \(O(n)\) for the temporary lists.

Linear search: checks each item in turn until the target is found or the end is reached. Time \(O(n)\), space \(O(1)\). Works on unsorted data.

Binary search: requires sorted data. Compares the target with the middle item and discards half of the remaining data each time. Time \(O(\log n)\), about 21 comparisons for 2 000 000 items; space \(O(1)\) iteratively.

Recommendation: the data is large, is sorted repeatedly and searched often, so merge sort and binary search are most suitable. The extra memory of merge sort is acceptable. Because new readings are added, the array must be kept sorted (or re-sorted) for binary search to remain valid. Linear search would only be justified if the data were small or rarely searched.

Level 3 (7-9 marks): Accurate and detailed description of all four algorithms with correct complexities. Reasoning is applied to the size of the data set, the repeated sorting and the frequent searching. Both time and space trade-offs are evaluated, and a fully justified recommendation is made. Few or no errors.
Level 2 (4-6 marks): Reasonable description of most algorithms and some correct complexities. Some application to the scenario. Evaluation partial, or the recommendation only partly justified.
Level 1 (1-3 marks): Basic description of one or more algorithms or isolated complexities, little application to the scenario, and no or minimal recommendation.
0 marks: No creditworthy response.

Indicative content (not exhaustive):
- Bubble sort: adjacent comparisons and swaps over repeated passes; O(n^2) time; O(1) space
- Merge sort: split into halves, merge in order (divide and conquer); O(n log n) time; O(n) space
- Linear search: check each item in order; O(n); works on unsorted data
- Binary search: needs sorted data; halves the search area each time; O(log n)
- Application: 2 000 000 items makes O(n^2) impractical; frequent searches favour O(log n); new readings added mean data must be re-sorted/kept sorted
- Trade-off: merge sort's extra memory vs speed
- Justified recommendation, e.g. merge sort and binary search
Allow 'n squared' and 'n log n' written in words. Do not accept 'bubble sort is slow' without reference to complexity or data size as a Level 3 point. Allow an alternative recommendation (e.g. linear search for small or unsorted data) only if justified.

Round robin: each process receives a fixed time slice in turn from a queue; when the slice expires a timer interrupt occurs, the ISR saves the process state (registers, PC) and the next process is loaded. Benefits: fair, no starvation, simple, short look-ups get a turn quickly. Drawbacks: monitoring process has no priority so may wait behind many others and miss its deadline; context-switch overhead if the slice is small; the back-up is repeatedly interrupted.

Shortest job first: the process with the smallest estimated run time is chosen next. Benefits: look-ups complete quickly and average waiting time is minimised. Drawbacks: needs estimates of run time; the long back-up could be starved while short jobs keep arriving; it does not consider deadlines, so the monitoring process is not guaranteed to run promptly.

Multi-level feedback queue: several queues of differing priority; new processes enter the highest queue; a process that uses its whole time slice moves down a queue, while processes that block for I/O stay high. Benefits: the monitoring process can be given top priority; short look-ups finish in the upper queues; the back-up drifts to the lowest queue and runs when the others are idle. Drawbacks: more complex to implement and tune; the back-up may be delayed for a long time unless processes are promoted after waiting (ageing).

Operating system role: the scheduler decides which ready process gets the processor. A timer interrupt (or an I/O or sensor interrupt) is detected at the end of the fetch-decode-execute cycle; the interrupt service routine runs, the current process's register contents are stored in its process control block, and the scheduler loads the state of the chosen process so it resumes. A high-priority sensor interrupt can pre-empt a lower-priority process.

Conclusion: multi-level feedback queue is best because it combines priority for the time-critical monitoring process with quick completion of short jobs and eventual completion of the back-up.

Extended response, 12 marks, levels of response. Award the level from the overall quality of the reasoning, then position the mark within the level. Indicative content is not exhaustive.

Indicative content (AO1 knowledge):
- Round robin: fixed time slice, processes served in turn, pre-emption by timer interrupt.
- Shortest job first: shortest (estimated) run time chosen next.
- Multi-level feedback queue: several queues with priorities; processes move between queues depending on behaviour; each queue may use a different algorithm.
- Scheduler selects the next process; interrupt causes the ISR to run; registers/PC saved and restored (context switch); interrupts are checked at the end of the fetch-decode-execute cycle.
- Allow priority-based interrupts pre-empting lower-priority work.

Indicative content (AO2 application to the hospital server):
- Round robin: fair to look-ups; monitoring process not guaranteed to meet its deadline; back-up repeatedly interrupted; context-switch overhead.
- Shortest job first: look-ups favoured; back-up may starve; run times must be estimated; no deadline handling.
- Multi-level feedback queue: monitoring in the top queue; look-ups finish quickly; back-up in the lowest queue runs when the system is idle; complexity.

Indicative content (AO3 evaluation):
- Weighing the algorithms against the time-critical requirement and starvation risk.
- A justified recommendation (multi-level feedback queue expected; accept any other choice supported by valid reasoning, e.g. round robin with a short slice, but a real-time requirement must be addressed).
- Allow mention of ageing or a real-time operating system as a further point.

Level 3 (10-12 marks): Thorough knowledge of all three algorithms and of the interrupt/context-switch role. Applies knowledge consistently to the three processes. Balanced evaluation of benefits and drawbacks leading to a well-justified conclusion. Reasoning is logical and fully supported. Top of the level: all four checklist bullets addressed with specific, correct detail.

Level 2 (5-9 marks): Good knowledge of at least two algorithms, some correct reference to interrupts or the scheduler. Some application to the context, but not for every process. Some evaluation; the conclusion may be partly justified or the discussion unbalanced.

Level 1 (1-4 marks): Basic knowledge, e.g. a description of one or two algorithms with little accuracy. Limited or generic application to the scenario. Little or no evaluation; any conclusion is unsupported.

0 marks: no creditable response.

Do not accept: definitions that merely restate the algorithm name; confusing scheduling with memory management (paging). Do not award Level 3 if no conclusion is given. No follow through applies to this question; the conclusion is credited for the quality of its justification, not for which algorithm is chosen.

7B in hexadecimal: \(7 \times 16 + 11 \times 1 = 112 + 11 = 123\).

• 123 (1 mark)
Do not accept 123 with a base subscript other than 10.

45 in 8-bit binary is 00101101. Invert the bits to give 11010010. Add 1 to give 11010011. Check: \(-128 + 64 + 16 + 2 + 1 = -45\).

• 11010011 (1 mark)
Do not accept sign and magnitude answers (10101101). Do not accept fewer or more than 8 bits.

Compare bit by bit; XOR gives 1 only when the bits differ.
10110110
11110000
--------
01000110

• 01000110 (1 mark)
Do not accept the result of AND (10110000) or OR (11110110).

Step 1: XOR bit by bit.
11010110 XOR 01100101 = 10110011 (bits differ in positions 1, 3, 4, 7, 8 from the left, giving 1,0,1,1,0,0,1,1).
Step 2: Logical shift right by two places: drop the two least significant bits (11) and insert two 0s at the left.
10110011 >> 2 = 00101100.
Final value: 00101100 (2C in hexadecimal).

- 1 mark (method/accuracy): correct result of the XOR, 10110011 (may be shown in working only).
- 1 mark (accuracy): correct logical shift right of two places applied to the XOR result, giving 00101100.

Follow through: award the second mark for a correct two-place logical shift right of an incorrect 8-bit XOR result shown in the working area.
Allow: the final answer given without working for both marks if it is 00101100.
Do not accept: an answer of fewer than 8 bits, e.g. 101100, unless leading zeros are clearly implied; an arithmetic shift or a shift in the wrong direction.

(a) 45 in binary is 00101101. Invert the bits: 11010010. Add 1: 11010011.
(b) 01101110 is 110 and 00110111 is 55. Adding the bits gives 10100101. The sign bit is now 1, so the result would be read as -91, but 110 + 55 = 165, which exceeds 127. Overflow has occurred.
(c) Step 1: 10110110 XOR 11110000 = 01000110. Step 2: shifting 01000110 right by two places and filling with zeros gives 00010001.

(a) Max 2
- 1 mark: correct method, e.g. 45 = 00101101 and invert/add 1 (or 256 - 45); allow for a correct intermediate such as 11010010.
- 1 mark: 11010011.
- Award both marks for the correct answer without working.

(b) Max 2
- 1 mark: 10100101.
- 1 mark: overflow identified, with a valid reason, e.g. the result 165 is outside the range -128 to 127 / two positive numbers have produced a result with sign bit 1 (negative).
- Do not accept 'carry' alone. Do not award the reason mark without 'overflow' or an equivalent description.

(c) Max 2
- 1 mark: 01000110 after Step 1.
- 1 mark: 00010001 after Step 2.
- FT: award the Step 2 mark for a correct logical right shift by two of the candidate's Step 1 value, provided that value is 8 bits.

When a parameter is passed by value, the procedure receives a copy of the data, so any change is made to the copy only and the original variable keeps its value. When a parameter is passed by reference, the procedure receives a reference (the memory location) to the original variable, so any change made inside the procedure is also seen in the original variable.

Max 2. One mark for each matching statement:
- By value: a copy of the value is passed / the original variable is not changed by the procedure (1)
- By reference: the address / a reference to the original variable is passed, so the original variable is changed by the procedure (1)

Allow: 'the original value is overwritten' for by reference.
Do not accept: statements that only describe one method with no contrast, unless both methods are covered. Do not accept 'by reference copies the variable'.
A response that gives only the two descriptions without mention of the effect on the original variable can earn a maximum of 1 mark.

Recursive version (pseudocode):

function digitSum(n)
if n < 10 then
return n
else
return (n MOD 10) + digitSum(n DIV 10)
endif
endfunction

Iterative version:

function digitSum(n)
total = 0
while n > 0
total = total + (n MOD 10)
n = n DIV 10
endwhile
return total
endfunction

The recursive version repeats by calling itself with n DIV 10 until the base case n < 10 is met. The iterative version repeats using a while loop which ends when n reaches 0. Each recursive call is stored on the call stack with its own parameters and return address, so memory use grows with the number of digits. The iterative version only needs the variables n and total, so memory use is constant. The recursive version is usually shorter and closer to the mathematical definition; the iterative version is usually faster as there is no call overhead.

Max 4. Award one mark per point, up to 2 marks for each approach, or for matched comparison points.

Repetition:
- Recursion repeats by the subroutine calling itself (with a smaller/modified argument) (1)
- ... until a base case/stopping condition is met (1)
- Iteration repeats using a loop (for/while/do...until) (1)
- ... until a loop condition becomes false/is met (1)

Memory:
- Recursion creates a new stack frame for each call (holding parameters/return address/local variables) (1)
- ... so memory use increases with the number of digits/depth of recursion; risk of stack overflow (1)
- Iteration reuses the same variables so memory use is constant/lower (1)

Other valid points (max 1): recursive code is shorter/more elegant; recursion has function-call overhead so is slower.

Allow 'function calls itself'. Do not accept 'recursion is faster' or 'iteration is more efficient' without a reason. Do not accept a description of only one approach for more than 2 marks. Comparison points may be paired in a table; a pair of matched statements earns 2 marks.

Insertion sort takes each item in turn and shifts it left into its correct position in the sorted part of the array. In the worst and average cases this needs about \(n^2\) comparisons, so the time complexity is \(O(n^2)\). It works in the original array so it needs only constant extra memory, \(O(1)\).

Merge sort repeatedly divides the array into halves and merges the sorted halves. It has \(O(n \log n)\) time complexity in all cases, but the merge step needs extra arrays so it needs \(O(n)\) additional memory.

For 50 000 items, \(n^2\) is about 2.5 billion operations, compared with roughly 800 000 for \(n \log n\), so merge sort is much faster at the cost of more memory.

Max 4. One mark per point.

Time complexity:
- Insertion sort is \(O(n^2)\) (polynomial) in the worst/average case (1)
- Merge sort is \(O(n \log n)\) (1)
- Merge sort is faster/scales better for large data sets such as 50 000 items; insertion sort becomes slow (1)
- Insertion sort is \(O(n)\) in the best case (already sorted data) (1)

Memory:
- Insertion sort is in place / needs no (significant) additional array, \(O(1)\) extra space (1)
- Merge sort needs additional arrays/space for the sub-lists when merging, \(O(n)\) (1)

Allow 'quadratic' for \(O(n^2)\) and 'linearithmic' for \(O(n \log n)\). Allow 'uses more RAM' for extra memory. Do not accept 'merge sort is faster' without reference to complexity or data size, unless a different mark point is credited. Each comparison point must be stated for both algorithms or as a clear contrast; a single-algorithm statement earns 1 mark only if the contrast is implied.

If changing the parameter alters the caller's original variable, the procedure must have received a reference to the variable's memory location rather than a copy of its value. The method is therefore passing by reference.

- By reference / byRef (1)

Allow: 'pass by address'.
Do not accept: 'by value', 'global variable'.

Comparing with the middle item of a sorted list and halving the search space on each comparison describes a binary search. It has logarithmic time complexity, \(O(\log n)\).

- Binary search (1)

Allow: 'binary chop'.
Do not accept: 'linear search', 'divide and conquer' on its own.

Passing by value gives the subroutine its own copy of the data, so changes are local. Passing by reference gives access to the original memory location, so changes affect the caller's variable.

Any two from (1 mark each):
- By value, a copy of the value is passed; by reference, the address/reference of the variable is passed
- By value, changes inside the procedure do not alter the original variable; by reference, they do
- By value, the original variable is protected/unaffected; by reference, the original can be modified
Do not accept answers that describe only one method. Max 2.

Without a stopping condition, or without progress towards it, the function would call itself indefinitely and cause a stack overflow.

- A base case / terminating condition that returns without a further recursive call (1)
- A recursive call (to itself) using modified argument(s) that progress towards the base case (1)
Allow 'stopping condition'. Do not accept 'a loop'. Max 2.

Each comparison halves the remaining search space, giving logarithmic time complexity. The halving only works if the data is ordered.

- O(log n) / logarithmic (1)
- The data/array must be sorted / in order (1)
Allow O(log2 n). Do not accept O(n) or 'ascending only' being required as the sole detail unless sorted is implied. Max 2.

A stack is last in, first out. The last value pushed, 2, is removed first, leaving 9 at the top.

(a) 2 (1)
(b) 9 (1)
Follow through: award (b) if the candidate's (a) is a value from the list and (b) is the correct next top for that answer only where consistent with LIFO behaviour. Max 2.

FormID in Student refers to the primary key of Form, so it is a foreign key. It creates the relationship and supports referential integrity.

- Foreign key (1)
- Links/relates the Student table to the Form table by matching the primary key of Form / enforces referential integrity (1)
Do not accept 'primary key' or 'secondary key'. Max 2.

After finishing the current instruction, the processor checks for interrupts of higher priority. If one is present, the current register contents are saved and the ISR is executed.

- A (section of) code/subroutine that is executed to handle/respond to a specific interrupt (1)
- Checked at the end of each fetch-decode-execute cycle / after the current instruction has completed (1)
Do not accept 'at the start of the cycle'. Max 2.

De Morgan: NOT (P AND Q) = (NOT P) OR (NOT Q). The expression NOT (P AND Q) is the output of a NAND gate.

- NOT P OR NOT Q (any accepted notation, e.g. ¬P ˅ ¬Q, P-bar + Q-bar) (1)
- NAND (1)
Do not accept expressions that retain brackets around AND. Max 2.

+5 is 00000101. Invert the bits to give 11111010, then add 1 to give 11111011.

- Correct 8-bit representation 11111011 (2)
If incorrect, award 1 mark for 00000101 shown as the starting value with bits inverted (11111010), or for a correct method of invert and add 1 with one arithmetic slip. Max 2.

(a) An interrupt is a signal from hardware or software that tells the processor an event needs attention, so the processor pauses its current task and runs an Interrupt Service Routine.
(b) Two events from different sources, for example a key press on the keyboard and the printer reporting that it is out of paper.

(a) 1 mark: a signal (sent to the processor) indicating that an event requires attention / that causes the current task to be paused. Allow: causes an ISR to run. Do not accept: 'a error' or 'the computer stops' with no reference to a signal or to attention.
(b) 1 mark per valid, distinct event, max 2. e.g. a key press / mouse click; printer out of paper or job complete; a hardware failure; a timer expiring; a software error such as division by zero. Do not accept two answers that are the same event worded differently. Do not accept vague answers such as 'the printer'.

(a) A GPU contains very many simple cores, so the same calculation can be applied to a large number of data values simultaneously. Weather simulation repeats similar calculations across many points, which suits this.
(b) For example training machine learning models.

(a) 1 mark per point, max 2:
- has many cores / thousands of processing units
- can process many data items at the same time / parallel processing
- optimised for repeated, similar calculations (e.g. matrix or floating point operations)
- high throughput of data
Do not accept: 'faster' or 'better' with no reason. Do not accept 'higher clock speed'.
(b) 1 mark for one valid use, e.g. machine learning / neural network training; data mining; password cracking; cryptocurrency mining; physics or scientific modelling. Do not accept 'gaming' or 'video editing' (graphics uses).

(a) The parameter score is passed by reference, so the change made in the procedure alters points: points becomes 10 + 5 = 15. The parameter bonus is passed by value, so the procedure works on a copy; setting it to 0 does not change extra, which remains 5. (b) Local variables exist only inside their subroutine, so they cannot be altered unintentionally elsewhere, names can be reused without clashes, and the memory they use is released when the subroutine finishes.

(a) Maximum 2
- 15 for line 09 (1)
- 5 for line 10 (1)
Allow each mark independently. Do not accept 0 for line 10.

(b) Maximum 2, one mark per valid benefit
- Cannot be changed accidentally / unintentionally by other parts of the program, so fewer side effects (1)
- Same identifier can be reused in different subroutines without conflict (1)
- Memory is released when the subroutine ends / uses less memory (1)
- Subroutine is self-contained so it is easier to reuse, test and debug (1)
Do not accept 'faster' or 'easier' without a reason. Do not accept two statements that make the same point.

The loop visits every element of the array. The condition must test whether the current reading is strictly greater than limit, so gap (A) is > limit. When the condition is true the counter total must increase by one, so gap (B) is total = total + 1. For example, with readings [0, 5, 2, 9] and limit 2, the function returns 2.

(A) 1 mark: > limit
- Allow > limit in any equivalent notation for a high-level language.
- Do not accept >= limit or == limit.

(B) 1 mark: total = total + 1
- Allow total += 1 or total++ or equivalent increment by one.
- Do not accept total = 1 or total + 1 on its own (no assignment).

Maximum 2 marks. Each gap is marked independently.

The counter used on line 05 is 'count', so line 02 must initialise count (not total) and line 08 must return count. The array is 0-indexed, so the loop must run from 0 to readings.length - 1 (line 03). The specification says 'greater than or equal to', so line 04 needs >= rather than >.

One mark per correct error identified with a valid correction, maximum 4:
- Line 02: count = 0 (initialise count instead of total) (1)
- Line 03: for i = 0 to readings.length - 1 (start at 0 and end at length - 1; both parts needed) (1)
- Line 04: if readings[i] >= limit then (1)
- Line 08: return count (1)
Allow equivalent corrections, e.g. renaming count to total on line 05 together with the return on line 08 stays as total (award the marks for lines 02 and 08 together if the renamed variable is consistent across lines 02, 05 and 08 and the line 05 change is shown). Allow readings.length - 1 written as an equivalent expression, e.g. 'for i = 0 to readings.length-1'. Do not accept a correct line number with an unchanged line. Do not accept a rewrite of the whole function without line numbers unless each change is clearly identifiable. If more than four lines are given, mark only the first four.

The base case is an empty search range, which occurs when low > high. If the middle item is less than the target, the target must lie in the upper half, so the new low is mid + 1. Otherwise it lies in the lower half, so the new high is mid - 1. The array has 12 items indexed 0 to 11, so the initial call uses low = 0 and high = 11 (or club.length - 1).

(a) Maximum 3:
- (1) low > high (1) Allow high < low. Do not accept low >= high.
- (2) mid + 1 (1)
- (3) mid - 1 (1)
(b) Maximum 1:
- position = findName(club, "Rowan", 0, 11) (1) Allow club.length - 1 or 12 - 1 for 11. Both 0 and the upper bound must be correct, and the argument order must match the function definition. Do not accept 12 as the high value.

The loop must visit every index from 0 to loans.length - 1 inclusive (the for loop is inclusive of both ends). Each element is tested for equality with target using ==. When a match is found, position is overwritten with the current index i, so after the loop position holds the index of the last match. If there is no match, position keeps its initial value of -1. The function then returns position.

1 mark per gap, maximum 5:
- GAP 1: 0 (allow any equivalent expression evaluating to 0)
- GAP 2: loans.length - 1 (allow loans.length - 1 written as a correct equivalent, e.g. len(loans)-1). DNA loans.length alone, as this would access an index outside the array.
- GAP 3: == (allow = if used as the comparison in the candidate's chosen language; allow 'equals'). DNA != or any other operator.
- GAP 4: i
- GAP 5: position

Allow correct alternative loop forms only if all gaps remain consistent with a working function (e.g. loop running from loans.length - 1 down to 0 is not accepted here, as the structure of the code is given). Each gap is marked independently; no follow through is needed.

The loop compares each reading with the one before it. If it is greater, the current run grows by one; otherwise a new run of length 1 starts. Whenever current exceeds best, best is updated. After the loop, best holds the longest run.

(a) (1) > (2) current + 1 (3) 1 (4) current (5) best

(b) The runs are 4,6,7 (length 3), 3,5,8,9,10 (length 5) and 2 (length 1). The longest is 5, so the function returns 5.

(a) One mark per correct gap, maximum 5:
- (1) > (strictly greater than). Do not accept >= . Allow readings[i - 1] < readings[i] only if the whole condition is rewritten consistently; otherwise DNA.
- (2) current + 1. Allow current = current + 1 or equivalent (e.g. current += 1).
- (3) 1. DNA 0.
- (4) current.
- (5) best. DNA current.
Allow any equivalent syntax that a competent programmer could interpret. Each gap is marked independently.

(b) 1 mark: 5.
Award follow through for (b) only if the candidate's trace of their own answer to (a) is correct for the logic they wrote; otherwise award the mark for 5 only.

By reference, the procedure receives the address of the original variable, so any assignment to score inside resetScore changes the caller's variable. By value, a copy is made, so the original is unaffected.

Max 2:
- The parameter refers to / is the address of the original variable (1)
- Any change made in the procedure persists in / alters the original variable after the procedure ends (1)
Allow: contrast with by value where a copy is changed and the original is unchanged, for either mark.
DNA: 'the variable is global' without reference to the original being changed.

Binary search needs sorted data, which is already the case. Each comparison discards half of the remaining items, giving logarithmic time complexity, about 20 comparisons for 1 000 000 items, whereas a linear search may need up to 1 000 000.

Max 2:
- The data is already sorted, which binary search requires (1)
- Binary search halves the remaining items on each comparison / has O(log n) complexity (1)
- Linear search may need to check every item / has O(n) complexity, so binary search needs fewer comparisons (1)
Allow: 'faster' only when supported by one of the above points.

First check that the stack is not empty (top is not -1). Then read the value at array[top] to return, and decrement top so that the next item becomes the top.

Max 2:
- Check that the stack is not empty / underflow check (1)
- Return / copy the item at position top AND decrement top by 1 (1)
Allow: the order of reading and decrementing if the correct item is returned.
DNA: removing items from the bottom of the stack.

On meeting a dead end, the program undoes its most recent moves until it reaches the last decision point that still has an unexplored option, and then tries that option instead.

Max 2:
- Return / go back along the path to the most recent decision point / junction (1)
- Choose / try a different, previously untried route from there (1)
Allow: 'abandon the failed path and try another' for one mark only.
DNA: restarting from the beginning of the maze.

ClubID in Pupil acts as a foreign key. The database system only accepts a ClubID value in Pupil if the same value exists in Club, and prevents deletion of a Club record that is still referenced, so no orphan records occur.

Max 2:
- Values in the foreign key field (ClubID in Pupil) must match an existing primary key value in Club (1)
- A record in Club cannot be deleted / changed while records in Pupil refer to it, so no orphan records exist (1)
Allow: 'cascading delete' for second mark.

Processes wait in a queue. The process at the front runs for a fixed time slice (quantum). If it has not finished, it is placed at the back of the queue and the next process is given the processor.

Max 2:
- Each process is allocated a fixed time slice / quantum in turn (1)
- An unfinished process is moved to the back of the queue when its time slice ends (1)
Allow: processes finishing early release the processor.
DNA: processes run in order of priority or length.

Inheritance allows the subclass Lorry to reuse the attributes and methods defined in the superclass Vehicle without rewriting them, while also defining extra attributes or methods or overriding existing ones.

Max 2:
- Lorry (subclass) gains / reuses the attributes and methods of Vehicle (superclass) (1)
- Lorry can have additional attributes / methods of its own or override those from Vehicle (1)
DNA: Vehicle inheriting from Lorry.

A compiler translates the complete source code into an executable file before execution begins, so the program can run without the translator. An interpreter translates and runs the source line by line each time the program is run.

Max 2, for one matched difference:
- Compiler translates the whole program before it is run / produces an executable (1)
- Interpreter translates and executes line by line / statement by statement, and does not produce a separate executable (1)
Allow: other valid differences, e.g. errors reported for the whole program versus at the line reached.
Both halves are required for 2 marks.

One concern is bias. If the decision rules or training data reflect past discrimination, qualified applicants from particular groups may be unfairly rejected, and the lack of transparency makes it hard to challenge the outcome.

Max 2:
- Identifies a valid concern, e.g. bias / discrimination in the rules or training data / lack of transparency or accountability (1)
- Development of the impact on applicants, e.g. suitable applicants unfairly rejected / cannot challenge the decision (1)
DNA: 'it is not fair' without development.

When passed by value, a copy of the contents of price is given to applyDiscount. Any reduction is made to the copy, so the original price in the calling code keeps its old value. When passed by reference, applyDiscount works on the original variable (it receives its memory location), so the ten per cent reduction is still in effect after the procedure ends.

Max 2 from:
- By value: a copy of the value of price is passed to the procedure (1)
- ...so changes made inside applyDiscount do not affect the original variable / the original price is unchanged after the call (1)
- By reference: the address / a pointer to the original variable is passed (1)
- ...so changes made inside applyDiscount alter the original variable / the discounted price is kept after the call (1)

Award 1 mark for the by value description and 1 mark for the by reference description if both are linked to the example. Allow 'reference' described as 'the procedure uses the same variable'.
Do not accept a response that only says 'one is a copy and the other is not' without stating the effect on the original variable.
Do not award marks for definitions that are not applied to price or applyDiscount, apart from one mark maximum for correct general statements.

Passing by value gives the procedure its own copy of the argument, so any change is made to the copy and the original array is unchanged when the procedure ends. Passing by reference gives the procedure the memory location of the original array, so changes made inside the procedure alter the original array. To change the stored scores, scores should therefore be passed by reference (byRef).

Max 3 from:
- By value, a copy of the data/argument is passed to the procedure (1)
- ... so changes made in the procedure do not affect the original/calling variable, e.g. the original scores array stays unchanged (1)
- By reference, the address/memory location of the original variable is passed (1)
- ... so changes made in the procedure change the original data, e.g. the scores array in the calling program is updated (1)
- Application: scores must be passed by reference for the procedure to change its values (1)

Allow 'pointer' for address. Do not accept 'by value cannot be used' or answers that only define the terms without any difference. Maximum 2 marks if the array scores is not referred to.

The three processes are held in a ready queue. The process at the front is given the processor for a fixed time slice (quantum). When the time slice ends, an interrupt occurs, the process's state is saved and it is placed at the back of the queue. The next process is then taken from the front and run. This repeats until each process completes, so every process receives an equal share of processor time.

Max 3 from:
- Processes are held in a (ready) queue (1)
- Each process is allocated a fixed/equal time slice (quantum) of processor time (1)
- When the time slice expires, an interrupt/timer causes the process to stop, and its state/registers are saved (1)
- ... the process is moved to the back of the queue (1)
- The next process at the front of the queue is then run / this repeats in a cycle until processes complete (1)
- A process that finishes before its slice ends is removed from the queue / leaves early (1)

Do not accept 'processes run at the same time'. Do not accept 'the most important process runs first'.

(a) cost is passed by value, so price starts as a copy of 20. Line 02 makes price 15. basket is passed by reference and starts at 0, so line 03 sets basket to 0 + 15 = 15. Line 09 outputs 20 and line 10 outputs 15.

(b) By value: a copy of the value of cost is placed in the local variable price. Changing price alters only the copy, which is discarded when the procedure ends, so cost remains 20. By reference: basket refers to the address of the original variable, so line 03 changes the original and the new value 15 remains after the procedure ends.

(a) Max 2
- 20 output by line 09 (1)
- 15 output by line 10 (1)
Allow outputs in the correct order if line numbers are not given. Accept 20 then 15 only.

(b) Max 3
- cost/price is passed by value (1)
- ...so price is a (local) copy of the value / changes affect only the copy, not the original variable cost (1)
- basket is passed by reference, so the procedure receives the address/memory location of the original variable (1)
- ...so changes made to basket inside the procedure change the original variable and persist after the procedure ends (1)
Do not accept 'global' or 'local' as the sole explanation of the difference. Do not accept a bare statement that 'by reference is permanent' without reference to the original variable or its address. Mark the best three points.

(a) With pass by value the subroutine receives a copy of the value, so changes made to the parameter inside the subroutine are lost when it ends and the original variable is unchanged. With pass by reference the subroutine receives the address of the original variable, so changes made inside the subroutine alter the original.
(b) By value: the procedure works on a copy of the array, so readings keeps its original values. By reference: line 3 changes the elements of the original array, so each value in readings is increased by 2.
(c) The code can be reused by calling it many times without rewriting it; a fault or change need only be corrected in one place, which improves maintainability and testing; the main program is shorter and easier to read.

(a) Max 2:
- Value: a copy of the data is passed / original not changed by the subroutine (1)
- Reference: the memory address/reference to the original is passed / original can be changed by the subroutine (1)
Do not accept 'value is passed' without reference to a copy. Allow one mark for a correct but undeveloped statement only if both methods are addressed.

(b) Max 2:
- By value: readings is unchanged / copy is altered only (1)
- By reference: all elements of readings are increased by 2 (1)
Allow 'each temperature goes up by 2'. Do not accept 'the array is changed' without stating how.

(c) Max 2, one mark per benefit (benefit must be linked to a reason where indicated):
- Reusable: code written once and called many times (1)
- Maintainable: a change/fix needs to be made in one place only (1)
- Easier to test or debug in isolation (1)
- Main program shorter / more readable (1)
Do not accept 'quicker to run' or 'uses less memory' on their own.

First iteration: low = 0, high = 7, so mid = 7 DIV 2 = 3 and values[3] = 19. 19 is not equal to 31 and is less than 31, so low becomes 4.
Second iteration: low = 4, high = 7, so mid = 11 DIV 2 = 5 and values[5] = 31. This equals the target, so the function returns 5. No third row is needed.

- 1 mark: first row completed correctly: mid = 3 and values[mid] = 19.
- 1 mark: second row completed correctly: low = 4, high = 7, mid = 5, values[mid] = 31.

Allow follow through only if the first row is wrong but the second row is consistent with the candidate's own first row. Do not accept extra rows after the row containing 31. Mark each row as a whole. Do not award the second mark if the low value is not 4 (unless following through from a wrong first row).

Iteration 1: low = 0 and high = 7, so mid = 7 DIV 2 = 3 and ages[3] = 22. As 22 > 15, high becomes 2.
Iteration 2: low = 0 and high = 2, so mid = 1 and ages[1] = 9. As 9 < 15, low becomes 2.
Iteration 3: low = 2 and high = 2, so mid = 2 and ages[2] = 15. This equals the target, so found becomes true and the loop ends. A fourth iteration is not needed.

One mark per correctly completed row (whole row marked together), maximum 3:
- Row 1: 0, 7, 3, 22
- Row 2: 0, 2, 1, 9
- Row 3: 2, 2, 2, 15

Do not award a mark for a row containing any incorrect value. Row 4 must be blank or crossed through; if row 4 contains values, do not award the mark for row 3. Allow follow through only if an earlier row is wrong but the later row is correct for the candidate's previous values (low and high consistent with the algorithm), up to a maximum of 2 marks in that case.

Pass 1: 4<6 no swap; 6>2 swap -> 4,2,6,5,1; 6>5 swap -> 4,2,5,6,1; 6>1 swap -> 4,2,5,1,6. 3 swaps.
Pass 2: 4>2 swap -> 2,4,5,1,6; 4<5 no swap; 5>1 swap -> 2,4,1,5,6; 5<6 no swap. 2 swaps.
Pass 3: 2<4 no swap; 4>1 swap -> 2,1,4,5,6; 4<5, 5<6 no swaps. 1 swap.
Pass 4: 2>1 swap -> 1,2,4,5,6; remaining comparisons need no swap. 1 swap.
Pass 5: no swaps, so changed stays false and the loop ends. rounds = 5, which is output by line 17.

4 marks in total, one mark per bullet:
- Pass 1 row correct: [4,2,5,1,6] and 3 swaps (both needed) (1)
- Pass 2 row correct: [2,4,1,5,6] and 2 swaps (both needed) (1)
- Passes 3 and 4 rows both correct: [2,1,4,5,6] with 1 swap; [1,2,4,5,6] with 1 swap (1)
- Pass 5 row correct: [1,2,4,5,6] with 0 swaps AND output value 5 (1)

Allow: follow through for the swap counts and final output if the array contents are consistent with an earlier error in the trace (output must equal the number of passes the candidate has shown until a pass with 0 swaps).
Do not accept: array contents written with missing values or in the wrong order for the mark.
DNA: a sixth pass row or an output other than the number of passes completed.

Row 1 (given): low 0, high 8, mid 4, arr[4] = 27. 27 > 20, so high = 3.
Row 2: low 0, high 3, mid = 3 DIV 2 = 1, arr[1] = 9, steps 2. 9 < 20, so low = 2.
Row 3: low 2, high 3, mid = 5 DIV 2 = 2, arr[2] = 15, steps 3. 15 < 20, so low = 3.
Row 4: low 3, high 3, mid = 3, arr[3] = 22, steps 4. 22 > 20, so high = 2.
Now low (3) > high (2), so the loop ends and -1 is returned (20 is not present).
The algorithm is a binary search, which halves the search space each iteration, so the complexity is logarithmic: O(log n).

a) Maximum 4 marks.
- Row 2 correct: 0, 3, 1, 9, 2 (1 mark; whole row marked together)
- Row 3 correct: 2, 3, 2, 15, 3 (1 mark; whole row marked together)
- Row 4 correct: 3, 3, 3, 22, 4 (1 mark; whole row marked together)
- Value returned is -1 (1 mark)
FT: award follow through for a row if it is correct for the candidate's previous row. Do not accept additional rows after row 4 unless the candidate's earlier error causes them (FT applies). Allow blank cells to be filled with the values only; no need to restate the condition.

b) 1 mark
- O(log n) / O(log2 n) / logarithmic complexity
DNA O(n) or O(n log n) or 'log n' without the O notation if the candidate does not mention complexity at all.

i = 2: key = 9. a[1] = 7 is not greater than 9, so nothing moves and the array is unchanged: [3, 7, 9, 2, 5].
i = 3: key = 2. 9, 7 and 3 are each greater than 2 so each shifts one place right (three executions of line 06). 2 is placed at index 0: [2, 3, 7, 9, 5].
i = 4: key = 5. 9 and 7 are shifted right (two executions of line 06); 3 is not greater than 5, so the loop stops. 5 is placed at index 2: [2, 3, 5, 7, 9].
Line 06 executions: i=1 gives 1, i=2 gives 0, i=3 gives 3, i=4 gives 2, total 6.
Worst case: every element must be compared with and shifted past every element before it, so the work grows with the square of n: O(n^2). This occurs when the data starts in reverse order.

1 (a) [4 marks]
- 1 mark: key column correct for all three rows (9, 2, 5). Do not accept if any key is wrong.
- 1 mark: i = 2 array [3, 7, 9, 2, 5]
- 1 mark: i = 3 array [2, 3, 7, 9, 5]
- 1 mark: i = 4 array [2, 3, 5, 7, 9]
- Each array mark is awarded independently, but the whole array must be correct. Award FT for an array mark if it is a correct application of the algorithm to the candidate's own previous row. Allow arrays written without brackets or commas if clearly in order.

1 (b) [1 mark]
- 6. Award FT from the candidate's own trace table only if the answer is consistent with the shifts shown in it.

1 (c) [2 marks]
- (i) 1 mark: O(n^2). Allow O(n squared), quadratic or polynomial. Do not accept O(n) or O(n log n).
- (ii) 1 mark: data in reverse order / descending order / largest value first. Allow 'in the opposite order to the one required'. Do not accept 'unsorted' or 'random' without further detail.

Recursive version: findMax calls itself with position + 1 until the base case (line 02) is met at the last element. Each call waits for the result of the next (line 05), so the calls build up on the call stack and values are compared as the calls return. An iterative version would use a loop with a local variable holding the highest value so far, comparing each element once.

Both approaches examine each element once, so time complexity is linear, O(n). The recursive version uses O(n) stack space because one stack frame is created per element; with millions of readings this is likely to cause a stack overflow error. The iterative version uses O(1) extra space and avoids the overhead of repeated subroutine calls. Recursion can be shorter and closer to the mathematical definition of the problem, but here the code is not noticeably easier to follow. Conclusion: use iteration, because the array is very large and there is no benefit from recursion.

Indicative content (not exhaustive):

Knowledge / understanding:
- Recursion: a subroutine calls itself with a changed argument until a base case is reached
- Base case in the code is when position is the last index (line 02); the recursive call is on line 05
- Iteration uses a loop (e.g. for/while) and a variable holding the current maximum
- Each recursive call creates a stack frame holding parameters, local variables and the return address

Application to the scenario:
- Several million readings gives several million nested calls; the call stack may overflow
- Both approaches are O(n) in time; the recursive version is O(n) in space, the iterative version O(1)
- Function call overhead makes recursion slower in practice
- Recursive code is short and its structure is clear, but no real benefit for a simple linear scan
- Iterative code is easier to trace/debug for large inputs

Evaluation:
- A reasoned conclusion, e.g. iteration is preferable for this task because of the array size; recursion would be acceptable for small arrays or if the stack depth were limited (e.g. divide and conquer which halves the depth)

Level 3 (7-9 marks): Thorough knowledge of both approaches, accurately linked to the code and the large data size. Advantages and disadvantages are fully developed, with correct reference to stack use and complexity. A justified conclusion follows logically from the points made. Well structured, with no significant errors.

Level 2 (4-6 marks): Good knowledge of recursion and iteration. Some application to the scenario, e.g. mentions stack or memory use for a large array. Some balanced discussion, but the conclusion may be limited or only partly justified.

Level 1 (1-3 marks): Basic, generic statements about recursion and/or iteration with little or no link to the code or scenario. Points may be one-sided or listed. Any conclusion is unsupported.

0 marks: No creditable response.

Allow stack overflow, running out of memory for the call stack. Do not accept 'recursion is slower' without a reason. Do not accept 'iteration uses no memory'. Position within a level is decided by the quality of reasoning.

Linear search checks each record in turn until the ISBN is found or the end is reached: O(n) per search, about 200 000 comparisons in the worst case, no extra space and no need for sorted data.

Merge sort divides the array into halves repeatedly, then merges the sorted halves: O(n log n) time and O(n) extra space. Binary search compares the target with the middle item and discards half of the remaining records each time: O(log n), about 18 comparisons for 200 000 records, but it requires sorted data.

The sort is performed once, so its cost is shared over many searches. With only weekly additions, the array can be re-sorted or new items inserted into position infrequently. If many searches are made each day, the total cost of Option A is far greater. Option A would be better only if very few searches were made, or if the data changed constantly. Conclusion: Option B.

Indicative content (not exhaustive):

Knowledge / understanding:
- Linear search: checks items one at a time from the start; works on unsorted data; O(n)
- Binary search: needs sorted data; compares with middle item and discards half; O(log n)
- Merge sort: divide and conquer; splits the list, sorts the parts, merges them; O(n log n) time
- Merge sort needs O(n) additional space; linear and binary searches need O(1) extra space (iterative binary search)

Application to the scenario:
- Sorting is a one-off cost; searching occurs many times a day, so the cost of the sort is spread across many searches
- 200 000 records: linear search up to 200 000 comparisons; binary search around 18
- Weekly additions mean the data is rarely changed, so re-sorting (or inserting) is infrequent and affordable
- Extra memory for the merge sort is acceptable on a modern system / the sort can be run when the system is quiet
- Option A would be preferable if the data changed frequently or there were very few searches

Evaluation:
- A conclusion that is justified using the complexities and the usage pattern

Level 3 (7-9 marks): Accurate and detailed description of all three algorithms. Complexities are correct and are compared. The usage pattern is explicitly used to weigh up the options, with both sides considered. A clear justified conclusion.

Level 2 (4-6 marks): Good knowledge of at least two of the algorithms and some correct use of Big O notation. Some link to the scenario. Limited balance or a conclusion that is only partly justified.

Level 1 (1-3 marks): Basic description of the searches or sort with little or no use of Big O notation or the scenario. Largely unsupported statements.

0 marks: No creditable response.

Allow O(log2 n) for O(log n). Do not accept binary search working on unsorted data. Do not accept 'merge sort is quicker than binary search'. Position within a level is decided by the quality of reasoning.

When a parameter is passed by value, a copy of the argument is made and the procedure works on that copy, so the original variable keeps its value after the call. When a parameter is passed by reference, the procedure is given the address of the original variable, so any assignment to the parameter changes the original variable in the main program.

Max 2 marks, one mark for each point:
- By value: a copy of the value is passed / changes made in the procedure do not affect the original variable (1)
- By reference: the address / location of the original variable is passed / changes made in the procedure do affect the original variable (1)

Allow 'pointer to' or 'reference to' the variable for address.
Do not accept answers that only define the terms without stating the effect on the original variable, e.g. 'by value passes the value'.
A statement that only describes one method scores a maximum of 1 mark unless the contrast with the other method is clear.

A variable declared inside a subroutine and accessible only within that subroutine has local scope. A global variable would be accessible throughout the program.

- Local (1)

Allow: local variable, local scope.
Do not accept: private, global.

When a parameter is passed by value, a copy of the argument's value is made and the procedure doubles only that copy, so the variable in the calling program keeps its original value. When a parameter is passed by reference, the procedure receives the address of the original variable, so doubling score changes the variable in the calling program.

Award 1 mark for each point, maximum 2:
- By value: the original variable / value in the calling program is not changed (the procedure changes only a copy) (1)
- By reference: the original variable in the calling program is changed / updated (the procedure uses the memory address of the original) (1)

Allow: by value, a copy of the data is passed; by reference, a pointer / address to the data is passed, as the explanation of the difference.
Do not accept: answers that only say 'by reference is faster' or that give no effect on the calling program's variable.
Both marks require a comparison relating to the calling program's variable; a definition of each term alone, with no effect stated, scores a maximum of 1.

The loop must visit every index of a 0-indexed array, from 0 up to temps.length - 1 inclusive, because the for loop is inclusive of both ends. The condition must be a strict comparison, so the operator is >.

(A) temps.length - 1 (1 mark). Allow any equivalent expression for the last index, e.g. len(temps) - 1. Do not accept temps.length, as this goes out of bounds.
(B) > (1 mark). Do not accept >=.
Max 2.

If names[mid] is less than target, the target must lie in the upper half, so low must move to mid + 1 (line 9). Otherwise names[mid] is greater than target, so the target is in the lower half and high must become mid - 1 (line 11). The two assignments are swapped.

Line 9 changed to low = mid + 1 (1 mark).
Line 11 changed to high = mid - 1 (1 mark).
Allow the correction to be given by swapping the comparison on line 8 to names[mid] > target, if both lines 9 and 11 are then left unchanged; this scores both marks together.
Do not award a mark where the correct line number is given with an incorrect line of code.
Max 2.

Line 2: total is initialised to 1, so every result would be 1 too large; it must start at 0.
Line 3: the loop is inclusive of both ends, so i reaches weights.length, which is outside a zero-indexed array; the upper bound must be weights.length - 1.
Line 4: the comparison selects parcels lighter than the limit; it must select parcels heavier, so > is needed.

Corrected function:
function heavyTotal(weights, limit)
total = 0
for i = 0 to weights.length - 1
if weights[i] > limit then
total = total + weights[i]
endif
next i
return total
endfunction

Award one mark for each correct line identified and corrected (max 3):
- Line 2: total initialised to 0, e.g. total = 0
- Line 3: upper bound of loop reduced to weights.length - 1, e.g. for i = 0 to weights.length - 1. Allow weights.length - 1 written as an equivalent expression.
- Line 4: comparison changed to greater than, e.g. if weights[i] > limit then

Allow any equivalent correct code, e.g. a while loop on line 3 provided the whole line is rewritten correctly and the loop covers indexes 0 to weights.length - 1.
Do not accept a correction on the wrong line number. Do not accept >= on line 4 (parcels equal to the limit are not heavier than it).
If a candidate changes a correct line (e.g. line 5, 6 or 8) in a way that introduces an error, do not award the mark for that line's change, but this does not remove marks already awarded for the three errors.
One mark per line; each mark is independent.

The variable current counts the length of the present run of readings above limit. If the reading is above the limit the run grows by one (A); otherwise the run is broken and resets to zero (B). Whenever the present run exceeds the longest run so far, best is updated (C). After the loop, best holds the longest run (D).

For part (b) the readings above 6 are 8, 9 (run of 2), then 2 breaks the run, then 7, 8, 9, 10 (run of 4). The longest run is 4.

(a) Max 4, one mark per gap:
- [A] current + 1 (allow current += 1, 1 + current) (1)
- [B] 0 (1)
- [C] best = current (1)
- [D] best (1)
Do not accept a gap that assigns to the wrong variable, e.g. current = best for [C]. Allow equivalent code in any recognised language.

(b) 4 (1)
Do not accept 2 or 6. Award this mark independently of the answers given in (a).

The queue is full when count equals the array size, 5 (A). Adding a job increases count by one (B). Removing a job moves front on by one, wrapping to 0 after index 4, so (front + 1) MOD 5 (C).

(b)(i) rear = (3 + 4) MOD 5 = 7 MOD 5 = 2.
(ii) Space at the start of the array that is freed by dequeue can be reused by wrapping round, so items do not need shifting and the queue does not report full while empty locations remain.

(a) Max 3, one mark per gap:
- [A] count == 5 (allow count >= 5, count == queue.length) (1)
- [B] count + 1 (allow count += 1) (1)
- [C] (front + 1) MOD 5 (1)
Do not accept front + 1 for [C] (no wrap-around).

(b)(i) 2 (1)
Do not accept 7.

(b)(ii) Max 1:
- Freed locations at the front can be reused / the array is used efficiently (1)
- Avoids shifting all items along after a dequeue (1)
- Avoids the queue appearing full when there are empty locations (1)
Do not accept 'it is faster' or 'it uses less memory' without development.

With 40 addresses there are around 40! possible orders, far too many to check in a reasonable time, even on a fast computer. A heuristic uses a rule of thumb, for example moving to the nearest unvisited address next. This produces an acceptable route in a short time, although it may not be the shortest possible route. For Harbourline, a reasonably short route available quickly is more useful than a perfect route that takes too long to calculate.

Max 3 from:
- Number of possible routes is very large / grows factorially or exponentially as addresses are added (1)
- ... so checking every route (exhaustive search) would take impractical / too much time (1)
- A heuristic uses a rule of thumb / approximation, e.g. nearest unvisited address next (1)
- ... which gives a good / acceptable route quickly (1)
- The route may not be optimal, but this is acceptable for delivery drivers (1)
- Must be applied to Harbourline, e.g. 40 addresses per round / routes needed before drivers start (1)

Allow: 'brute force' for exhaustive search.
DNA: 'faster' or 'easier' without reference to the number of routes or the time taken.
DNA: answers claiming a heuristic always finds the best route.

(a) hireA is called by value (the default). Parameter count is a local copy of 12; decrementing it does not change available, so line 11 prints 12. hireB uses byRef, so count refers to the same memory location as available. available becomes 11, so line 13 prints 11.
(b) In hireA the value 12 is copied into a local variable, which is discarded when the procedure ends. In hireB the address of available is passed, so count is an alias for it and the subtraction changes the original variable.

(a) Max 2
- 12 for line 11 (1)
- 11 for line 13 (1)
Allow follow through for line 13 only if line 11 is given as 12 or the candidate's reasoning is consistent with by value / by reference. Both values must be linked to the correct line.

(b) Max 3
- hireA passes the parameter by value // a copy of the value of available is passed (1)
- ...so changes to count affect only the local copy / the original variable is unchanged (1)
- hireB passes the parameter by reference // the address / memory location of available is passed (1)
- ...so count refers to the same variable and the change updates available (1)
Award a maximum of 3 marks.
Do not accept 'global' or 'local' variable as the sole explanation without reference to copying or addresses. Do not accept a description that does not distinguish the two procedures.

Dijkstra: all nodes start with distance infinity except the start node (0). Repeatedly select the unvisited node with the smallest known distance, update the distances of its neighbours if a shorter path is found via this node, and record the previous node. Stop when the destination is visited (or all nodes are visited). The route is rebuilt by following the previous-node links backwards. It always gives the quickest route when weights are non-negative (sailing times are), needs no extra information, and uses current weights each run. Its drawback is that it explores outwards in every direction, including ports in the wrong direction, so it may process many of the 400 ports. With a priority queue the cost is roughly O((V+E) log V), so for 400 ports and 1 200 edges this is only a few thousand operations, which is likely to be well inside one second even on a low-powered kiosk.

A*: works like Dijkstra but chooses the next node with the lowest f = g + h, where g is the known time from the start and h is the heuristic estimate to the destination. This directs the search towards the destination so fewer nodes are explored. Drawbacks: it needs port coordinates to be stored and a heuristic to be designed; if h overestimates the true time the route may not be the quickest. Straight-line distance divided by maximum speed never overestimates the time (ferries cannot go faster than maximum speed or shorter than a straight line), so it is admissible, and changing sailing times (delays, slower speeds) only make real times longer, so it remains admissible. It is more complex to implement and each node needs extra data (h and f), using slightly more memory. In the worst case, with a poor heuristic, it can behave like Dijkstra.

Conclusion: both are feasible on a small graph. A* is preferable as it reduces explored ports and response time while keeping the quickest route, because the heuristic is admissible. Dijkstra is simpler and could be chosen if simplicity and maintainability matter more, as the graph is small.

AO1 (knowledge), AO2 (application to the Harbourline scenario), AO3 (evaluation and judgement). Award the level from the overall quality of the response, then position the mark within the level. Indicative content is not exhaustive.

Level 3 (10-12 marks): Detailed and accurate description of how both algorithms find a route, including the role of distances/priority and, for A*, the heuristic. Benefits and drawbacks of both are clearly applied to the context (graph size, kiosk, changing times). A justified conclusion is reached that follows from the points made. Few or no errors; well structured.

Level 2 (5-9 marks): Reasonable description of how at least one algorithm works, with some description of the other. Some benefits and/or drawbacks are applied to the context, but may be one-sided or lack development. A conclusion is given but may be only partly justified.

Level 1 (1-4 marks): Limited or generic description of one or both algorithms, with little or no reference to the context. Benefits/drawbacks are stated, not developed. Conclusion absent or unsupported.

0 marks: No creditworthy response.

Indicative content (knowledge):
- Dijkstra: initial distances infinity/0 for start; choose unvisited node with smallest distance; update neighbours; record previous node; trace back to give the route
- A* similar but selects by f = g + h; h is an estimate of remaining cost to the destination
- Both use a priority queue/list of open nodes; both need non-negative weights
- Dijkstra and A* with an admissible heuristic both give the quickest route

Indicative content (application):
- 400 ports and 1 200 edges is a small graph so Dijkstra may be fast enough
- Dijkstra explores ports in all directions, including those away from the destination, wasting processing on a low-powered kiosk
- A* explores fewer nodes so is faster/uses less memory for the queue
- Straight-line distance / maximum speed is admissible, so A* remains optimal; delays only increase real times
- A* requires port coordinates to be stored and a heuristic to be designed; extra data per node
- Sailing times change several times a day, so the graph weights must be re-read for each search; neither algorithm needs pre-computed results (unlike caching all routes, which would become out of date)
- Heuristic is only a good guide if sailings are close to straight lines; if routes must go around land/islands, h is a poor estimate and A* gains less

Indicative content (evaluation):
- Judgement on which algorithm, weighing speed against complexity/maintainability
- Valid conclusions include A* (preferred, with justification) or Dijkstra (acceptable if justified by simplicity and the small graph)

Allow: Big O notation used correctly, e.g. O(n^2) for array-based Dijkstra or O((V+E) log V) with a priority queue.
Do not accept: statements that Dijkstra or A* sorts the graph, or that A* is always guaranteed to be faster in the worst case.
Do not accept: a conclusion that A* is optimal without any reference to the heuristic not overestimating.
If the response describes only one algorithm in detail, the maximum is Level 2.

On line 8, extra (3) is passed by value to bonus, so bonus is a copy. Line 2 changes the copy to 6, and the original extra stays 3. points (10) is passed by reference to score, so line 3 changes points to 10 + 6 = 16. Line 9 outputs 16 and line 10 outputs 3. The variable extra is unchanged because it was passed by value.

(a) Max 2
- 16 output first (1)
- 3 output second (1)
Allow follow through for the second mark only if the candidate has shown the outputs in the order points then extra. Do not accept 6 for the second value. Accept the two values on separate lines or separated by a comma.

(b) Max 1
- By value / pass by value / byVal (1)
Do not accept by reference.