Exam style questions
Download a pdf version of the test
Use the space below each question or a pen and paper to write your answer. When complete click the button for the answer and mark scheme.
NOTE: Answers typed into the browser will not be retained if you leave the page or refresh
Questions
Define algorithm. (1 mark)
An algorithm is a sequence of steps that can be followed to complete a task.(1)
Explain what decomposition is and how it might apply to making a higher or lower number guessing game. (2 marks)
Decomposition is breaking a problem into a number of sub-problems(1)
Any suitable example of a subroutine from the game e.g. getGuess(), checkGuess(), getName() etc.(1)
Explain a way in which the London Tube Map demonstrates abstraction. (2 marks)
Abstraction is the process of removing unnecessary detail from a problem.(1)
Any suitable example e.g. the distances are spaced to fit names on not by how far apart they actually are
Basic flowchart algorithm
What is the purpose of the basic flowchart algorithm above? (2 marks)
It gets input of a number from the user(1) and outputs whether it is a multiple of 3 or not(1)
What is the processing in the algorithm? (1 mark)
Comparing the result of dividing the number input by 3 and storing the remainder with 0(1)
Basic pseudocode algorithm
What would be the output if the user entered 5 when running the basic pseudocode algorithm above? (1 mark)
The output would be 1, 2, 3, 4, 5 each on a new line
Explain how a binary search for 'fuchsia' in the array colours=['amber','blue','coral','deeppink','fuchsia','gold','honeydew'] would proceed. (5 marks)
It would start by comparing the middle item in the list 'deeppink' with the search term 'fuchsia'(1)
As they don't match and fuchsia would come after 'deeppink alphabetically, 'deeppink' and everything to its left is removed.(1)
It would now look at the middle of the shortened list 'gold' and compare that with 'fuchsia'(1)
As they don't match and 'fuchsia' would come before 'gold' alphabetically, 'gold' and 'honeydew' are removed.(1)
There is only one item left in the list and it is the search term so it would return found.(1)
Comparing algorithms
Both algorithms above have the same purpose. What is it, which algorithm is more efficient and why? (3 marks)
They are linear search algorithms.(1)
The while loop is more efficient(1) becuase it would stop if it found the value which could be a big saving if it was early in a long array.(1)
The next couple of questions refer to the array nums ← [21,3,42,7,13,22,18]
Show the process for making a pass of this data in a bubble sort (4 marks)
For full marks you will have shown something like below showing each comparison and when a swap is made:
| 21 |
03 |
42 |
07 |
13 |
22 |
18 |
| 03 |
21 |
42 |
07 |
13 |
22 |
18 |
| 03 |
21 |
42 |
07 |
13 |
22 |
18 |
| 03 |
21 |
07 |
42 |
13 |
22 |
18 |
| 03 |
21 |
07 |
13 |
42 |
22 |
18 |
| 03 |
21 |
07 |
13 |
22 |
42 |
18 |
| 03 |
21 |
07 |
13 |
22 |
18 |
42 |
If not fully correct:
1 mark - pairwise comparisons are made
1 mark - One pass is shown i.e. it goes once across the list
1 mark - at least one accurate swap
Show the process for merge sorting this data (3 marks)
For full marks you will have shown something like below where the data is split continuously until it is atomic and put in order as it is put in order by combining pairs of lists. Allow splits to the right not left when the list has an uneven number of items.
[21,3,42,7,13,22,18]
[21,3,42,7],[13,22,18]
[21,3],[42,7],[13,22],[18]
[21],[3],[42],[7],[13],[22],[18]
[3,21],[7,42],[13,22],[18]
[3,7,21,42],[13,18,22]
[3,7,13,18,21,22,42]
If not fully correct:
1 mark - splitting until atomic without swaps
1 mark - At least one correctly remerged list
Explain the advantages and disadvantages of the merge sort compared to the bubble sort (3 marks)
The merge sort is more efficient for large lists than the bubble sort(1) but the bubble sort uses less memory than the merge sort.(1)
<< Previous: Efficiency of algorithms Programming Home GCSE Home Next: Data types >>