Practise 30 exam-style questions on Data compression: Huffman coding and RLE for AQA GCSE Computer Science (Paper 2). Write your answer as you would in the exam and get it marked in seconds against the mark scheme, point by point, with the Study Helper on hand if you get stuck.
30 questions
1–4 marks each
Instant marking
No sign-up needed
20 questions, marked as you go
Sample questions with model answers
Here are 4 of the questions in this topic, each with a model answer, an explanation of why it earns the marks and the mark scheme an examiner would use.
Question 1
1 mark
A row of a black and white bitmap image is stored as 1111000000011111, where 1 is black and 0 is white.
Which of these shows the row as run length encoding (RLE) frequency/data pairs?
Choose your answer.
4 1 7 0 5 1
1 4 0 7 1 5
4 7 5
4 0 7 1 5 0
Model answer
4 1 7 0 5 1
Explanation
The row has a run of four 1s, then seven 0s, then five 1s, and each run is written as its frequency followed by its data value. 1 4 0 7 1 5 puts the value before the frequency, 4 7 5 leaves out the values, and 4 0 7 1 5 0 has the colours the wrong way round.
Mark scheme
1 mark
4 1 7 0 5 1
Mark is for AO2 (apply). If more than one option is given, 0 marks.
Question 2
2 marks
A file that has been compressed using Huffman coding must also store the Huffman tree, or a table of the codes it uses.
Explain why.
Model answer
Huffman codes are not a fixed standard like ASCII: they are worked out from how often each character appears in that particular file, so another file will have different codes. To decompress the file, the computer must know which code stands for which character, so the tree (or table) has to be stored with the data.
Explanation
ASCII codes are the same everywhere, but Huffman codes are built for each piece of data. Without the tree the bits are meaningless, so it must travel with the compressed data, which slightly reduces the saving. Saying 'so it can be read' without explaining that the codes differ between files is not enough.
Mark scheme
1 mark
the codes are not standard / fixed // they depend on the frequencies of the characters in that file // different files have different codes
All marks AO1 (understanding).
1 mark
without the tree the computer could not tell which character each code represents // could not decompress / decode the data
I. 'the tree adds to the size of the file' (true, but it does not explain why the tree is needed).
Question 3
2 marks
The figure shows a Huffman tree for the word BOOKKEEPER. Two of the nodes are labelled X and Y instead of showing their values.
State the values of X and Y.
Model answer
Each node's value is the total of the two nodes joined below it. Y = 1 (R) + 2 = 3 X = 3 (E) + 3 (Y) = 6 Check: 4 + 6 = 10, the number of letters in BOOKKEEPER.
Explanation
When a Huffman tree is built, the two lowest nodes are joined to make a new node whose value is their combined frequency. So each value is found by adding the two values below it, working from the bottom up. The root must equal the total number of characters, 10, which is a useful check.
Mark scheme
1 mark
X = 6
All marks AO2 (apply). X = E (3) + Y (3).
1 mark
Y = 3
Y = R (1) + 2. ft X as 3 + their Y.
Question 4
3 marks
Leon is compressing the 12 × 5 logo in the figure using run length encoding. He has already written row 1 as 3 1 6 0 3 1, using 1 for black and 0 for white.
Each run of identical pixels becomes one pair: how many pixels, then the colour value. A single pixel on its own still needs a pair with a frequency of 1, which is why row 3 starts 1 1. Check each row by adding the frequencies: they must total 12.
Mark scheme
1 mark
Row 2: 2 1 2 0 4 1 2 0 2 1
All marks AO2 (apply). Each pair is frequency then data value. I. brackets or commas between pairs.
1 mark
Row 3: 1 1 2 0 6 1 2 0 1 1
1 mark
Row 5: 4 0 4 1 4 0
DPT. If the same error is repeated in every row (e.g. data value written before frequency throughout), penalise it once only.
Ready to try the rest? Every answer you write is marked against the mark scheme, so you can see exactly where the marks are.
Ctrl + Enter to check
Study HelperHints first, answers after you try
Stuck on this one? Ask for a hint and I’ll point you in the right direction, without giving the answer away. Once you’ve checked your answer, I’ll show you how the marks are awarded.