Level:
Correct: 0
Incorrect: 0
Marks: 0/0
Exam Practice
Course:
Topics:
AQA GCSE Computer Science (Paper 2) Smart practice A mixed round aimed at your weak spots
Unit 1
3.3 Fundamentals of data representation
Unit 2
3.4 Computer systems
Unit 3
3.5 Fundamentals of computer networks
Unit 4
3.6 Cyber security
Fundamentals of cyber security; cyber security threats
Cyber security, its threats and penetration testing
Methods to detect and prevent cyber security threats
Detecting and preventing cyber security threats
Unit 5
3.7 Relational databases and SQL
Unit 6
3.8 Ethical, legal and environmental impacts
Ethical, legal and environmental impacts
Ethical, legal and environmental impacts of technology
Avg
score:
–
Topics
done:
0/22

Data compression: Huffman coding and RLE

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. 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. 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).

  2. 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.

Block diagram with 11 parts in five rows. Top row: a circle "10". Second row, left to right: a circle "4" and a circle labelled X. Third row, left to right: a circle "O 2", a circle "K 2", a circle "E 3" and a circle labelled Y. Fourth row, left to right: a circle "R 1" and a circle "2". Bottom row, left to right: a circle "B 1" and a circle "P 1". Connections: a line joining "10" and "4", labelled "0"; a line joining "10" and circle X, labelled "1"; a line joining "4" and "O 2", labelled "0"; a line joining "4" and "K 2", labelled "1"; a line joining circle X and "E 3", labelled "0"; a line joining circle X and circle Y, labelled "1"; a line joining circle Y and "R 1", labelled "0"; a line joining circle Y and "2", labelled "1"; a line joining "2" and "B 1", labelled "0"; a line joining "2" and "P 1", labelled "1".

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. 1 mark

    X = 6

    All marks AO2 (apply). X = E (3) + Y (3).

  2. 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.

Write rows 2, 3 and 5 in the same way.

Bitmap image drawn as a grid of 12 × 5 pixels (12 wide, 5 high), each pixel white or black. A key gives the binary code of each colour: 0 = white, 1 = black. The columns are numbered 1 to 12 along the top and the rows 1 to 5 down the left. The pixels, row by row from the top (left to right): row 1: 3 black, 6 white, 3 black; row 2: 2 black, 2 white, 4 black, 2 white, 2 black; row 3: black, 2 white, 6 black, 2 white, black; row 4: 2 black, 2 white, 4 black, 2 white, 2 black; row 5: 4 white, 4 black, 4 white.

Model answer

Row 2 is 110011110011: 2 1 2 0 4 1 2 0 2 1
Row 3 is 100111111001: 1 1 2 0 6 1 2 0 1 1
Row 5 is 000011110000: 4 0 4 1 4 0

Explanation

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. 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.

  2. 1 mark

    Row 3: 1 1 2 0 6 1 2 0 1 1

  3. 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.

Study Helper Hints 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.