GCSE Computer Science Short Paper B
Covers Searching and Sorting Algorithms, Algorithm Design and Trace Tables, Programming Constructs and 3 more.
Questions
Question 1 [1 mark]
Representing Text, Images, Sound and Compression
A text file uses ASCII, where each character is stored using 1 byte.
State the file size, in bytes, of a text file containing exactly 250 characters (ignore any file header).
Question 2 [2 marks]
Programming Constructs
A program stores a person's height in metres as a decimal value, for example 1.75.
State the most appropriate data type for this variable, and state one other example of data that would use this data type.
Question 3 [3 marks]
Searching and Sorting Algorithms
The sorted list [5, 12, 18, 24, 31, 40, 47] is searched using a binary search for the value 31.
State the values checked, in the order they are checked, until the value 31 is found.
Question 4 [4 marks]
Boolean Logic and Logic Gates
A teacher explains four basic logic gates: AND, OR, NOT and XOR.
For each gate, state a valid usual number of inputs: one, two, or 'two or more'. Where more than one option is valid, give any valid option.
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 [3 marks]
Boolean Logic and Logic Gates
The Boolean expression NOT (NOT A AND NOT B) is to be simplified.
Simplify this expression using a Boolean identity, and name the identity used.
Question 7 [4 marks]
Algorithm Design and Trace Tables
The following pseudocode is intended to print the multiplication table for 5, from 5 * 1 to 5 * 5, but contains a logic error.
for i = 0 to 5
print 5 * i
next i
Identify the error, explain its effect on the output, and state the correction needed.
Question 8 [5 marks]
Searching and Sorting Algorithms
The list [7, 2, 9, 4] is sorted into ascending order using an insertion sort.
Starting with the first item as the sorted prefix, state the complete list after inserting each remaining item. Then explain which items shift during the final insertion and where the final key is placed.
Question 9 [4 marks]
Number Systems: Binary and Hexadecimal
A single parity bit is added to each 7-bit binary code sent between two computers, set so that the total number of 1 bits, including the parity bit, is always even.
The 7-bit code 1011001 is sent. State the value the parity bit should be set to, and explain how the receiving computer could use the parity bit to detect a single-bit transmission error.
Question 10 [5 marks]
Searching and Sorting Algorithms
A programmer needs to sort a list of 1 million customer records by surname, and this sort needs to be repeated regularly as new customers are added.
Compare a bubble sort with a merge sort for this task, and recommend which the programmer should use, justifying your answer.
Question 11 [6 marks]
Algorithm Design and Trace Tables
Design an algorithm, in pseudocode, that repeatedly asks the user to enter a number, stopping when the user enters -1, and then outputs the smallest number entered (not counting the -1).
Model solutions
| Question 1[1 mark] | |
|---|---|
| Answer or working | Marks |
| 250 bytes (250 characters * 1 byte per character), with no header included. | B1 |
| Final answer: 250 bytes | |
| Question 2[2 marks] | |
|---|---|
| Answer or working | Marks |
| real (float) is the most appropriate data type, since the value needs decimal places | B1 |
| valid other example, for example a temperature reading, an average, or a price with pence | B1 |
| Final answer: Real/float; another example could be a temperature or an average, which also need decimal places | |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| the first value checked is 24 (the middle item) | B1 |
| the second value checked is 40 | B1 |
| the third value checked is 31, which is found | B1 |
| Final answer: 24, then 40, then 31 (found) | |
| Question 4[4 marks] | |
|---|---|
| Answer or working | Marks |
| AND: two, or two or more. | B1 |
| OR: two, or two or more. | B1 |
| NOT: one. | B1 |
| XOR: two; also accept two or more for a multi-input parity XOR gate. | B1 |
| Final answer: AND: two or two or more. OR: two or two or more. NOT: one. XOR: two, with multi-input XOR also valid. | |
| 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[3 marks] | |
|---|---|
| Answer or working | Marks |
| Uses De Morgan to obtain NOT (NOT A) OR NOT (NOT B), or an equivalent valid simplification route. | M1 |
| Obtains A OR B, accepting equivalent notation; award the method mark for a correct simplified answer. | A1 |
| Names De Morgan's law or theorem. | B1 |
| Final answer: A OR B (De Morgan's law) | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| identifies the error is in the loop range, "for i = 0 to 5" | B1 |
| explains that this makes the loop run with i taking the values 0, 1, 2, 3, 4 and 5, six times instead of five | B1 |
| as a result, the output starts with an extra, unwanted line, 5 * 0 = 0, before the correct table values | B1 |
| states the correction: change the line to "for i = 1 to 5", so the loop runs exactly five times starting from 5 * 1 | B1 |
| Final answer: The loop should be 'for i = 1 to 5'; as written it also prints 5 * 0, an extra unwanted line before the table starts | |
| Question 8[5 marks] | |
|---|---|
| Answer or working | Marks |
| After inserting 2: [2,7,9,4] | B1 |
| After inserting 9: [2,7,9,4] | B1 |
| After inserting 4: [2,4,7,9] | B1 |
| Final insertion shifts 9 and 7 right | B1 |
| Place 4 after 2 in the sorted prefix | B1 |
| Final answer: The sorted prefix starts with 7. Insert 2: [2,7,9,4]. Insert 9: [2,7,9,4]. Insert 4: [2,4,7,9]. The final insertion shifts 9 and 7 right before placing 4 after 2. | |
| Question 9[4 marks] | |
|---|---|
| Answer or working | Marks |
| Counts four 1 bits in 1011001. | M1 |
| Parity bit 0; the correct parity answer earns the counting mark. | A1 |
| Receiver counts the 1 bits in the whole received code including the parity bit. | B1 |
| A single flipped bit changes even parity to odd, so an odd total signals an error; does not locate or correct it. | B1 |
| Final answer: Parity bit = 0 (the code already has four 1 bits, an even number); the receiver recounts the 1 bits including the parity bit, and an odd total reveals a single-bit error | |
| Question 10[5 marks] | |
|---|---|
| Answer or working | Marks |
| a bubble sort compares and swaps adjacent items repeatedly, and the number of comparisons needed grows very quickly as the list gets longer | B1 |
| a list as large as 1 million records, a bubble sort would take an impractically long time to complete | B1 |
| a merge sort divides the list and merges the parts back in order, which scales far better and is much more efficient for large lists | B1 |
| a merge sort does require extra memory to hold the sub-lists while merging, which is a drawback | B1 |
| valid recommendation: merge sort should be used, justified by its far better performance for a list of this size, despite using more memory | B1 |
| Final answer: Merge sort should be used: it scales far better than bubble sort for a list of 1 million records, despite needing extra memory | |
| Question 11[6 marks] | |
|---|---|
| Answer or working | Marks |
| declares a variable to store the smallest value found so far | B1 |
| inputs the first number and checks it is not -1 before initialising smallest; handles an immediate -1 by reporting that no smallest value exists | B1 |
| uses a loop that continues to input further numbers until -1 is entered, excluding the sentinel from processing | B1 |
| inside the loop, compares each newly entered number with the current smallest value | B1 |
| updates the smallest variable whenever a newly entered number is less than the current smallest value | B1 |
| outputs the smallest value once the loop ends if at least one non-sentinel number was entered | B1 |
| Final answer: input number / if number == -1 then / print "No numbers entered; no smallest value" / else / smallest = number / input number / while number != -1 / if number < smallest then smallest = number / endif / input number / endwhile / print smallest / endif | |