AS Paper 5: Mixed Practice B
A second mixed paper covering boolean logic and logic gates, computer architecture, networks, linear data structures, searching and sorting algorithms and writing and tracing short programs.
Questions
Question 1 [1 mark]
Boolean Algebra and Logic Gates
A logic circuit implements the Boolean expression X = (A AND B) OR (NOT C).
Evaluate X when A = 1, B = 0 and C = 0.
Question 2 [3 marks]
Searching and Sorting Algorithms
A linear search checks each element of a list in turn, starting from index 0, until the target is found or the list is exhausted.
State the best-case number of comparisons for a linear search on a list of n elements, describe the circumstance in which this best case occurs, and state the best-case time complexity in Big O notation.
Question 3 [2 marks]
Networks and Communication
State what is meant by a network protocol, and give one example of a network protocol.
Question 4 [2 marks]
Boolean Algebra and Logic Gates
State the output of the logic expression A OR B for each of the four possible combinations of A and B (each 0 or 1).
Question 5 [3 marks]
Linear Data Structures
A stack supports push(), pop(), peek() (which returns the top value without removing it) and isEmpty().
The following operations are performed on an empty stack: push(6), push(2), peek(), pop(), isEmpty().
State the value returned by peek(), the value returned by pop(), and the value returned by isEmpty().
Question 6 [2 marks]
Boolean Algebra and Logic Gates
A logic circuit implements the Boolean expression Z = (A AND B) OR (B AND C) OR (A AND C), sometimes called a majority function.
Evaluate Z when A = 1, B = 1 and C = 0, and state, in words, what condition on A, B and C makes Z equal to 1.
Question 7 [3 marks]
Computer Architecture and the CPU
A CPU is connected to memory using three buses: the address bus, the data bus and the control bus.
State the purpose of each of these three buses.
Question 8 [4 marks]
Programming: Trace, Write and Explain
The following pseudocode is executed on the list values = [-3, 8, -1, 5, -9, 2]:
count = 0
FOR EACH v IN values
IF v < 0 THEN
count = count + 1
ENDIF
NEXT v
OUTPUT count
Complete a trace showing which values cause count to increase, and state the value output.
Question 9 [1 mark]
Computer Architecture and the CPU
A computer's memory hierarchy includes CPU registers, cache memory and main memory (RAM), typically in that order from fastest to slowest.
State one reason a computer does not simply use registers for all of its memory, given how much faster they are than main memory.
Question 10 [3 marks]
Programming: Trace, Write and Explain
A student writes the following pseudocode, intended to check whether a list of numbers, values, with n elements (indexed 0 to n - 1) is sorted in ascending order:
isSorted = TRUE
FOR i = 0 TO n - 3
IF values[i] > values[i + 1] THEN
isSorted = FALSE
ENDIF
NEXT i
OUTPUT isSorted
Explain why this code gives the wrong answer for the list [1, 2, 5, 3], and rewrite the FOR line so the code correctly checks every adjacent pair in a list of any length.
Question 11 [3 marks]
Boolean Algebra and Logic Gates
Use De Morgan's laws to write an equivalent expression for NOT (A OR B), using only AND, NOT and the individual variables A and B, then confirm your answer is correct by evaluating both expressions when A = 0 and B = 1.
Question 12 [3 marks]
Networks and Communication
In the client-server model, a web browser (the client) requests a web page from a web server.
Describe the roles of the client and the server in this exchange, and state one advantage of the client-server model over a peer-to-peer model for a busy website.
Question 13 [3 marks]
Programming: Trace, Write and Explain
A student writes the following pseudocode, intended to output the numbers 1 to 5:
i = 1
j = 1
WHILE i <= 5
OUTPUT i
j = j + 1
ENDWHILE
Explain why this code never terminates, and rewrite the loop body so it correctly outputs 1 to 5 and then stops.
Question 14 [4 marks]
Networks and Communication
An IPv4 address is 192.168.1.130 and its subnet mask is 255.255.255.192.
State the number of bits used for the network portion of the address under this subnet mask, and explain how a subnet mask is used to determine whether two IP addresses are on the same subnet.
Question 15 [4 marks]
Computer Architecture and the CPU
A program consists of 5,000,000 instructions. On a particular processor, each instruction takes an average of 3 clock cycles to complete, and the processor runs at a clock speed of 2.5 GHz (2,500,000,000 cycles per second).
Calculate the total number of clock cycles needed to run the program, and hence the total execution time in seconds.
Question 16 [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 17 [4 marks]
Searching and Sorting Algorithms
The list [5, 2, 9, 1, 6] is sorted using insertion sort, which builds a sorted section at the start of the list by inserting each new element into its correct position.
State the contents of the whole list after the first three elements (5, 2, 9) have been inserted into the sorted section, but before 1 is considered.
Question 18 [5 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called CountOccurrences that takes a list of values, items, and a target value, target, as parameters, and returns the number of times target appears in items.
Question 19 [5 marks]
Searching and Sorting Algorithms
Quicksort partitions a list around a pivot value: elements smaller than the pivot are moved before it, and elements larger are moved after it.
The list [8, 3, 12, 5, 9, 2] is partitioned using the last element, 2, as the pivot. The elements in each sublist keep their original relative order.
State the two sublists formed either side of the pivot after partitioning, and the pivot's final index (counting from 0).
Question 20 [3 marks]
Boolean Algebra and Logic Gates
Use De Morgan's laws to write an equivalent expression for NOT (A AND B AND C), using only OR, NOT and the individual variables, then confirm your answer is correct by evaluating both expressions when A = 1, B = 1 and C = 0.
Question 21 [5 marks]
Searching and Sorting Algorithms
Quicksort partitions a list around a pivot value: elements smaller than the pivot are moved before it, and elements larger are moved after it.
The list [10, 4, 15, 2, 8, 12] is partitioned using the lower of the two middle elements (index 2), 15, as the pivot. The elements in each sublist keep their original relative order.
State the two sublists formed either side of the pivot after partitioning, and the pivot's final index (counting from 0).
Question 22 [2 marks]
Boolean Algebra and Logic Gates
A logic circuit has inputs A, B and C, and its output Z is 1 for exactly these combinations: A = 1, B = 0, C = 0 and A = 1, B = 0, C = 1, and Z is 0 for every other combination.
Write the Boolean expression for Z as a sum of products (before simplification), then simplify it to its shortest form.
Question 23 [5 marks]
Computer Architecture and the CPU
A processor can find out that a device needs attention either by polling (repeatedly checking the device's status at regular intervals) or by using interrupts (the device signals the processor only when it actually needs attention).
Explain one disadvantage of polling compared with interrupts, and explain why a processor needs to save its current state before running an interrupt service routine (ISR).
Question 24 [6 marks]
Searching and Sorting Algorithms
Quicksort partitions a list around a pivot, then recursively sorts the sublist before the pivot and the sublist after the pivot.
The list [7, 3, 9, 1, 5] is partitioned using the last element, 5, as the pivot, giving the sublist [3, 1] before the pivot and [7, 9] after it, with 5 at index 2.
State the two recursive calls made next, and explain why quicksort's worst-case time complexity is O(n^2) even though its average case is O(n log n).
Model solutions
| Question 1[1 mark] | |
|---|---|
| Answer or working | Marks |
| X = 1; correct output alone earns full credit | A1 |
| Final answer: X = 1. | |
| Question 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| stating the best case is 1 comparison | B1 |
| describing this occurring when the target is the first element checked, at index 0 | B1 |
| stating the best-case time complexity is O(1) | B1 |
| Final answer: Best case: 1 comparison, when the target is at index 0; best-case complexity O(1) | |
| Question 3[2 marks] | |
|---|---|
| Answer or working | Marks |
| a definition such as: a set of rules that govern how devices communicate and exchange data over a network | B1 |
| a valid example, such as TCP, IP, HTTP, HTTPS or FTP | B1 |
| Final answer: A set of rules governing how devices communicate, e.g. HTTP | |
| Question 4[2 marks] | |
|---|---|
| Answer or working | Marks |
| the labelled rows 00 -> 0 and 01 -> 1 | B1 |
| the labelled rows 10 -> 1 and 11 -> 1 | B1 |
| Final answer: 00 -> 0; 01 -> 1; 10 -> 1; 11 -> 1. | |
| Question 5[3 marks] | |
|---|---|
| Answer or working | Marks |
| peek() returning 2. | A1 |
| pop() returning 2. | A1 |
| isEmpty() returning false. | A1 |
| Final answer: peek returns 2; pop returns 2; isEmpty returns false because 6 remains. | |
| Question 6[2 marks] | |
|---|---|
| Answer or working | Marks |
| Z = 1 | A1 |
| the condition that at least two of A, B and C are 1 | B1 |
| Final answer: Z = 1; Z is 1 exactly when at least two inputs are 1. | |
| Question 7[3 marks] | |
|---|---|
| Answer or working | Marks |
| the address bus - carries the memory address the CPU wants to read from or write to | B1 |
| the data bus - carries the actual data being transferred between the CPU and memory (or another device) | B1 |
| the control bus - carries control signals, such as read/write signals, that coordinate and synchronise the transfer | B1 |
| Final answer: Address bus: carries the memory address; data bus: carries the data itself; control bus: carries signals that coordinate the transfer | |
| Question 8[4 marks] | |
|---|---|
| Answer or working | Marks |
| showing that -3 causes count to increase | M1 |
| showing that -1 causes count to increase | M1 |
| showing that -9 causes count to increase, with no other value identified as causing an increase | M1 |
| output 3 | A1 |
| Final answer: Count increases at -3, -1 and -9; counts after each item: 1,1,2,2,3,3; output 3. | |
| Question 9[1 mark] | |
|---|---|
| Answer or working | Marks |
| stating one valid reason, such as registers being more expensive per byte than RAM or requiring more chip area per byte; either statement alone earns full credit. | B1 |
| Final answer: Registers are much more expensive per byte than RAM. | |
| Question 10[3 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that the loop omits the final adjacent pair at indices 2 and 3 | B1 |
| explaining that the missed pair 5,3 is out of order, so the original output incorrectly stays TRUE | B1 |
| FOR i = 0 TO n - 2, or an equivalent bound covering every adjacent pair | A1 |
| Final answer: The bound n - 3 omits the final pair (5,3), so isSorted incorrectly stays TRUE. Replace with FOR i = 0 TO n - 2. | |
| Question 11[3 marks] | |
|---|---|
| Answer or working | Marks |
| (NOT A) AND (NOT B), or an equivalent De Morgan expression using only AND and NOT | A1 |
| the original expression evaluating to 0 at A = 0, B = 1 | B1 |
| the equivalent expression evaluating to 0 at A = 0, B = 1 | B1 |
| Final answer: (NOT A) AND (NOT B); both sides are 0 at A = 0, B = 1. | |
| Question 12[3 marks] | |
|---|---|
| Answer or working | Marks |
| describing the client's role, such as sending a request for a resource, for example an HTTP request for a page | B1 |
| describing the server's role, such as receiving the request, processing it and returning the requested resource | B1 |
| a valid advantage, such as centralised control and management of data and security, or resources being easier to back up when kept in one place | B1 |
| Final answer: The client requests a resource; the server processes the request and returns it. Client-server gives centralised control of data and security | |
| Question 13[3 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that only j changes, so i stays 1 and the guard i <= 5 never becomes false | B1 |
| retaining OUTPUT i in the repaired loop body | M1 |
| incrementing i by 1 after output, producing 1 to 5 and then stopping; removing j is optional | A1 |
| Final answer: i remains 1 because only j changes, so i <= 5 is always true and 1 is output repeatedly. Replace the loop body with OUTPUT i followed by i = i + 1. | |
| Question 14[4 marks] | |
|---|---|
| Answer or working | Marks |
| converting the last octet, 192, to binary: 11000000 | M1 |
| 26 network bits in total (8 + 8 + 8 + 2) | A1 |
| explaining a bitwise AND is performed between an IP address and the subnet mask to find its network address | B1 |
| stating two addresses are on the same subnet if this calculation gives the same network address for both | B1 |
| Final answer: 26 network bits; two addresses are on the same subnet if ANDing each with the subnet mask gives the same network address | |
| Question 15[4 marks] | |
|---|---|
| Answer or working | Marks |
| calculating instructions * cycles per instruction: 5000000 * 3. | M1 |
| 15000000 cycles. | A1 |
| dividing total cycles by 2500000000 cycles/s. | M1 |
| 0.006 seconds; accept 6 milliseconds. | A1 |
| Final answer: 15000000 cycles; 0.006 s = 6 ms | |
| Question 16[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 17[4 marks] | |
|---|---|
| Answer or working | Marks |
| 2 being shifted before 5 to give the sorted section 2, 5 | M1 |
| 9 remaining after 5, since it is already larger, giving the sorted section 2, 5, 9 | M1 |
| the unsorted elements 1 and 6 remaining unchanged in their original positions | A1 |
| the complete list 2, 5, 9, 1, 6 Award all 4 marks for the complete correct requested answer: [2,5,9,1,6]. 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: [2,5,9,1,6]. | |
| Question 18[5 marks] | |
|---|---|
| Answer or working | Marks |
| CountOccurrences with items and target parameters | M1 |
| initialising a zero counter | M1 |
| inspecting every element for equality with target | M1 |
| counting each matching occurrence without stopping early | M1 |
| returning the count; equivalent valid algorithms receive credit | A1 |
| Final answer: FUNCTION CountOccurrences(items, target) count = 0 FOR EACH v IN items IF v = target THEN count = count + 1 ENDIF NEXT v RETURN count ENDFUNCTION | |
| Question 19[5 marks] | |
|---|---|
| Answer or working | Marks |
| recognising every other element, 8, 3, 12, 5 and 9, is greater than the pivot value 2 | M1 |
| concluding no elements belong before the pivot | M1 |
| the pivot moving to index 0 | A1 |
| the sublist after the pivot containing 8, 3, 12, 5, 9 | A1 |
| the sublist before the pivot being empty Award all 5 marks for the complete correct requested answer: Before pivot: []; after pivot: [8,3,12,5,9]. Pivot 2 finishes at index 0. 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. | B1 |
| Final answer: Before pivot: []; after pivot: [8,3,12,5,9]. Pivot 2 finishes at index 0. | |
| Question 20[3 marks] | |
|---|---|
| Answer or working | Marks |
| (NOT A) OR (NOT B) OR (NOT C), or an equivalent De Morgan expression using only OR and NOT | A1 |
| the original expression evaluating to 1 at A = 1, B = 1, C = 0 | B1 |
| the equivalent expression evaluating to 1 at A = 1, B = 1, C = 0 | B1 |
| Final answer: (NOT A) OR (NOT B) OR (NOT C); both sides are 1 at (1,1,0). | |
| Question 21[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying the middle element (index 2), value 15, as the pivot | M1 |
| comparing each remaining element, 10, 4, 2, 8, 12, against the pivot value 15 | M1 |
| recognising every one of these elements is smaller than 15 | A1 |
| concluding no elements belong after the pivot, so the pivot moves to the last index, index 5 | A1 |
| the sublist before the pivot containing all five remaining elements, 10, 4, 2, 8, 12, in their original relative order Award all 5 marks for the complete correct requested answer: Using the explicitly named pivot 15: before pivot [10,4,2,8,12]; after pivot []; final index 5. The list has two middle positions, so the wording should identify index 2 (the lower middle). 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. | B1 |
| Final answer: Before pivot: [10,4,2,8,12]; pivot 15 at index 5; after pivot: []. | |
| Question 22[2 marks] | |
|---|---|
| Answer or working | Marks |
| the unsimplified sum of products (A AND NOT B AND NOT C) OR (A AND NOT B AND C), accepting reordered terms | M1 |
| the shortest expression A AND NOT B; no separate derivation is requested | A1 |
| Final answer: Z = (A AND (NOT B) AND (NOT C)) OR (A AND (NOT B) AND C) = A AND (NOT B). | |
| Question 23[5 marks] | |
|---|---|
| Answer or working | Marks |
| one valid disadvantage of polling compared with interrupts, such as wasted CPU time or delayed response to a device. | B1 |
| a linked explanation: repeated checks consume time even when no service is needed, or a newly ready device must wait until the next poll; either route earns both disadvantage marks. | B1 |
| preserving a return address or program counter before running the ISR. | B1 |
| preserving working register values that the ISR might overwrite. | B1 |
| explaining restoration allows the interrupted computation to resume correctly; accept an equivalent explanation of sufficient saved context. | B1 |
| Final answer: Polling spends CPU time checking inactive devices; saved state permits correct resumption | |
| Question 24[6 marks] | |
|---|---|
| Answer or working | Marks |
| identifying the first recursive call as sorting the sublist before the pivot, [3, 1] | M1 |
| identifying the second recursive call as sorting the sublist after the pivot, [7, 9] | A1 |
| explaining the average case splits the list into two roughly equal halves each time, giving O(log n) levels of recursion with O(n) work partitioning at each level, hence O(n log n) | B1 |
| explaining the worst case occurs when a pivot is chosen that is the smallest or largest remaining value each time, for example on an already-sorted list with a fixed choice of pivot | B1 |
| explaining this gives sublists of size (n-1) and 0 at every level, meaning n levels of recursion instead of log n | B1 |
| concluding n levels each doing O(n) work partitioning gives O(n^2) overall in the worst case | B1 |
| Final answer: Recursive calls sort [3, 1] and [7, 9]; the worst case is O(n^2) because a poor pivot choice (e.g. smallest/largest each time) gives n levels of recursion instead of log n, each doing O(n) work | |