AS Paper 1: Data Representation and Logic
Covers data representation, boolean logic and logic gates, computer architecture, linear data structures such as stacks and queues, 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]
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 3 [2 marks]
Boolean Algebra and Logic Gates
A logic circuit implements the Boolean expression X = (NOT A) OR (B AND C).
Evaluate X when A = 1, B = 1 and C = 0, and state the general rule for when the OR operator gives an output of 1.
Question 4 [3 marks]
Computer Architecture and the CPU
An interrupt is a signal sent to the processor, often by a hardware device, indicating that it needs immediate attention.
State what the CPU does immediately after recognising an interrupt has occurred, and give one example of an event that might generate an interrupt.
Question 5 [3 marks]
Linear Data Structures
A stack is a linear data structure that follows Last In First Out (LIFO).
The following operations are performed on an empty stack: push(4), push(9), pop(), push(2), pop().
State the value returned by each pop() operation, in the order they occur.
Question 6 [4 marks]
Data Representation
Convert the denary number 200 into hexadecimal, and then into an 8-bit unsigned binary number.
Question 7 [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 8 [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 9 [4 marks]
Boolean Algebra and Logic Gates
A half adder is a circuit that adds two single binary digits, A and B, producing a SUM output and a CARRY output.
State the Boolean expression for SUM and for CARRY in terms of A and B, and identify which standard logic gate each expression corresponds to.
Question 10 [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 11 [4 marks]
Data Representation
Convert the 8-bit unsigned binary number 10110110 into hexadecimal, and then convert the same binary number into denary.
Question 12 [5 marks]
Linear Data Structures
A stack is implemented using an array of fixed capacity 3, with a top pointer that starts at -1 (meaning empty). isFull() returns true once top = 2.
The operations push(5), push(9), push(2) and push(7) are attempted in that order.
State which of these operations succeed, and explain what happens on the operation that fails.
Question 13 [5 marks]
Data Representation
Two positive 8-bit two's complement numbers, each representing 90, are added together: 01011010 + 01011010.
Show the result of the binary addition, convert it to denary as a two's complement number, and explain why this result shows that signed overflow has occurred.
Question 14 [2 marks]
Boolean Algebra and Logic Gates
Simplify the Boolean expression Y = (A OR B) AND (A OR (NOT B)), showing each law used.
Question 15 [3 marks]
Programming: Trace, Write and Explain
The following recursive function is defined:
FUNCTION Fib(n)
IF n <= 1 THEN
RETURN n
ELSE
RETURN Fib(n - 1) + Fib(n - 2)
ENDIF
ENDFUNCTION
Trace the calls made when Fib(5) is evaluated, and state the value returned.
Question 16 [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 17 [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.
Question 18 [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 = 0, B = 0, C = 1; A = 0, B = 1, C = 1; and A = 1, B = 1, C = 1. 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 19 [6 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called FindIndex that takes a list, items, and a target value, target, as parameters, and returns the index (counting from 0) of the first occurrence of target in items, or -1 if target does not appear in the list.
Explain why the function should return -1 rather than, for example, 0, when the target is not found.
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 |
| 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 3[2 marks] | |
|---|---|
| Answer or working | Marks |
| X = 0 | A1 |
| OR producing 1 when at least one input is 1, including both | B1 |
| Final answer: X = 0; OR gives 1 when at least one operand is 1 (including both). | |
| Question 4[3 marks] | |
|---|---|
| Answer or working | Marks |
| stating the CPU finishes its current instruction, then saves its current state (such as the contents of its registers) before responding | B1 |
| stating the CPU then jumps to run a specific interrupt service routine (ISR) associated with that interrupt | B1 |
| a valid example, such as a key being pressed on a keyboard, a mouse click, or a printer signalling it has run out of paper | B1 |
| Final answer: The CPU finishes its current instruction, saves its state, and jumps to run the interrupt service routine; an example trigger is a key press | |
| Question 5[3 marks] | |
|---|---|
| Answer or working | Marks |
| applying LIFO correctly; this may be inferred from the correct requested pop values and does not require an intermediate stack state. | M1 |
| the first pop returning 9. | A1 |
| the second pop returning 2. Award all 3 marks for 9, 2 in order alone. | A1 |
| Final answer: The pop values are 9, then 2. | |
| Question 6[4 marks] | |
|---|---|
| Answer or working | Marks |
| converting 200 to hexadecimal by finding 200 = 12 x 16 + 8 | M1 |
| hexadecimal C8 (12 = C, 8 = 8) | A1 |
| converting 200 to binary by summing place values 128 + 64 + 8 | M1 |
| 8-bit binary 11001000 Award equivalent credit for another valid complete conversion method; the particular listed route is not compulsory. | A1 |
| Final answer: Hexadecimal C8, binary 11001000 | |
| Question 7[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 8[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 9[4 marks] | |
|---|---|
| Answer or working | Marks |
| SUM = A XOR B or an equivalent expression | B1 |
| identifying the SUM gate as XOR | B1 |
| CARRY = A AND B or an equivalent expression | B1 |
| identifying the CARRY gate as AND | B1 |
| Final answer: SUM = A XOR B (XOR gate); CARRY = A AND B (AND gate). | |
| Question 10[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 11[4 marks] | |
|---|---|
| Answer or working | Marks |
| splitting the byte into two nibbles, 1011 and 0110 | M1 |
| hexadecimal B6 | A1 |
| summing the correct place values, 128 + 32 + 16 + 4 + 2 | M1 |
| denary 182 | A1 |
| Final answer: Hexadecimal B6; unsigned denary 182. | |
| Question 12[5 marks] | |
|---|---|
| Answer or working | Marks |
| push(5) succeeding, with top becoming 0 | M1 |
| push(9) succeeding, with top becoming 1 | M1 |
| push(2) succeeding, with top becoming 2, so isFull() is now true | A1 |
| push(7) failing, since isFull() is true when it is attempted | A1 |
| explaining this is a stack overflow, since the array has reached its fixed capacity and cannot store another value 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. The prompt requests successes and an explanation of failure. The top values are implied by the stated capacity convention; a separate top trace must not be mandatory. | B1 |
| Final answer: push(5), push(9), push(2) succeed. top is then 2, so isFull is true. push(7) fails with stack overflow and must leave the stack unchanged. | |
| Question 13[5 marks] | |
|---|---|
| Answer or working | Marks |
| correctly adding the two binary numbers to give 10110100 | M1 |
| recognising the leading bit of the result is 1, so it represents a negative two's complement value | M1 |
| converting 10110100 to denary: inverting to 01001011, adding 1 to give 01001100 (76), so the value is -76 | A1 |
| stating the mathematically correct result should be 90 + 90 = 180 | A1 |
| explaining signed overflow has occurred because adding two positive numbers has produced a result that reads as negative, which is impossible for a correct positive sum, since 180 cannot be represented in 8-bit two's complement (range -128 to 127) | B1 |
| Final answer: 10110100, which as two's complement is -76; since two positive numbers cannot correctly sum to a negative result, this shows signed overflow, because the true sum 180 is outside the 8-bit two's complement range of -128 to 127 | |
| Question 14[2 marks] | |
|---|---|
| Answer or working | Marks |
| showing valid laws for a complete simplification, such as distributivity, complementarity and identity; accept any valid derivation | M1 |
| Y = A | A1 |
| Final answer: Y = A. Dual distributivity gives A OR (B AND NOT B). Complementarity gives B AND NOT B = 0. Identity gives A OR 0 = A. | |
| Question 15[3 marks] | |
|---|---|
| Answer or working | Marks |
| tracing the full Fib(4) branch called by Fib(5): calls 4,3,2,1,0,1,2,1,0 in left-first order, or the equivalent subtree | M1 |
| tracing the full Fib(3) branch called by Fib(5): calls 3,2,1,0,1 in left-first order, or the equivalent subtree; accept either operand evaluation order | M1 |
| the returned value 5; intermediate return values and naming the sequence are not required | A1 |
| Final answer: Fib(5) returns 5. Calls in left-first order: 5, 4, 3, 2, 1, 0, 1, 2, 1, 0, 3, 2, 1, 0, 1. | |
| Question 16[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 17[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. | |
| Question 18[2 marks] | |
|---|---|
| Answer or working | Marks |
| the unsimplified sum of products (NOT A AND NOT B AND C) OR (NOT A AND B AND C) OR (A AND B AND C), accepting reordered terms | M1 |
| C AND (NOT A OR B), or an equivalent minimal expression; no separate derivation is requested | A1 |
| Final answer: Z = ((NOT A) AND (NOT B) AND C) OR ((NOT A) AND B AND C) OR (A AND B AND C) = C AND ((NOT A) OR B). | |
| Question 19[6 marks] | |
|---|---|
| Answer or working | Marks |
| FindIndex with items and target parameters | M1 |
| examining items within valid zero-based bounds, or an equivalent lookup; ascending traversal is one valid method, not a requirement | M1 |
| testing equality with target | M1 |
| returning the first matching index | A1 |
| returning -1 only if there was no match | A1 |
| explaining -1 distinguishes not-found from the valid index 0; accept other correct implementations | B1 |
| Final answer: FUNCTION FindIndex(items, target) FOR i = 0 TO LEN(items) - 1 IF items[i] = target THEN RETURN i ENDIF NEXT i RETURN -1 ENDFUNCTION -1 is outside the valid indices; 0 is a valid first-element index. | |