Time allowed: 45 minutes
| Centre number |
| | | |
|
Candidate number |
| | | |
| First name |
|
Last name |
INSTRUCTIONS
- Use black ink.
- Answer all the questions.
- Pseudocode or OCR Exam Reference Language should be used for all algorithm writing questions.
INFORMATION
- The total mark for this paper is 42.
- The marks for each question are shown in brackets [ ].
Turn over
Section A: Algorithm Mechanics & Tracing
1
A computer program needs to sort the following list of names into alphabetical order:
[ "Dave", "Alan", "Cian", "Ben" ]
(a) Show the state of the list after the
first pass of a Bubble Sort.
[2]
(b) Explain why a Bubble Sort requires a second pass for this specific list, even if the list appears sorted.
[2]
2
The following list is to be sorted using an
Insertion Sort:
[ 12, 5, 18, 1, 9 ]
(a) Show the state of the list after the
second insertion (i.e., after the number 18 has been processed).
[2]
(b) Describe the logical steps the algorithm took to place the number
1 into the correct position during the next stage.
[3]
3
A
Merge Sort is being performed on the following list of numbers:
[ 15, 3, 9, 12, 6, 2 ]
(a) The first stage of a Merge Sort is to divide the list. Show the state of the list when it has been
completely separated into individual lists.
[2]
(b) Show the step-by-step process of merging these lists back together into a final sorted list.
(You may use arrows or write the list states on separate lines)
[3]
Turn over
4
Compare Merge Sort and Bubble Sort.
Explain
one advantage of using a Merge Sort and
one advantage of using a Bubble Sort.
[4]
Section B: Code Production & Logic
5
A junior programmer has written an algorithm to perform a Bubble Sort, but it contains logic errors.
The goal is to sort the array
scores in
ascending order.
01 array scores = [9, 2, 5, 1]
02 n = scores.length
03 swapped = True
04 while swapped == True
05 swapped = False
06 for i = 0 to n - 1
07 if scores[i] < scores[i+1] then
08 temp = scores[i]
09 scores[i] = scores[i+1]
10 scores[i+1] = temp
11 endif
12 next i
13 endwhile
(a) Identify the line number where the comparison direction is incorrect for an
ascending sort.
[1]
Line:
(b) Identify the line number that causes an "Index Out of Bounds" error when the loop reaches the end of the array.
[1]
Line:
(c) Explain the purpose of the variable
swapped in this algorithm.
[2]
Turn over
6
Write an algorithm using
Pseudocode or
OCR Reference Language to perform an
Insertion Sort on an array named
data.
You do not need to declare variables, but you must show the logic for:
- Iterating through the list.
- Comparing the current item with the previous items.
- Shifting items to the right to make space.
[6]
Section C: Scenario-Based Application
7
A database contains 1,000,000 records. The records are already sorted, but a user adds 5 new records to the end of the list.
The system needs to ensure the entire list is sorted again.
(a) Which sorting algorithm would be most efficient for this specific scenario?
[1]
(b) Justify your choice in part (a).
[2]
8
Describe how a Merge Sort uses the technique of
Decomposition (divide and conquer).
[2]
Turn over