AS Paper 3: Algorithms and Structures
Covers linear data structures such as stacks, queues and linked lists, searching and sorting algorithms, writing and tracing short programs, data representation and computer architecture.
Questions
Question 1 [2 marks]
Data Representation
Convert the denary number 109 into an 8-bit unsigned binary number.
Question 2 [3 marks]
Searching and Sorting Algorithms
The list [8, 3, 6, 1] is sorted using a bubble sort. Each pass compares adjacent elements and swaps them if they are in the wrong order, working from the start of the list to the end.
State the contents of the list after one complete pass.
Question 3 [3 marks]
Programming: Trace, Write and Explain
The following pseudocode is executed:
product = 1
n = 4
WHILE n > 0
product = product * n
n = n - 1
ENDWHILE
OUTPUT product
Complete a trace of the values of product and n after each iteration of the loop, and state the value output.
Question 4 [3 marks]
Computer Architecture and the CPU
State the purpose of the Control Unit (CU) and the Arithmetic Logic Unit (ALU) within a CPU, and state which of the two directs the fetch-decode-execute cycle.
Question 5 [4 marks]
Linear Data Structures
A circular queue uses an array of fixed capacity, with front identifying the next item to remove and rear identifying the next position for insertion. The indices wrap modulo capacity; no separate count, empty flag or reserved unused slot is used.
Explain why the condition front = rear is ambiguous in this implementation, and explain how keeping a separate count variable resolves the ambiguity.
Question 6 [4 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called IsPalindrome that takes a string, s, as its parameter, and returns TRUE if s reads the same forwards and backwards, and FALSE otherwise. You may assume a function LEN(s) returns the length of s, and that individual characters of s can be accessed using s[i], indexed from 0.
Question 7 [4 marks]
Computer Architecture and the CPU
A CPU has a clock speed of 3.2 GHz (3,200,000,000 cycles per second). A particular instruction takes 4 clock cycles to complete.
Calculate the time, in nanoseconds, taken to execute this one instruction, and state one factor other than clock speed that affects how many instructions a CPU can complete per second.
Question 8 [4 marks]
Linear Data Structures
A queue is implemented using an array of fixed size, with a front index and a rear index. Dequeuing moves the front index forward but never reuses the array positions before it.
After several enqueue and dequeue operations, the rear index reaches the end of the array even though several positions at the start of the array are unused.
Explain the problem this causes, and explain how a circular buffer implementation solves it.
Question 9 [2 marks]
Computer Architecture and the CPU
A RISC (Reduced Instruction Set Computer) processor has a small set of simple instructions, each usually completing in one clock cycle. A CISC (Complex Instruction Set Computer) processor has a larger set of instructions, some of which are complex and take multiple clock cycles to complete.
State one advantage RISC has over CISC, and one advantage CISC has over RISC.
Question 10 [5 marks]
Linear Data Structures
A stack-based algorithm reverses a string by pushing every character onto a stack in order, then popping every character off and appending each one to the output as it is popped.
Trace this algorithm for the input string CODE, showing the stack contents once every character has been pushed, and state the final reversed output.
Question 11 [5 marks]
Linear Data Structures
A singly linked list stores each node as a value and a pointer to the next node. The list currently holds, in order, 6 -> 14 -> 21 -> 35, with a head pointer to the node holding 6.
Describe, as a sequence of steps, how the node holding 21 is removed so the list becomes 6 -> 14 -> 35. You do not need to write code.
Question 12 [5 marks]
Data Representation
A two's complement representation using n bits can represent integers from -(2^(n-1)) to (2^(n-1)) - 1.
State the range of values that can be represented using 10-bit two's complement, and explain why the range is not symmetrical (there is one more negative value than there are positive values).
Question 13 [4 marks]
Programming: Trace, Write and Explain
A student writes the following pseudocode, intended to output every element of a list, values, which has 6 elements (indices 0 to 5):
FOR i = 1 TO 6: OUTPUT values[i] ; NEXT i
Explain why this code either misses an element or causes an error, and rewrite the FOR line so the code works correctly for a list of any length.
Question 14 [4 marks]
Data Representation
ASCII uses 7 bits to represent 128 characters, covering the basic English alphabet, digits and some punctuation and control characters. Unicode aims to represent characters from every writing system in the world, and is commonly encoded using UTF-8, a variable-length encoding using 1 to 4 bytes per character.
Explain one limitation of ASCII that Unicode addresses, and explain why UTF-8 is described as backward compatible with ASCII.
Question 15 [5 marks]
Linear Data Structures
A doubly linked list stores each node as a value, a pointer to the next node and a pointer to the previous node. The list currently holds, in order, 4 <-> 9 <-> 15 <-> 22, with a head pointer to the node holding 4.
Describe, as a sequence of steps, how the node holding 15 is removed so the list becomes 4 <-> 9 <-> 22. You do not need to write code.
Question 16 [3 marks]
Programming: Trace, Write and Explain
A function is defined as: FUNCTION AddOne(n): n = n + 1, RETURN n, ENDFUNCTION
In the main program: x = 5, y = AddOne(x), OUTPUT x, OUTPUT y
State the values output for x and y, and explain, in terms of parameter passing, why x is not changed by the call to AddOne even though the function reassigns its parameter n.
Model solutions
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| a valid conversion method, such as 109 = 64 + 32 + 8 + 4 + 1, or repeated division by 2. | M1 |
| 01101101, including the leading zero. | A1 |
| Final answer: 01101101 | |
| Question 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| swapping 8 and 3 to give 3, 8, 6, 1 | M1 |
| swapping 8 and 6, then swapping 8 and 1, moving 8 towards the end | M1 |
| the list 3, 6, 1, 8 after one pass Award all 3 marks for the complete correct requested answer: After one pass: [3,6,1,8]. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: After one pass: [3,6,1,8]. | |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| post-iteration (product,n) pairs (4,3) and (12,2) | M1 |
| post-iteration pairs (24,1) and (24,0) | M1 |
| output 24 | A1 |
| Final answer: (product,n): (4,3), (12,2), (24,1), (24,0); output 24. | |
| Question 4[3 marks] | |
|---|---|
| Answer or working | Marks |
| the CU coordinating CPU operations, decoding instructions or issuing control signals. | B1 |
| the ALU performing arithmetic and logical operations. | B1 |
| identifying the CU as directing the fetch-decode-execute cycle. | B1 |
| Final answer: CU coordinates and directs fetch-decode-execute; ALU performs arithmetic and logic | |
| Question 5[4 marks] | |
|---|---|
| Answer or working | Marks |
| equal front and rear representing an empty queue under the printed next-insertion convention | B1 |
| also representing a full queue after a complete wrap. | B1 |
| count tracking the number of stored items | B1 |
| empty at count=0 and full at count=capacity. Accept equivalent correct explanations. | B1 |
| Final answer: With rear as the next insertion position, equal indices can mean empty or full after wrapping. A separate count tracks stored items: empty when count=0, full when count=capacity. | |
| Question 6[4 marks] | |
|---|---|
| Answer or working | Marks |
| IsPalindrome with parameter s | M1 |
| comparing mirrored characters, or an equivalent comparison with the reversed string | M1 |
| returning FALSE when any corresponding characters differ | A1 |
| returning TRUE when all corresponding characters match; accept equivalent algorithms without requiring early return or a midpoint bound | A1 |
| Final answer: FUNCTION IsPalindrome(s) left = 0 right = LEN(s) - 1 WHILE left < right IF s[left] != s[right] THEN RETURN FALSE ENDIF left = left + 1 right = right - 1 ENDWHILE RETURN TRUE ENDFUNCTION | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| one clock cycle taking 1 / 3200000000 seconds. | M1 |
| converting to nanoseconds, obtaining 0.3125 ns per cycle. | M1 |
| 4 * 0.3125 = 1.25 ns; accept calculating 4 / 3200000000 seconds then converting. | A1 |
| one valid other performance factor, such as cycles per instruction, cache behaviour or useful parallelism; no second factor is required. | B1 |
| Final answer: 1.25 ns; cycles per instruction also affect throughput | |
| Question 8[4 marks] | |
|---|---|
| Answer or working | Marks |
| explaining the queue now appears full and rejects further enqueue operations, since the rear index cannot move past the end of the array | B1 |
| explaining this happens even though the positions before the front index hold no live data and are effectively wasted space | B1 |
| explaining a circular buffer solves this by treating the array as circular, wrapping the rear index back to index 0 (using MOD the array size) once it passes the last index | B1 |
| explaining this allows the freed positions at the start of the array to be reused, rather than a queue overflowing while space is still available | B1 |
| Final answer: Wasted space at the front makes the queue seem full early; a circular buffer wraps the rear index back to 0 (via MOD) so freed space at the start is reused | |
| Question 9[2 marks] | |
|---|---|
| Answer or working | Marks |
| one valid RISC advantage, such as regular simple instructions being easier to pipeline; accept a suitably qualified implementation-dependent advantage. | B1 |
| one valid CISC advantage, such as a complex instruction doing work that needs several simpler instructions, potentially reducing instruction count or code size. | B1 |
| Final answer: RISC can pipeline simple regular instructions efficiently; CISC may express work in fewer instructions | |
| Question 10[5 marks] | |
|---|---|
| Answer or working | Marks |
| the stack after pushing being C,O,D,E from bottom to top (or the equivalent labelled reverse orientation). | M1 |
| E being popped first | A1 |
| the remaining pop order D,O,C. These may be inferred from the correct reversed output. | A1 |
| appending in pop order | A1 |
| final output EDOC. No additional explanation of LIFO is required. | A1 |
| Final answer: After pushing: [C,O,D,E], bottom to top. Popping gives E,D,O,C, so output EDOC. | |
| Question 11[5 marks] | |
|---|---|
| Answer or working | Marks |
| traversing from the head until the node holding 14 is reached, the node before 21 | B1 |
| reading the pointer stored in the node holding 21, which points to the node holding 35 | B1 |
| setting the pointer of the node holding 14 to point to the node holding 35, skipping over 21 | B1 |
| the node holding 21 now being unreachable and able to be discarded | B1 |
| confirming the list now correctly reads 6, 14, 35 Award all 5 marks for a complete correct answer to the requested task. Accept equivalent valid explanations and notation. Method details not explicitly requested may be inferred from the correct requested results. Locating the predecessor, bypassing the node and the resulting list are within the requested deletion sequence. Discarding may mean permitting garbage collection; explicit free is not required. | B1 |
| Final answer: Locate predecessor 14 and bypass 21 by setting 14.next to 21.next (35). The list is 6 -> 14 -> 35. Reclaim the removed node if the memory model requires it; garbage collection is also valid. | |
| Question 12[5 marks] | |
|---|---|
| Answer or working | Marks |
| substituting n = 10 to obtain -(2^9) and 2^9 - 1. | M1 |
| -512 to 511 inclusive. | A1 |
| 512 patterns with sign bit 0 and 512 with sign bit 1. | B1 |
| zero occupying one non-negative code, leaving only 511 positive values. | B1 |
| all 512 negative codes representing negative values, reaching -512 without reserving a second zero code. | B1 |
| Final answer: -512 to 511 inclusive | |
| Question 13[4 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that index 0 is omitted | B1 |
| explaining that index 6 is out of bounds | B1 |
| starting the corrected loop at index 0 | M1 |
| ending the corrected loop at LEN(values) - 1, or an equivalent length-dependent bound | A1 |
| Final answer: Index 0 is omitted and index 6 is outside 0..5. Replace the FOR line with FOR i = 0 TO LEN(values) - 1. | |
| Question 14[4 marks] | |
|---|---|
| Answer or working | Marks |
| ASCII having insufficient codes for many writing systems. | B1 |
| Unicode assigning code points to a much wider set of characters. | B1 |
| the ASCII code points 0 to 127 having identical single-byte values in UTF-8. | B1 |
| explaining the compatibility consequence: ASCII-only text is valid UTF-8 with unchanged characters. | B1 |
| Final answer: Unicode represents many more writing systems; ASCII codes retain identical one-byte UTF-8 values | |
| Question 15[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying 9 and 22 as the neighbours of 15. | M1 |
| setting 9.next to 22 | A1 |
| setting 22.previous to 9. | A1 |
| bypassing the removed node in both directions | B1 |
| a valid completed deletion sequence. Accept equivalent pointer descriptions and automatic memory reclamation. No comparison with singly linked lists is required. | B1 |
| Final answer: Set 9.next to 22 and 22.previous to 9, bypassing 15 in both directions. The list is 4 <-> 9 <-> 22. Reclaim 15 if required; equivalent valid descriptions need no explicit manual deallocation. | |
| Question 16[3 marks] | |
|---|---|
| Answer or working | Marks |
| x = 5 | A1 |
| y = 6 | A1 |
| explaining that n receives a copy of the value of x, so reassigning local n does not change x | B1 |
| Final answer: x = 5 and y = 6. The parameter receives a copy of the value of x; reassigning local n does not change x. | |