Year 11 Paper 2: Programming and Data
Covers searching and sorting algorithms, algorithm design and trace tables, programming constructs, logic gates and boolean logic, binary and hexadecimal number systems, and representing text, images, sound and compression.
Year 11 follows a typical teaching order. No exam board defines what belongs to Year 11, and schools sequence the course differently. Check it against your own scheme of work before using it to decide what a class has covered.
Questions
Question 1 [3 marks]
Boolean Logic and Logic Gates
An OR gate has two inputs, A and B.
State the output of the OR gate for each of these input combinations: A=0,B=0 ; A=1,B=0 ; A=1,B=1.
Question 2 [3 marks]
Searching and Sorting Algorithms
A bubble sort compares each pair of adjacent items in a list, one pass at a time.
For an ascending bubble sort, describe what happens when two adjacent items are compared, covering both an out-of-order pair and a pair already in order.
Question 3 [4 marks]
Representing Text, Images, Sound and Compression
A programmer is choosing between ASCII and Unicode to represent text in an international app used in many countries.
State what Unicode is, and state why it is more suitable than ASCII for this app.
Question 4 [4 marks]
Programming Constructs
A program stores the names of five students in an array called names, indexed from 0 to 4.
State what is stored in names[0], and explain what would happen if the program tried to access names[5].
Question 5 [3 marks]
Number Systems: Binary and Hexadecimal
Two 4-bit binary values are combined using a bitwise AND: 1010 AND 1100.
Calculate the result of this bitwise AND, and state the general rule that a bitwise AND applies to each pair of corresponding bits.
Question 6 [4 marks]
Algorithm Design and Trace Tables
A programmer wants to validate that a user enters a number from 1 to 10 inclusive, re-asking until a valid number is entered. Their pseudocode is:
input number
while number < 1 or number > 10
print "Invalid, try again"
input number
endwhile
print "Valid number entered"
For the printed inputs, state why each is rejected or accepted, and list all messages printed in order.
Question 7 [4 marks]
Searching and Sorting Algorithms
The list [8, 3, 6, 1] is sorted into ascending order using a bubble sort.
Use ascending, left-to-right passes comparing adjacent pairs; each pass starts at the first item. State the complete list after each pass until it first becomes sorted. Also state which item reaches its final position during pass 1 and how it gets there. Do not include a final no-swap confirmation pass.
Question 8 [4 marks]
Boolean Logic and Logic Gates
A NAND gate has two inputs, C and D, and its output is the opposite of what an AND gate would give for the same inputs.
Write a Boolean expression for the NAND gate's output using C and D, and state its output when C=1 and D=1.
Question 9 [5 marks]
Programming Constructs
A program stores a student's exam mark as a percentage (a whole number from 0 to 100), and separately stores whether the student passed (true or false).
State and justify the most appropriate type for each value. Also state the valid mark range and explain whether choosing the mark type alone enforces that range.
Question 10 [5 marks]
Algorithm Design and Trace Tables
The following pseudocode is intended to swap the values stored in two variables, a and b, but contains a logic error.
a = b
b = a
Identify the error, explain why it does not correctly swap the values, and state a correction using a third variable.
Example initial values: a = 2 and b = 9.
Question 11 [6 marks]
Searching and Sorting Algorithms
A supermarket needs to search its list of 50000 product barcodes to find a product's price at the checkout. The list of barcodes is kept sorted, and a new search happens every time an item is scanned, hundreds of times a minute across many tills.
Discuss why binary search is well suited to these frequent lookups, comparing its worst-case checked-item comparisons with linear search. Explain the effect of losing sorted order, and name one other data structure that could support efficient exact barcode lookup.
Question 12 [5 marks]
Number Systems: Binary and Hexadecimal
A control system for a small robot stores sensor readings using 8-bit unsigned binary numbers. During testing, an 8-bit register holding 11111111 has 1 added to it.
Explain what happens when this addition is carried out, and discuss why an overflow error like this could be a serious problem in a real control system.
Question 13 [6 marks]
Searching and Sorting Algorithms
A programmer needs to sort a list that is almost fully sorted already, with only a few items out of place.
Assume an array, very few inversions and standard merge sort that divides to singletons without skipping merges. Compare insertion sort and merge sort, including time and extra storage, and recommend an algorithm with a justified limitation of your recommendation.
Question 14 [4 marks]
Number Systems: Binary and Hexadecimal
A student claims: 'Binary can only be used to represent positive whole numbers.'
Discuss whether this claim is accurate, referring to how negative numbers and non-integer values can be represented in binary.
Model solutions
| Question 1[3 marks] | |
|---|---|
| Answer or working | Marks |
| A=0, B=0 gives output 0. | B1 |
| A=1, B=0 gives output 1. | B1 |
| A=1, B=1 gives output 1. | B1 |
| Final answer: A=0,B=0: 0. A=1,B=0: 1. A=1,B=1: 1 (OR outputs 1 whenever at least one input is 1) | |
| Question 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| Compare the relative order of adjacent values | B1 |
| Swap if the left value is greater in ascending order | B1 |
| Leave an already ordered or equal pair unchanged | B1 |
| Final answer: For ascending order, compare adjacent values. If the left value is greater than the right value, swap them; otherwise leave them in place. Move to the next adjacent pair in the pass. | |
| Question 3[4 marks] | |
|---|---|
| Answer or working | Marks |
| Unicode is a standard assigning code points to characters. | B1 |
| Its repertoire includes many scripts, symbols and emoji. | B1 |
| These characters support users writing in their own languages in an international app. | B1 |
| ASCII has too small a repertoire for all these languages; no fixed Unicode byte width is required. | B1 |
| Final answer: Unicode assigns code points to a much wider repertoire of characters than ASCII, including many scripts and symbols. This supports international users; storage size depends on the encoding and character. | |
| Question 4[4 marks] | |
|---|---|
| Answer or working | Marks |
| names[0] holds the first name | B1 |
| Valid indices are 0 through 4 | B1 |
| names[5] lies outside the array | B1 |
| Bounds checking raises an error; exact behaviour depends on language | B1 |
| Final answer: names[0] holds the first student name, because the array is zero-indexed. Valid indices run from 0 to 4; names[5] refers beyond the fifth and last element. In a bounds-checked language that raises an out-of-range error; unguarded languages can instead have invalid or undefined access. | |
| Question 5[3 marks] | |
|---|---|
| Answer or working | Marks |
| Compares corresponding bit pairs using AND. | M1 |
| 1000; a correct result earns the method mark. | A1 |
| Each output bit is 1 exactly when both corresponding inputs are 1, otherwise 0. | B1 |
| Final answer: 1000; a bitwise AND gives 1 in a position only when both corresponding bits are 1, otherwise 0 | |
| Question 6[4 marks] | |
|---|---|
| Answer or working | Marks |
| 15 exceeds 10 and triggers the loop | B1 |
| 0 is below 1 and triggers the loop | B1 |
| 7 is within range and exits the loop | B1 |
| Two invalid messages then one valid message are printed | B1 |
| Final answer: Input 15 is rejected because it exceeds 10: print Invalid, try again. Input 0 is rejected because it is below 1: print Invalid, try again again. Input 7 is accepted because both out-of-range comparisons are false, so the loop exits and prints Valid number entered. | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| First full pass gives [3,6,1,8] | B1 |
| Second full pass gives [3,1,6,8] | B1 |
| Third full pass gives [1,3,6,8] | B1 |
| Pass 1 moves 8 to the final position by three adjacent swaps | B1 |
| Final answer: With left-to-right ascending passes: [3,6,1,8], [3,1,6,8], [1,3,6,8]. Pass 1 swaps 8 with 3, 6 and 1; pass 2 swaps 6 with 1; pass 3 swaps 3 with 1. | |
| Question 8[4 marks] | |
|---|---|
| Answer or working | Marks |
| Combines C and D with AND, or uses an equivalent De Morgan form. | M1 |
| Negates the whole conjunction: NOT (C AND D), accepting NOT C OR NOT D. | M1 |
| Evaluates C AND D as 1 for C=D=1, or correctly substitutes into an equivalent expression. | M1 |
| Gives output 0; full evaluation credit for the correct stated output. | A1 |
| Final answer: output = NOT (C AND D); with C=1, D=1 the output is 0 | |
| Question 9[5 marks] | |
|---|---|
| Answer or working | Marks |
| Choose integer for the mark | B1 |
| Whole-number percentages need no fractional representation | B1 |
| Choose Boolean for the pass flag | B1 |
| Boolean represents true or false | B1 |
| Range 0..100 requires validation beyond choosing integer | B1 |
| Final answer: Use an integer for the percentage, because it is a whole number with no fractional part. Validate its range as 0..100: the type alone need not enforce that range. Use a Boolean for passed, because it represents exactly true or false. | |
| Question 10[5 marks] | |
|---|---|
| Answer or working | Marks |
| First assignment loses the original a | B1 |
| Original code leaves both variables equal to original b | B1 |
| Save original a with temp = a | B1 |
| Assign original b to a using a = b | B1 |
| Assign saved original a to b using b = temp | B1 |
| Final answer: The first assignment overwrites the old a before it is saved. Then b = a copies the old b back, leaving both equal to the old b. Correct pseudocode: temp = a a = b b = temp For a=2,b=9, the corrected final values are a=9,b=2. For the printed a=2,b=9 test, the faulty code ends with a=9,b=9. | |
| Question 11[6 marks] | |
|---|---|
| Answer or working | Marks |
| Frequent barcode lookups need efficient repeated searches | B1 |
| Halving the interval yields at most 16 checked items | B1 |
| Linear search can require 50000 checks | B1 |
| Sorted order makes elimination correct | B1 |
| Unsorted data can cause false not-found results and needs sorting or a different search | B1 |
| Other indices such as hash tables can also provide efficient exact lookups | B1 |
| Final answer: Binary search is well suited to frequent lookups on the sorted barcodes: every unsuccessful comparison halves the interval, with at most 16 checks for 50000 items. Linear search may need 50000 checks, so repeated checkout lookups favour binary search. Correct comparisons require sorted order; an unsorted list can cause it to discard the interval containing the barcode and falsely report absence. Keep order on updates or sort first; linear search works without order but is slower for this workload. Binary search is not uniquely essential: a suitable hash index can also support quick exact lookups. | |
| Question 12[5 marks] | |
|---|---|
| Answer or working | Marks |
| 11111111 is the unsigned 8-bit maximum, 255. | B1 |
| Adding 1 produces 256, requiring the ninth bit in 100000000. | B1 |
| In an 8-bit wrapping register the carry is lost and the stored result is 00000000, causing overflow; allow explicit detected/trapped overflow. | B1 |
| Gives a plausible incorrect control decision caused by treating the wrapped zero as a genuine low reading. | B1 |
| Develops the practical consequence, e.g. a motor continues running when it should stop, risking damage or injury. | B1 |
| Final answer: The register overflows and wraps around from 255 to 0 instead of reaching 256; in a real control system this sudden, incorrect jump could cause dangerous or unpredictable behaviour unless the system is designed to handle or detect overflow | |
| Question 13[6 marks] | |
|---|---|
| Answer or working | Marks |
| Insertion sort moves each key into its sorted prefix | B1 |
| Few inversions mean few shifts and work near O(n) | B1 |
| Standard merge sort divides regardless of initial order | B1 |
| Standard merge sort takes O(n log n) even for sorted input | B1 |
| Insertion sort is in-place versus usual array merge auxiliary storage | B1 |
| Recommend insertion sort with a caveat about displacement and size | B1 |
| Final answer: Usually choose insertion sort for a nearly sorted list. It inserts each item into the sorted prefix and shifts only larger items. Work is O(n + I), where I is the number of inversions, and is close to linear when displacement is small. Standard merge sort still divides and merges through O(log n) levels with O(n) work per level, taking O(n log n). Insertion sort uses constant extra storage; merge sort usually needs an auxiliary array. If a few misplaced items are far away, or the list is very large, measure actual work rather than assuming near-linear performance. | |
| Question 14[4 marks] | |
|---|---|
| Answer or working | Marks |
| Explains a valid signed convention such as two's complement, sign-and-magnitude or a signed fixed-point format. | B1 |
| Gives a correct negative representation or explains the signed place values, e.g. leading weight -128 in 8-bit two's complement. | B1 |
| Describes a valid fractional representation, such as fixed point or floating point. | B1 |
| Develops that explanation with fractional binary place values, e.g. 0.1 base 2 = 0.5, or a valid significand/exponent account; these examples disprove the claim. | B1 |
| Final answer: The claim is false: signed binary conventions represent negatives, and fixed-point or floating-point binary can represent non-integers. For example, 11111111 is -1 in 8-bit two's complement and 0.1 base 2 is one half. | |