1 Consider the following algorithm in Fig.

2, expressed in pseudocode, as a function S:

Describe the purpose of this algorithm.

[2]

© OCR 2024. You may photocopy this page. 1 of 52 Created in ExamBuilder

 2(a) A 1-dimensional array stores a set of numbered cards from 0 to 7. An example of this data is shown in Fig in 4.1

The programmer wants to search for a specific card in the array.

State whether a binary search or a linear search would be the most appropriate method to search for a specific
card, and justify your answer.

Search method _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Justification

[3]
(b) A programmer is writing a computer program to sort the cards into the correct order (0 to 7).

(i) Show how an insertion sort would sort the array in Fig 4.1 into the correct order. Draw the array after each
move.

[3]

(ii) Describe how a quick sort algorithm works with the data in Fig 4.2.

© OCR 2024. You may photocopy this page. 2 of 52 Created in ExamBuilder

 [6]

© OCR 2024. You may photocopy this page. 3 of 52 Created in ExamBuilder

 (c) * Two other sorting algorithms the programmer could have used are a merge sort and bubble sort.

The worst case scenario for Merge is O(n log(n)) and for Bubble is O(n^2).

Compare the use of a merge sort and a bubble sort on this array, evaluating the performance of each sort,
making reference to the worse case Big O notation.

[9]

© OCR 2024. You may photocopy this page. 4 of 52 Created in ExamBuilder

 3(a) Linear search and binary search are two different algorithms which can be used for searching arrays.

When comparing linear and binary search it is possible to look at the best, worst and average number of items in
the array that need to be checked to find the item being searched for. Assume every item in the array is equally
likely to be searched for.

Complete the table below

Worst Case number of Average Case Best Case

searches
Binary Search Log2(n)-1
Linear Search n/2
[4]
(b) As the size of an array increases the average number of checks grows logarithmically. State what is meant by
logarithmic growth.

[1]
(c) Assuming an array is sorted give a situation when a linear search would perform better than a binary search.

[1]

4 The list of positive even numbers up to and including 1000 is

2, 4, 6,… 500, 502,… 998, 1000

An attempt is to be made to find the number 607 in this list.

Use the values given to show the first three steps for:

(i) a binary search

© OCR 2024. You may photocopy this page. 5 of 52 Created in ExamBuilder

 [3]

(ii) a serial search

[3]

(iii) Explain the difference between binary searching and serial searching.

[2]

(iv) State one advantage and one disadvantage of a binary search compared with a serial search.

[2]

© OCR 2024. You may photocopy this page. 6 of 52 Created in ExamBuilder

 5(a) Describe an algorithm to insert one data item into a queue data structure.

[4]

© OCR 2024. You may photocopy this page. 7 of 52 Created in ExamBuilder

 (b)

(i) Describe how an insertion sort is performed.

[3]

(ii) Demonstrate an insertion sort to place the following numbers into descending numerical order.

12 7 4 5 26

[4]

(iii) State one disadvantage of an insertion sort compared with a quick sort.

[1]

© OCR 2024. You may photocopy this page. 8 of 52 Created in ExamBuilder

 6 A programmer decides to use a dynamic data structure to hold items.

Part of the data held is as follows:

(42, 83, 27, 18, 52)

(i) Explain why a binary search would not be used for this data.

[2]

(ii) Describe the steps that a serial search would take to find the value 27.

[4]

(iii) Demonstrate the steps needed for a quick sort on these values: (42, 83, 27, 18, 52).

[5]

© OCR 2024. You may photocopy this page. 9 of 52 Created in ExamBuilder

 7(a) Describe the steps involved in a binary search to find the value 47 in the list below.

4, 7, 8, 21, 46, 47, 51

[4]

© OCR 2024. You may photocopy this page. 10 of 52 Created in ExamBuilder

 (b) A programmer has been tasked with writing a function that uses a binary search to return a Boolean value. The
function should return true if the target integer is found in a list of integers. Using pseudocode, write an
algorithm for the function.

[8]

© OCR 2024. You may photocopy this page. 11 of 52 Created in ExamBuilder

 (c) The target integer 8 exists in a list of integers 1, 4, 6, 9, 8, 12, 15 but is not found during a binary search. There
are no errors in the code.

(i) Give the reason why the target integer 8 is not found.

[1]

(ii) Identify and describe an alternative search algorithm that could be used.

[3]

© OCR 2024. You may photocopy this page. 12 of 52 Created in ExamBuilder

 8(a) A program needs to sort an array of lowercase strings into descending alphabetic order. An example of the data
is shown in Fig. 4.1.

Fig. 4.1

Show how a bubble sort would sort the data in Fig. 4.1.

[6]

© OCR 2024. You may photocopy this page. 13 of 52 Created in ExamBuilder

 (b) Show how a binary search would be performed on the array shown in Fig. 4.2 to find the value ‘duck’.

Fig. 4.2

[3]

© OCR 2024. You may photocopy this page. 14 of 52 Created in ExamBuilder

 (c)

(i) Describe how a merge sort differs from a bubble sort.

[4]

(ii) Name two sorting algorithms, other than a bubble sort and merge sort.

[2]

© OCR 2024. You may photocopy this page. 15 of 52 Created in ExamBuilder

 9 A 2-dimensional (2D) array, data, holds numeric data that Karl has entered. The declaration for the array is:

array data[16,11]

The array data, has 16 ‘rows’ and 11 ‘columns’.

Fig. 1.1 shows an extract from data.

Fig. 1.1

The data in each ‘row’ is in ascending numerical order.

Karl needs to analyse the data.

Karl needs to find out if a number he enters appears in a given row of the array. He is going to use a search
algorithm to do this.

(i) State the name of two different search algorithms that Karl could consider using.

[2]

© OCR 2024. You may photocopy this page. 16 of 52 Created in ExamBuilder

 (ii) Choose one search algorithm from those you gave in part (i), and describe how this algorithm works.

Algorithm

Description

[5]

© OCR 2024. You may photocopy this page. 17 of 52 Created in ExamBuilder

 10 A programmer is developing an ordering system for a fast food restaurant. When a member of staff inputs an
order, it is added to a linked list for completion by the chefs.

The user needs to be able to search for, and find, a specific order number.

State an appropriate search algorithm that could be used, and justify your choice against an alternative Search
algorithm.

Appropriate Search Algorithm

Justification

[3]

© OCR 2024. You may photocopy this page. 18 of 52 Created in ExamBuilder

 11(a) A programmer needs to sort an array of numeric data using an insertion sort.

(i) The following, incomplete, algorithm performs an insertion sort.

Complete the algorithm.

[3]

(ii) Show how an insertion sort would sort the following data:

© OCR 2024. You may photocopy this page. 19 of 52 Created in ExamBuilder

 6 1 15 12 5 6 9

[6]

© OCR 2024. You may photocopy this page. 20 of 52 Created in ExamBuilder

 (b)

(i) Using Big-O notation state the best case complexity of insertion sort.

[1]

(ii) Explain what your answer to part (b)(i) means.

[3]

12 Oscar owns a taxi company. He would like a program to handle taxi bookings from customers.

Some of Oscar’s customers are rated as gold. Customers who are rated as gold are given priority when they
make a taxi booking. Some customers rated as gold are shown here.

Arshad Betty Dave Freddie Harry Jimmy Kanwal Lynn Siad Tommy Will

When a customer makes a booking, Oscar will make use of a binary search to check if they are gold rated.

Oscar would like to know if ‘Tommy’ is gold rated.

(i) State the three values that will be set as the midpoints and then checked against ‘Tommy’ on each iteration
of the binary search.

Show your working here.

© OCR 2024. You may photocopy this page. 21 of 52 Created in ExamBuilder

 Midpoint 1

Midpoint 2

Midpoint 3

[3]

(ii) Oscar has 75 000 customers stored in his program.

Describe the benefit to Oscar of using binary searches in his program.

Benefit

[2]

(iii) State one other search algorithm that Oscar could have used.

[1]

(iv) State the pre-condition which has been met, which meant that Oscar did not need to use the search
algorithm you stated in the part above.

[1]

© OCR 2024. You may photocopy this page. 22 of 52 Created in ExamBuilder

 13(a) Poppy would like to use a bubble sort to sort 250 000 numbers into order from lowest to highest.

Currently the first five numbers before they have been sorted are:

195 584 167 147 158 187 160 125 184 236

Currently the last five numbers before they have been sorted are:

1058 19 558 1915 20 215 15

* Discuss how a bubble sort works and how efficient it will be when sorting these 250 000 items into order from
lowest to highest.

© OCR 2024. You may photocopy this page. 23 of 52 Created in ExamBuilder

 [9]

(b) State the number of comparisons that will need to be made in the first pass of the bubble sort.

[1]

(c) State the name of one other sorting algorithm that Poppy could have used.

[1]

14(a) The following pseudocode procedure performs an insertion sort on the array parameter.

01 procedure insertionSort(dataArray:byRef)
02 for i = 1 to dataArray.Length - 1
03 temp = dataArray[i]
04 tempPos = i – 1
05 exit = false
06 while tempPos >= 0 and exit == false
07 if dataArray[tempPos] < temp then
08 dataArray[tempPos + 1] = dataArray[tempPos]
09 tempPos = tempPos - 1
10 else
11 exit = true

© OCR 2024. You may photocopy this page. 24 of 52 Created in ExamBuilder

 12 endif
13 endwhile
14 dataArray[tempPos + 1] = temp
15 next i
16 endprocedure

* Two sorting algorithms are merge sort and quick sort.

Compare the use of merge sort, quick sort and insertion sort on an array with a small number of elements, and
on an array with a very large number of elements.

You should make reference to the time complexities of each algorithm using the Big O notation in your answer.

© OCR 2024. You may photocopy this page. 25 of 52 Created in ExamBuilder

 [9]

© OCR 2024. You may photocopy this page. 26 of 52 Created in ExamBuilder

 (b) Describe how a bubble sort will sort an array of 10 elements.

[6]

15(a) Identify one situation where a linear search is more appropriate than a binary search.

[1]

© OCR 2024. You may photocopy this page. 27 of 52 Created in ExamBuilder

 (b) The pseudocode function binarySearch() performs a binary search on the array dataArray that is passed
as a parameter. The function returns the array index of searchValue within the array, and -1 if it is not in the
array.

The pseudocode binary search algorithm is incomplete.

(i) Complete the algorithm by filling in the missing statements.

function binarySearch(dataArray:byref, upperbound, lowerbound, ………………………………)

while true
middle = lowerbound + ((upperbound – lowerbound) ………………………………)
if upperbound < lowerbound then
return ……………………………………………
else
if dataArray[middle] < searchValue then
lowerbound = ………………………………………………………………………………………………………………………
elseif dataArray[middle] > searchValue then
upperbound = ………………………………………………………………………………………………………………………
else
return ……………………………………………………………………………………………
endif
endif
endwhile
endfunction
[6]

(ii) The algorithm uses a while loop.

State a different type of loop that could be used instead of the while loop in the given algorithm.

[1]

© OCR 2024. You may photocopy this page. 28 of 52 Created in ExamBuilder

 (c) The tables below show possible Big O complexities for the worst-case space, best-case space and average time
for search algorithms.

Tick the worst-case space complexity for a binary and linear search.

Binary Linear
search search
O(log(n))
O(1)
O(n)

Tick the best-case space complexity for a binary and linear search.

Binary Linear
search search
O(log(n))
O(1)
O(n)

Tick the average time complexity for a binary and linear search.

Binary Linear
search search
O(log(n))
O(1)
O(n)
[6]

END OF QUESTION PAPER

© OCR 2024. You may photocopy this page. 29 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

1 To locate an item (1) in a list (1). The 2 Up to 2 marks for a valid description.
list is in some order (1).

Total 2

2 a 1 mark for linear search, 2 for justification 3

Justification:

The array is not sorted (1)

Linear does not need ordered / linear
goes through all elements from
beginning / binary needs a sorted array
(1)

b i 1 mark for each set of 2 moves 3 Allow follow through if one move is
incorrect

02174356
01274356 (1)
01247356
01234756 (1)
01234576
01234567 (1)

ii 1 mark per bullet to max 6 6 If no description i.e. the candidate has just
shown the quick sort, max 4 marks.
Uses divide-and-conquer (1)
First item becomes pivot / 2 is the pivot
(1)
Compare each item to the pivot (e.g.
compare 0 to 2, then 1 to 2) (1)
Make two lists, 1 with less than the
pivot… (0, 1) (1)
… 1 with more than the pivot
(7,4,3,5,6) (1)
Quick sort the new lists (1)
Recombine the sub-lists (1)

OR
Example of alternative quicksort method

© OCR 2024. You may photocopy this page. 30 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

marks for:

Uses divide-and-conquer (1)

Highlight first list element as start
pointer, and last list element as end
pointer
Repeatedly compare numbers being
pointed to…
…if incorrect, swap and move end
pointer
…else move start pointer
Split list into 2 sublists
Quick sort each sublist
Repeat until all sublists have only 1
number
Combine sublists

© OCR 2024. You may photocopy this page. 31 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

c Mark Band 3 – High level 9 AO1: Knowledge and Understanding

(7–9 marks) Indicative content
The candidate demonstrates a thorough
knowledge and understanding of merge Merge sort uses sub-lists
and bubble sorts; the material is generally Bubble sort uses a temp element
accurate and detailed. Bubble sort moves through the list
The candidate is able to apply their repeatedly
knowledge and understanding directly and Merge sort divides the list into smaller
consistently to the context provided. lists
Evidence / examples will be explicitly Merge is a recursive algorithm
relevant to the explanation. Worst case is logarithmic, scales up
There is a well-developed line of reasoning well
which is clear and logically structured. The Worst case is exponential, does not
information presented is relevant and scale up well
substantiated.
AO2: Application
Mark Band 2 – Mid level
(4–6 marks) Small data set
The candidate demonstrates reasonable Few changes are needed
knoledge and understanding of merge and Demonstrates use of merge and / or
bubble sorts; the material is generally bubble on the array
accurate but at times underdeveloped. Calculations of average speed / best
The candidate is able to apply their speed / worse speed
knowledge and understanding directly to
the context provided although one or two AO3: Evaluation
opportunities are missed. Evidence / Candidates will need to evaluate the
examples are for the most part implicitly benefits and drawbacks of each sorting
relevant to the explanation. algorithm
The candidate provides a reasonable e.g.
discussion, the majority of which is
focused. Evaluative comments are, for the Merge is fast on large data sets
most part appropriate, although one or two Bubble is intuitive (easier to program)
opportunities for development are missed. Both are fast (or even) on smaller data
There is a line of reasoning presented with sets
some structure. The information presented Bubble's average speed is worse than
is in the most part relevant and supported merge
by some evidence. Bubble will be easier to write for such a
small data set
Mark Band 1 – Low Level Accept argument for either way as long
(1–3 marks) as justified
The candidate demonstrates a basic
knowledge of merge and bubble sorts with
limited understanding shown; the material
is basic and contains some inaccuracies.
The candidates makes a limited attempt to
apply acquired knowledge and
understanding to the context provided.
The candidate provides a limited
discussion which is narrow in focus.

© OCR 2024. You may photocopy this page. 32 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

Judgements if made are weak and

unsubstantiated.
The information is basic and comunicated
in an unstructured way. The information is
supported by limited evidence and the
relationship to the evidence may not be
clear.

0 marks
No attempt to answer the question or
response is not worthy of credit.

Total 21

3 a 4 For 4 marks – 1 mark for each correct

entry.

b As x (or the size of the array) 1 For 1 mark.

increases, the rate at which y (or the
number of checks needed) increases
more slowly (1).
The inverse of exponential growth (1).
The rate of increase is a logarithmic
function of the size of the array (1).

c If the array is very small. (1) 1 For 1 mark.

If the item being searched for is very
close to the start of the array. (1)

Total 6

© OCR 2024. You may photocopy this page. 33 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

4 i Compare 607 with 500 3 Must use values given

Compare 607 with 750
Compare 607 with 625+/-1 Examiner's Comments
or
go to middle value 500 / 502 This was one of the questions that required
compare value with 607 an answer in context and many students
discard first half / repeat in second half of did poorly as a result of not contextualising
set their response. Centres should emphasise
to candidates that they need to think about
the context of their answer if the question
stem requires it.

ii Compare 607 with 2 3 Must use values given

Compare 607 with 4
Compare 607 with 6 Examiner's Comments
or
Start at 2 This question also suffered from
Compare with 607 candidates either not reading the question
Go to 4 (& repeat comparison… etc) properly or not contextualising their
response.

iii Binary search discards half data at each 2 Examiner's Comments

step
Serial search discards one data item at In the main a well answered question, any
each step / each item in turn candidates who did not gain marks for this
probably lost them for being too vague in
their answer; this was an easy question but
required a full answer to justify the mark.

iv Advantage: 2 Examiner's Comments

Generally faster (in large set of data)
Disadvantage: Well answered by most candidates who
Values must have been sorted / values obtained one mark with the more able
must be in order candidates getting the second mark.

Total 10

© OCR 2024. You may photocopy this page. 34 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

5 a if queue full… 4 Rear pointer indicating first free space in

…return error & stop queue - accept alternative with rear pointer
else insert item at rear pointer indicating final item & increment before
position… insertion
& increment rear pointer
Examiner's Comments

This was a standard algorithm that almost

everyone should have been able to get, but
a fair proportion of candidates did not put
the stop on “report error and stop” and/or
did not state that for a queue they should
have been adding to the rear pointer and
incrementing the rear pointer. Slightly
disappointing.

b i One item at a time / serially … 3

…moved into correct position… Do not allow swap(ped) or pivots
…until all items in list checked
Allow two lists.

One item at a time taken from 1st list…

…and inserted into 2nd list…
…in the correct place.

Examiner's Comments

There were quite a few very muddled

answers to this question, those that were
not muddled, were just plain wrong. A large
proportion of candidates either were
swapping for a bubble sort or using pivots;
neither of which were what was required.

ii 4 Method must be demonstrated somehow -

circles, underlining, description e.g. “insert
12” etc
Must be an insertion sort

1 mark per correct row after row 1 in Do not allow swap(ped) or pivots
sequence to max 4

Examiner's Comments

Those who knew what an insertion sort

was got this correct, a fair percentage used
quick sorts or bubble sorts and as such did
not receive any marks.

© OCR 2024. You may photocopy this page. 35 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

iii Less efficient/takes longer for large 1

sets of data Examiner's Comments

A lot of unnecessarily vague answers who

did not get an easy mark.

Total 12

© OCR 2024. You may photocopy this page. 36 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

6 i Data is not in any order / binary search 2

needs an ordered set of data Examiner's Comments
Data set is too small to warrant binary
search Almost all candidates got at least one mark
for this, an appropriate amount managed
the second mark as well.

ii Compare 42 (first item) to be searched 4

with 27 Examiner's Comments
Compare 83 (second value) and
discard A few candidates still tried to write an
Compare 27 (third value) algorithm for this, although they were good,
Display result / search stops they did not answer the question.

iii 5 Answer may vary depending on pivots

chosen
Alternate answer below:

Pick a number as the pivot. [1]

Create two sub lists of those elements
greater and those less than the pivot.
[1]
Without attempting to order within the
sub lists. [1]
Repeat until all sub lists are 1 item
large [1]
The elements assembled as a sorted
List of numbers correctly built up list. [1]
1 mark for new pivot / pointer
1 mark per move (max 3) Example Below (Candidates may choose
any elements as pivots)
↓ ↓ STEP ONE
42 83 27 18 52 Stays the same
↓ ↓
42 83 27 18 52 83 moves
↓ ↓
42 27 18 52 83 Stays the same
↓ ↓
42 27 18 52 83 Stays the same
↓ ↓
42 27 18 52 83 New pivot (18)
↓ ↓
27 18 42 52 83 42 moves
↓ ↓
18 27 42 52 83 27 moves

© OCR 2024. You may photocopy this page. 37 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

Examiner's Comments

This question generated a fairly bizarre

assortment of answers. Those who knew
what they were doing got it right, those
who didn't or weren't sure responded in
strange ways.

Total 11

© OCR 2024. You may photocopy this page. 38 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

7 a Find the middle point in the list / 21 / 4 Some marks such as the comparison may
element 4 be by implication if the candidate’s logic
Compare it to the value 47, false works
Is 47 greater than middle point, true
New subset is 46-51 / change lower Must refer to the list given in the question
bound to 46 / element 5 i.e. not a generic description
Find the middle of the new subset / 47 /
element 6 Is this value equal to 47, true Examiner's Comments
Search finishes
In general, many candidates had an
understanding of how a binary search
operated. Unfortunately, some gave a
generic description rather than answering
the specific question which required the
candidate to illustrate how a binary search
would operate on a specific data set. Some
candidates drew concise and elegant
diagrams with appropriate annotations that
made their answers much clearer than
those who wrote prose at great length.

© OCR 2024. You may photocopy this page. 39 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

b Finding midPoint and correctly 8 Max 8 marks

checking if midPoint value is target
value ...
... and if so returning true Note: candidates may have given a
Correctly checking that all elements recursive algorithm and this should is
have been checked ... perfectly acceptable.
... and if so returning false
Identify top or bottom of list ... Examiner's Comments
... if top then leftPtr set/passed as
midPoint + 1 ... The Binary Search is one of the algorithms
... if bottom then rightPtr set/passed specifically identified in the specification
as midPoint – 1 that candidates need to be able to program
Correct use of indentation (AO2.1) and understand. It is a difficult algorithm to
code correctly and only the most able
Example iterative example candidates managed to produce a strong
response to give the degree of accuracy
required. Many candidates wrote in
structured English which was not
acceptable – the question specifically
required a pseudocode solution.
Candidates are not expected to be able to
write pseudocode in the form given by
OCR in the specification appendix, and
variations from various programming
languages were taken into account.
However, the overall ability to write
pseudocode proved to be a key
differentiator and many candidates should
aim to improve their ability to write
pseudocode before the A2 examination.

c i The integers in the list are unsorted (1) 1

Examiner's Comments

Most candidates correctly identified that a

list needs to be in order for a binary search
to be applied. However, a worrying number
of candidates thought that it could not be
applied because there was an even
number of items in the list, and hence no
clear mid-point.

© OCR 2024. You may photocopy this page. 40 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

ii Identification (Max 1) 3 Accept serial

Examiner's Comments
Perform a linear search
Many candidates identified a linear search,
Description (Max 2) but fewer could give a full description as to
how a linear search operates. A number of
candidates confused searching with sorting
starting at the first element / each item algorithms.
is checked...
until value is found
or end of list reached and not found

Total 16

© OCR 2024. You may photocopy this page. 41 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

8 a 1 mark for each correct swap 6

identified/described

b 1 mark for each bullet 3

Duck is smaller than goat

Duck is less than frog/elephant
Duck is equal to duck/less than
elephant so only duck left

c i 1 mark per bullet to max 4 4 Allow points by demonstration/example

Merge sort splits the data

Merge sorts the split data as it is put
back together
Bubble moves through the data in a
linear way
Bubble moves through the data
repeatedly
Merge is more efficient with larger
volumes of data to sort
Merge may require more memory
space

ii 1 mark per example 2

e.g.

Insertion
Quick

Total 15

© OCR 2024. You may photocopy this page. 42 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

9 i 1 mark each 2

Binary [1] AO1.1

Linear [1] (2)

Examiner's Comment:
Most candidates knew that linear and
binary were the required types of search.
Some confused sorting algorithms with
searching algorithms.

ii If the algorithm name does not match the 5 For binary search, allow movement of
description given then max 4 marks for upper bound and lower bound instead of
description. making sub-lists

Binary

Works on an ordered set of data [1]

Find mid-point [1]
If equal to mid-point [1]
Report found [1]
If less than mid-point[1]
ake sub-list from left [1]
If greater than mid-point [1]
Make sub-list from right [1]
Repeat with sub-list until found /
sub-list is empty [1]

Linear

Can work on both ordered and

unordered data sets [1]
Get first element [1]
If equal [1]
Report found [1]
If not equal [1]
Move to next element [1]
Repeat for all elements, until found /
end of list reached [1]

Examiner's Comment:
Most candidates could describe some
points related to the searching algorithm
they identified, but fewer could go on to
describe the steps in depth.

Total 7

© OCR 2024. You may photocopy this page. 43 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

10 Algorithm, max 1 3 No marks for justification if linear has not

AO1.1 been identified
(1)
linear AO2.1
(2)
Justification, 1 mark per bullet to max 2

Items do not have to be in a specific

order

Binary needs items in order Examiner’s Comment:

Many candidates correctly identified a
linear search and could justify the need for
it. However, a lot of candidates did answer
binary search without appreciating that the
data set needed to be in order first.

Total 3

© OCR 2024. You may photocopy this page. 44 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

11 a i 1 mark for each correct item in bold 3 answers must be in the correct case as
AO1.1 given
(3) e.g. currentData

Examiner’s Comment:
Many candidates found it difficult to apply
the logic required to calculate the correct
solution. Stronger candidates could do so
even if they did not know the algorithm for
insertion sort.

ii 1 mark for contents of each row in table 6 … each row is dependent upon the
AO2.1 preceding row being correct
(6)

Examiner’s Comment:
Some candidates confused insertion sort
with other sorting algorithms, but many
candidates gave good answers in
diagrammatic form. Answers in
diagrammatic form after each pass of the
loop were often far clearer than prose
descriptions. This form of answer should
be encouraged.

b i O(n) 1
AO1.1
(1)

ii 1 mark per bullet to max 3 3 B(ii) dependent upon b(i) being correct
AO1.2 i.e. answers for O(n) only
(3)
The best case is for a sorted list (O(n))
As the number of elements increases Accept appropriate graph for bullet points
… the number of steps increases in a 2 and 3
linear fashion

Examiner’s Comment:
Whilst many candidates had some
knowledge of 'Big O' notation fewer could
apply it correctly within the context given.

© OCR 2024. You may photocopy this page. 45 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

Total 13

12 i 1 mark per bullet up to a maximum of 3 3

marks:
A02.1
5 (Jimmy) (3)
8 (Siad)
9 (Tommy)

ii 1 mark per bullet up to a maximum of 2 2

marks, e.g:
A01.2
Efficient (2)
...as does not need to search every
single element/uses divide and
conquer

iii Linear Search / Serial Search 1

A02.1
(1)

iv The items are in alphabetical order / 1

the items are sorted
A02.1
(1)

Total 7

© OCR 2024. You may photocopy this page. 46 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

13 a Mark Band 3 – High level (7-9 marks) 9 Knowledge and Understanding

The candidate demonstrates a thorough AO1.1
knowledge and understanding of bubble (2) All adjacent items are compared
sorts; the material is generally accurate AO1.2 against each other.
and detailed. The candidate is able to (2) The biggest number in the adjacent
apply their knowledge and understanding A02.1 pair is swapped over with the smallest
directly and consistently to the context (2) number. A temp variable is used to
provided. Evidence/examples will be A03.3 hold the data while it’s being moved.
explicitly relevant to the explanation. The (3) When a swap is made a flag is set.
candidate is able to weigh up the use of This is repeated for all adjacent values,
bubble sorts within the context which known as one pass.
results in a supported and realistic At the end of one pass, the largest item
judgment as to whether it is suitable to use should appear at the end of the list.
within the context.There is a well- If at the end of the list the flag has
developed line of reasoning which is clear been set the flag is unset and the
and logically structured. The information algorithm starts from the beginning of
presented is relevant and substantiated. the list again.
When the algorithm gets to the end of
Mark Band 2 – Mid level (4-6 marks) the list and the flag is unset the list is
The candidate demonstrates reasonable sorted.
knowledge and understanding of bubble
sorts; the material is generally accurate but Application
at times underdeveloped.The candidate is
able to apply their knowledge and As there are 250,000 items a bubble
understanding directly to the context sort would perform very slowly as a lot
provided although one or two opportunities of passes will need to be made in order
are missed. Evidence/examples are for the to sort the items.
most part implicitly relevant to the Bubble sorts are better suited to data
explanation. sets where the items are almost/partly
The candidate makes a reasonable sorted. However the smaller numbers
attempt to come to a conclusion showing are currently towards the end and the
some recognition of influencing factors that larger numbers are towards the start.
would determine whether it is possible to This will therefore increase the amount
use bubble sorts in this context. of comparisons / passes/swaps
There is a line of reasoning presented with required which will therefore slow the
some structure. The information presented performance of the sort down.
is in the most part relevant and supported
by some evidence Evaluation

Mark Band 1 – Low Level (1-3 marks) The algorithm is easy to implement as
The candidate demonstrates a basic the number of lines of code is less than
knowledge of bubble sorts with limited other standard sorting algorithms.
understanding shown; the material is basic Although a bubble sort will be able to
and contains some inaccuracies. The sort the items into order, it will take
candidates makes a limited attempt to longer than other sorting algorithms
apply acquired knowledge and due to the number of items and the
understanding to the context provided. The current order or items in the unsorted
candidate provides nothing more than an list.
unsupported assertion.The information is

© OCR 2024. You may photocopy this page. 47 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

basic and comunicated in an unstructured

way. The information is supported by
limited evidence and the relationship to the
evidence may not be clear.

0 marks
No attempt to answer the question or
response is not worthy of credit.

b 249,999 1
A02.2
(1)

c Insertion sort 1 Allow other sorting algorithms not listed in

A02.1 the specification (e.g. Merge Sort, Quick
(1) Sort etc)

Total 11

© OCR 2024. You may photocopy this page. 48 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

14 a Mark Band 3 – High level (7-9 marks) 9 AO1: Knowledge and Understanding
The candidate demonstrates a thorough AO1.1 Indicative content
knowledge and understanding of big O and (2) O(1)
sorting algorithms; the material is generally AO1.2
accurate and detailed. (2) Constant space, does not change
The candidate is able to apply their AO2.1
knowledge and understanding directly and (2) O(n)
consistently to the context provided. AO3.3
Evidence/examples will be explicitly (3) Linear
relevant to the explanation. Same as number of elements
The candidate is able to weigh up the use As number of elements increases so
of the sorting algorithms which results in a does the time/space
supported and realistic judgment as to
whether it is possible to use them in this O(n2)
context.
There is a well-developed line of reasoning polynominal
which is clear and logically structured. The As number of elements increases,
information presented is relevant and time/space increases by *n
substantiated.
O(n log(n))
Mark Band 2 – Mid level (4-6 marks)
The candidate demonstrates reasonable Linearithmic
knoledge and understanding of big O and
sorting algorithms; the material is generally
accurate but at times underdeveloped. AO2: Application
The candidate is able to apply their
knowledge and understanding directly to Space: Merge sort will require more
the context provided although one or two memory usage as the number of
opportunities are missed. elements increases. Insertion will not
Evidence/examples are for the most part require any more space than original.
implicitly relevant to the explanation. Quick will increase but not as much as
The candidate makes a reasonable merge.
attempt to come to a conclusion showing Best time: Insertion increases at the
some recognition of influencing factors that same rate as the number of elements.
would determine whether it is possible to Quick and merge increase at greater
use the sorting algorithms in this context. rate
There is a line of reasoning presented with Worst time: insertion and quick
some structure. The information presented increase significantly by n for each
is in the most part relevant and supported additional item. Merge sort increases
by some evidence less per element.
Log more appropriate for large number
Mark Band 1 – Low Level (1-3 marks) of elements
The candidate demonstrates a basic
knowledge of big O and sorting algorithms AO3: Evaluation
with limited understanding shown; the e.g.
material is basic and contains some
inaccuracies. The candidates makes a Small array – space is not important.
limited attempt to apply acquired Few number of elements. Look for
knowledge and understanding to the consistency.

© OCR 2024. You may photocopy this page. 49 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

context provided. Large array therefore memory

The candidate provides nothing more than important – could remove merge as
an unsupported assertion. inappropriate. Logarithmic more
The information is basic and comunicated efficient.
in an unstructured way. The information is
supported by limited evidence and the
relationship to the evidence may not be
clear.

0 marks
No attempt to answer the question or
response is not worthy of credit.

b 1 mark per bullet for description to max 6 6

AO1.1
Compare each pair of adjacent (2)
elements AO1.2
If they are not in the correct order then (4)
swap the elements
If they are in the correct order then do
no swap elements
When you read the end of the array
return to the start
Repeat n elements time
Set a flag to be false whenever a swap
is made
…repeat the loop if the flag is not false

Total 15

© OCR 2024. You may photocopy this page. 50 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

15 a 1 mark for any example 1 AO1.2

e.g. (1)

Data is not sorted

Item you are looking for is the first item
in the list
Small number of items

b i 1 mark for each number/statement up to a 6 AO1.2

maximum of 6 marks: (2) AO3.3
(4)
function
binarySearch(dataArray:byref,
upperbound, lowerbound,
searchValue)
while true
middle = lowerbound +)
((upperbound – lowerbound))
DIV 2)
if upperbound < lowerbound
then
return -1
else
if dataArray[middle] <
searchValue then
lowerbound = middle + 1
elseif dataArray[middle] >
searchValue then
upperbound = middle - 1
else
return middle
endif
endif
endwhile
endfunction

ii Do…until // repeat…until // post condition 1 AO1.2

(1)

© OCR 2024. You may photocopy this page. 51 of 52 Created in ExamBuilder

 Mark Scheme

Question Answer/Indicative content Marks Guidance

c 1 mark for each tick up to a maximum of 6 6 AO1.1

marks (6)
Worst-case space complexity:

Binary Linear
search search
O(log(n))
O(1) ✓ ✓
O(n)
Best-case space complexity:

Binary Linear
search search
O(log(n))
O(1) ✓ ✓
O(n)

Average time complexity:

Binary Linear
search search
O(log(n)) ✓
O(1)
O(n) ✓

Total 14

© OCR 2024. You may photocopy this page. 52 of 52 Created in ExamBuilder

Powered by TCPDF (www.tcpdf.org)