Revision Library
Choose a subject
Menu
Computer Science
Need a new topic?
Missing a topic, found a bug, or want something added?

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.

16 questions - 60 marks

Download PDF

Open A Level Computer Science workspace

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

Mark scheme for Question 1 [2 marks]
Question 1[2 marks]
Answer or workingMarks
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
Mark scheme for Question 2 [3 marks]
Question 2[3 marks]
Answer or workingMarks
swapping 8 and 3 to give 3, 8, 6, 1M1
swapping 8 and 6, then swapping 8 and 1, moving 8 towards the endM1
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].
Mark scheme for Question 3 [3 marks]
Question 3[3 marks]
Answer or workingMarks
post-iteration (product,n) pairs (4,3) and (12,2)M1
post-iteration pairs (24,1) and (24,0)M1
output 24A1
Final answer: (product,n): (4,3), (12,2), (24,1), (24,0); output 24.
Mark scheme for Question 4 [3 marks]
Question 4[3 marks]
Answer or workingMarks
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
Mark scheme for Question 5 [4 marks]
Question 5[4 marks]
Answer or workingMarks
equal front and rear representing an empty queue under the printed next-insertion conventionB1
also representing a full queue after a complete wrap.B1
count tracking the number of stored itemsB1
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.
Mark scheme for Question 6 [4 marks]
Question 6[4 marks]
Answer or workingMarks
IsPalindrome with parameter sM1
comparing mirrored characters, or an equivalent comparison with the reversed stringM1
returning FALSE when any corresponding characters differA1
returning TRUE when all corresponding characters match; accept equivalent algorithms without requiring early return or a midpoint boundA1
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
Mark scheme for Question 7 [4 marks]
Question 7[4 marks]
Answer or workingMarks
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
Mark scheme for Question 8 [4 marks]
Question 8[4 marks]
Answer or workingMarks
explaining the queue now appears full and rejects further enqueue operations, since the rear index cannot move past the end of the arrayB1
explaining this happens even though the positions before the front index hold no live data and are effectively wasted spaceB1
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 indexB1
explaining this allows the freed positions at the start of the array to be reused, rather than a queue overflowing while space is still availableB1
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
Mark scheme for Question 9 [2 marks]
Question 9[2 marks]
Answer or workingMarks
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
Mark scheme for Question 10 [5 marks]
Question 10[5 marks]
Answer or workingMarks
the stack after pushing being C,O,D,E from bottom to top (or the equivalent labelled reverse orientation).M1
E being popped firstA1
the remaining pop order D,O,C. These may be inferred from the correct reversed output.A1
appending in pop orderA1
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.
Mark scheme for Question 11 [5 marks]
Question 11[5 marks]
Answer or workingMarks
traversing from the head until the node holding 14 is reached, the node before 21B1
reading the pointer stored in the node holding 21, which points to the node holding 35B1
setting the pointer of the node holding 14 to point to the node holding 35, skipping over 21B1
the node holding 21 now being unreachable and able to be discardedB1
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.
Mark scheme for Question 12 [5 marks]
Question 12[5 marks]
Answer or workingMarks
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
Mark scheme for Question 13 [4 marks]
Question 13[4 marks]
Answer or workingMarks
explaining that index 0 is omittedB1
explaining that index 6 is out of boundsB1
starting the corrected loop at index 0M1
ending the corrected loop at LEN(values) - 1, or an equivalent length-dependent boundA1
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.
Mark scheme for Question 14 [4 marks]
Question 14[4 marks]
Answer or workingMarks
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
Mark scheme for Question 15 [5 marks]
Question 15[5 marks]
Answer or workingMarks
identifying 9 and 22 as the neighbours of 15.M1
setting 9.next to 22A1
setting 22.previous to 9.A1
bypassing the removed node in both directionsB1
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.
Mark scheme for Question 16 [3 marks]
Question 16[3 marks]
Answer or workingMarks
x = 5A1
y = 6A1
explaining that n receives a copy of the value of x, so reassigning local n does not change xB1
Final answer: x = 5 and y = 6. The parameter receives a copy of the value of x; reassigning local n does not change x.

Build a free practice pack.

Pick the topics, add the student's name and print one PDF.