Skip to the worksheet
Revision Library
Choose a subject

Algorithms - Worksheets, Questions and Revision

16 original exam-style questions - 8 pages of questions with a full mark scheme - free printable PDF.

Grades 1-9

This topic is chapter 9 of GCSE Computer Science Topic Workbook 1 and chapter 9 of GCSE Computer Science 10-Minute Tests.

Revision Library
revisionlibrary.co.uk
GCSE · Computer Science

2.1 Algorithms

OCR J277 · Calculators not allowed · about 85 minutes
Total Marks
Name: _______________________________    Date: ____ / ____ / ______
Answer ALL questions. Show all your working.
1
A systems analyst is designing a new algorithm to calculate a student's average test score.
(a)State two ways in which an algorithm can be represented, other than by using a written description in ordinary sentences.(2)
(b)Identify one advantage of using a flowchart, rather than pseudocode, to represent an algorithm.(1)
(Total for Question 1 is 3 marks)
2
A student is asked to write a program to help organise a school's sports day.
(a)State two sub-problems the student could identify by decomposing the problem 'organise a school's sports day'.(2)
(b)Explain, using this scenario, what is meant by 'abstraction' when designing an algorithm.(2)
(Total for Question 2 is 4 marks)
3
A programmer writes the following pseudocode, using the OCR Exam Reference Language.
total = 0
for i = 1 to 5
total = total + i
next i
print(total)
(a)Complete a trace table for this algorithm, showing the value of i and total at the end of each pass through the loop.(4)
(b)State the value output by the algorithm.(1)
(Total for Question 3 is 5 marks)
4
An array called scores contains the values [55, 62, 48, 71, 60, 39] at indices 0 to 5.
(a)Describe how a linear search algorithm would locate the value 71 in this array, stating the number of comparisons needed.(3)
(b)State one disadvantage of using a linear search, rather than a binary search, on a large, sorted dataset.(1)
(Total for Question 4 is 4 marks)
5
An array called scores has 10 elements, at indices 0 to 9.
(a)Write an algorithm, using pseudocode, that finds and outputs the largest value in the array scores.(4)
(Total for Question 5 is 4 marks)
6
An algorithm uses a FOR loop that runs from 0 to 15 inclusive, using a variable called cycle to count each iteration.
(a)State the 8-bit binary representation of the maximum value that cycle reaches.(1)
(b)Convert the maximum value of cycle to hexadecimal.(1)
(c)Explain why programmers often use hexadecimal, rather than binary, when reading values from trace tables or debugging output.(2)
(Total for Question 6 is 4 marks)
7
An array contains the values [8, 3, 6, 1, 9], which need to be sorted into ascending order using a bubble sort that compares and swaps adjacent items.
(a)Show the state of the array after each comparison in the first full pass of the bubble sort.(4)
(b)State the maximum number of full passes a bubble sort would need to fully sort a list of 5 items.(1)
(Total for Question 7 is 5 marks)
8
A programmer needs to validate user input.
(a)Write an algorithm, using pseudocode, that repeatedly asks the user to input a number, and only accepts a value between 1 and 10 inclusive, then outputs the message 'Valid' once an acceptable value has been entered.(4)
(Total for Question 8 is 4 marks)
9
A sorted array called nums, in ascending order, contains: [3, 9, 14, 22, 27, 35, 41, 48, 55, 62] at indices 0 to 9.
(a)State the condition that must be met before a binary search can be used on this array.(1)
(b)A binary search uses mid <- (lower + upper) DIV 2 to find the middle index at each step. Complete a trace table to show the values of lower, upper and mid, and the outcome of each comparison, as a binary search locates the value 41.(5)
(c)State the number of comparisons made to find the value using binary search in part (b), and explain why this is fewer than a linear search would need in the worst case for this array.(2)
(Total for Question 9 is 8 marks)
10
An array contains the values [5, 2, 9, 1, 6], to be sorted into ascending order using insertion sort.
(a)Complete a trace table to show the state of the array after each new element has been inserted into its correct position.(4)
(b)Insertion sort is described as an 'in-place' sorting algorithm. State what is meant by an in-place algorithm.(1)
(Total for Question 10 is 5 marks)
11
Merge sort is an example of a 'divide and conquer' algorithm.
(a)Describe how merge sort would sort a list of 8 unsorted numbers, referring to both the dividing stage and the merging stage.(4)
(b)State one advantage of merge sort over bubble sort when sorting a very large dataset.(1)
(Total for Question 11 is 5 marks)
12
A programmer intends the following pseudocode to output the sum of all even numbers between 1 and 20 inclusive, but it contains errors.
total <- 0
FOR i <- 1 TO 20
    IF i / 2 = 0 THEN
        total <- total + 1
    ENDIF
NEXT i
OUTPUT total
(a)Identify two errors in the algorithm above which mean it does not correctly output the sum of all even numbers between 1 and 20.(2)
(b)Rewrite the algorithm with these errors corrected.(2)
(Total for Question 12 is 4 marks)
13
A programmer compares linear search and binary search on datasets of different sizes.
(a)Explain why the difference in efficiency between linear search and binary search becomes more significant as the size of the dataset increases.(3)
(b)Calculate the maximum number of comparisons required by a binary search on a sorted list of 1024 items.(2)
(Total for Question 13 is 5 marks)
14
A programmer writes the following pseudocode.
FUNCTION doubleIfEven(num)
    IF num MOD 2 = 0 THEN
        RETURN num * 2
    ELSE
        RETURN num
    ENDIF
ENDFUNCTION

total <- 0
FOR i <- 1 TO 4
    total <- total + doubleIfEven(i)
NEXT i
OUTPUT total
(a)Complete a trace table to show the value returned by doubleIfEven for each value of i, and the running value of total.(4)
(b)State the value output by the program.(1)
(Total for Question 14 is 5 marks)
15
A school is choosing which sorting algorithm to use to sort a list of 5000 student records by surname. The list is already nearly in alphabetical order, because it was exported from an existing system that keeps records mostly sorted. Discuss which of bubble sort, insertion sort and merge sort would be most suitable for this task, justifying your answer by referring to how each algorithm works and how efficient it is.
(Total for Question 15 is 6 marks)
16
Two algorithms both correctly sort the same array. One algorithm sorts the array in place, while the other creates a new array during sorting.
(a)State which of these two algorithms is likely to use more memory, and explain your reasoning.(2)
(Total for Question 16 is 2 marks)
Mark scheme · 2.1 Algorithms

Question 1

  • (a) flowchartB1
  • (a) pseudocode (accept structured English)B1
  • (a) Answer: Flowchart; pseudocode.
  • (b) a valid advantage, e.g. it shows the flow/structure/logic of the algorithm visually, making it easier for people who cannot yet read code to follow (oe)B1
  • (b) Answer: A flowchart shows the structure and flow of the algorithm visually, so it can be understood by people without programming knowledge.

Question 2

  • (a) any valid sub-problem, e.g. scheduling the order/timing of eventsB1
  • (a) any different valid sub-problem, e.g. assigning students to house teams, or recording race results, or allocating equipmentB1
  • (a) Answer: Example sub-problems: scheduling the events; recording and ranking race results.
  • (b) abstraction means removing details that are not relevant to solving the problem (oe)B1
  • (b) a relevant example applied to the scenario, e.g. ignoring the weather forecast and focusing only on event times and participant lists (oe)B1
  • (b) Answer: Abstraction means ignoring details that are not needed to solve the problem, such as ignoring the weather forecast for the day and focusing only on the information needed to schedule events and record results.

Question 3

  • (a) i = 1, total = 1B1
  • (a) i = 2, total = 3B1
  • (a) i = 3, total = 6; i = 4, total = 10B1
  • (a) i = 5, total = 15 (all five rows correct, cao)B1
  • (a) Answer: i: 1,2,3,4,5 -> total: 1,3,6,10,15
  • (b) 15 (cao)B1
  • (b) Answer: 15

Question 4

  • (a) starts at index 0 and compares each item in turn to the target value (71) (oe)B1
  • (a) moves to the next index each time the current item does not match, continuing until a match is found (oe)B1
  • (a) correctly states 4 comparisons are needed (55, 62, 48, 71 - cao)B1
  • (a) Answer: The linear search checks index 0 (55), index 1 (62), index 2 (48), then index 3 (71), which matches. 4 comparisons are needed.
  • (b) a linear search can require checking every item in the worst case, so it is much slower/less efficient on large datasets than a binary search (oe)B1
  • (b) Answer: A linear search may need to check every item in the dataset, making it much slower than a binary search for large, sorted data.

Question 5

  • (a) initialises a variable to the first element of the array, e.g. max <- scores[0]M1
  • (a) uses a loop to iterate through the remaining elements of the array, e.g. FOR i <- 1 TO 9M1
  • (a) compares each element to the current maximum and updates it if a larger value is found, e.g. IF scores[i] > max THEN max <- scores[i]M1
  • (a) outputs the maximum value after the loop has finished (any correct logic; ignore minor syntax errors)A1
  • (a) Answer:
    max <- scores[0]
    FOR i <- 1 TO 9
        IF scores[i] > max THEN
            max <- scores[i]
        ENDIF
    NEXT i
    OUTPUT max

Question 6

  • (a) 00001111 (cao)B1
  • (a) Answer: 00001111
  • (b) 0F (accept F, cao)B1
  • (b) Answer: 0F
  • (c) hexadecimal is much more compact/shorter than binary, so it is quicker and easier for a human to read (oe)B1
  • (c) each hexadecimal digit represents exactly 4 bits, so converting between binary and hexadecimal is quick and there is less chance of error than reading long binary strings (oe)B1
  • (c) Answer: Hexadecimal is far more compact than binary and easier for humans to read; each hex digit maps to exactly 4 bits, making conversion quick and reducing the chance of misreading long binary strings.

Question 7

  • (a) compare 8 and 3: swap, giving [3, 8, 6, 1, 9]B1
  • (a) compare 8 and 6: swap, giving [3, 6, 8, 1, 9]B1
  • (a) compare 8 and 1: swap, giving [3, 6, 1, 8, 9]B1
  • (a) compare 8 and 9: no swap needed, array remains [3, 6, 1, 8, 9] (cao)B1
  • (a) Answer: [3,8,6,1,9] -> [3,6,8,1,9] -> [3,6,1,8,9] -> [3,6,1,8,9] (end of pass 1)
  • (b) 4 (n - 1 passes for n = 5 items, cao)B1
  • (b) Answer: 4

Question 8

  • (a) uses an INPUT statement to accept a value from the userM1
  • (a) uses a loop that repeats while/until the value is out of range, e.g. REPEAT ... UNTILM1
  • (a) correct condition combining both bounds using an appropriate logical operator, e.g. num ≥ 1 AND num ≤ 10M1
  • (a) outputs 'Valid' once the loop ends (any correct logic; ignore minor syntax errors)A1
  • (a) Answer:
    REPEAT
        INPUT num
    UNTIL num >= 1 AND num <= 10
    OUTPUT "Valid"

Question 9

  • (a) the data/array must already be sorted (into ascending or descending order) (oe)B1
  • (a) Answer: The array must be sorted (in ascending or descending order).
  • (b) step 1: lower=0, upper=9, mid=4, nums[4]=27, 41>27 so search upper half (lower<-5)B1
  • (b) step 2: lower=5, upper=9, mid=7, nums[7]=48, 41<48 so search lower half (upper<-6)B1
  • (b) step 3: lower=5, upper=6, mid=5, nums[5]=35, 41>35 so search upper half (lower<-6)B1
  • (b) step 4: lower=6, upper=6, mid=6, nums[6]=41, value foundB1
  • (b) all four steps correct and consistent with each other (cao)B1
  • (b) Answer: Step1: mid=4 (27), search upper. Step2: mid=7 (48), search lower. Step3: mid=5 (35), search upper. Step4: mid=6 (41), found at index 6.
  • (c) 4 comparisons were made (ft from part b)B1
  • (c) binary search eliminates half of the remaining items at each step, whereas a linear search worst case would need to check all 10 items one at a time (oe)B1
  • (c) Answer: 4 comparisons; binary search halves the remaining data each time, so it needs far fewer comparisons than the worst-case 10 needed by a linear search.

Question 10

  • (a) insert 2: [2, 5, 9, 1, 6]B1
  • (a) insert 9: [2, 5, 9, 1, 6] (unchanged, as 9 is already greater than 5)B1
  • (a) insert 1: [1, 2, 5, 9, 6]B1
  • (a) insert 6: [1, 2, 5, 6, 9] (cao)B1
  • (a) Answer: [2,5,9,1,6] -> [2,5,9,1,6] -> [1,2,5,9,6] -> [1,2,5,6,9]
  • (b) it sorts the data within the original data structure/array, without needing a significant amount of additional memory/another array (oe)B1
  • (b) Answer: An in-place algorithm sorts the data within its original array, without needing extra memory for a separate data structure.

Question 11

  • (a) the list is repeatedly split in half (divided) until each sub-list contains only one item (oe)B1
  • (a) a sub-list containing a single item is considered already sorted (oe)B1
  • (a) adjacent sub-lists are then merged back together, comparing the front item of each sub-list (oe)B1
  • (a) the smaller/next item is placed into the new merged list, and this repeats until all sub-lists have been merged into one fully sorted list (oe)B1
  • (a) Answer: The list is repeatedly divided in half until each sub-list has one item, then pairs of sub-lists are merged back together in order, comparing front items, until one fully sorted list remains.
  • (b) merge sort is more efficient/faster for large datasets, needing far fewer comparisons than bubble sort (oe)B1
  • (b) Answer: Merge sort is significantly more efficient than bubble sort for large datasets, requiring many fewer comparisons overall.

Question 12

  • (a) the condition i / 2 = 0 does not correctly test whether i is even (it should use MOD, e.g. i MOD 2 = 0)B1
  • (a) the algorithm adds 1 instead of adding the value of i itself (should be total <- total + i)B1
  • (a) Answer: Error 1: the condition should test i MOD 2 = 0, not i / 2 = 0. Error 2: the algorithm should add i (total <- total + i), not add 1.
  • (b) corrects the condition to test for an even number, e.g. i MOD 2 = 0M1
  • (b) corrects the addition to total <- total + i, giving a fully correct algorithm (any correct logic; ignore minor syntax errors)A1
  • (b) Answer:
    total <- 0
    FOR i <- 1 TO 20
        IF i MOD 2 = 0 THEN
            total <- total + i
        ENDIF
    NEXT i
    OUTPUT total

Question 13

  • (a) a linear search checks items one at a time, so its worst-case number of comparisons is directly proportional to the number of items, n (oe)B1
  • (a) a binary search halves the remaining data at each step, so its worst-case number of comparisons grows much more slowly, proportional to log2(n) (oe)B1
  • (a) as n grows very large, linear search's comparisons increase proportionally while binary search's increase only logarithmically, so the performance gap widens (oe)B1
  • (a) Answer: Linear search's worst-case comparisons grow directly with the size of the dataset, while binary search's grow only logarithmically (halving each time), so binary search becomes proportionally far faster as the dataset gets larger.
  • (b) recognises that 1024 = 210, or shows repeated halving of 1024 down to 1M1
  • (b) 10 or 11 (cao; 11 is exact when the last remaining item must also be compared, 10 counts the halving steps)A1
  • (b) Answer: 10 (11 is also correct)

Question 14

  • (a) i = 1: doubleIfEven returns 1, total = 1B1
  • (a) i = 2: doubleIfEven returns 4, total = 5B1
  • (a) i = 3: doubleIfEven returns 3, total = 8B1
  • (a) i = 4: doubleIfEven returns 8, total = 16 (cao)B1
  • (a) Answer: i=1: returns 1, total=1. i=2: returns 4, total=5. i=3: returns 3, total=8. i=4: returns 8, total=16.
  • (b) 16 (ft from part a, cao)B1
  • (b) Answer: 16

Question 15

  • Level 3 A detailed, coherent discussion that accurately describes how at least two of the algorithms work and links this to their efficiency. The nearly-sorted nature of the data is used to justify a clear, well-reasoned recommendation. Technical terminology is used accurately throughout.5-6
  • Level 2 Some relevant discussion of how the algorithms work, with limited or partial reference to efficiency or to the nearly-sorted nature of the data. A conclusion is given but is only partially justified. Technical terminology is used with some inaccuracy.3-4
  • Level 1 Basic, isolated statements are made about one or more of the algorithms, with little or no linking between ideas. Little or no reference to efficiency or to the nearly-sorted data. Conclusion, if present, is unjustified.1-2
  • Level 0 No creditable content.0
  • Indicative content:
    • Bubble sort repeatedly compares and swaps adjacent items across multiple passes; it is inefficient (many comparisons/swaps, roughly proportional to n^2) for a list of 5000 records, even if nearly sorted, because standard versions still make many passes.
    • Insertion sort builds up a sorted list by taking each item and inserting it into its correct position among the items already sorted; on data that is already nearly sorted, very few shifts are needed for each item, so insertion sort performs close to its best case and can be very efficient here.
    • Merge sort divides the list repeatedly and then merges the sorted sub-lists back together; it is consistently efficient (proportional to n log n) regardless of the initial order of the data, but requires extra memory for the sub-lists and is more complex to implement than the other two.
    • A well-justified conclusion could recommend insertion sort, because the nearly-sorted nature of the data plays to its strength of few shifts, or merge sort, because it guarantees good performance for a large dataset of 5000 records regardless of order; either conclusion should be credited if it is properly justified with reference to the scenario.

Question 16

  • (a) the algorithm that creates a new array (e.g. merge sort) is likely to use more memoryB1
  • (a) because it needs additional storage for the new array as well as the original, whereas an in-place algorithm reuses the original array's memory (oe)B1
  • (a) Answer: The algorithm that creates a new array uses more memory, because it needs space for both the new array and the original, whereas an in-place algorithm reuses the same memory throughout.

Mark your answers

Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.

Question 1

3 marks
Did your answer earn the marks?

Question 2

4 marks
Did your answer earn the marks?

Question 3

5 marks
Did your answer earn the marks?

Question 4

4 marks
Did your answer earn the marks?

Question 5

4 marks
Did your answer earn the marks?

Question 6

4 marks
Did your answer earn the marks?

Question 7

5 marks
Did your answer earn the marks?

Question 8

4 marks
Did your answer earn the marks?

Question 9

8 marks
Did your answer earn the marks?

Question 10

5 marks
Did your answer earn the marks?

Question 11

5 marks
Did your answer earn the marks?

Question 12

4 marks
Did your answer earn the marks?

Question 13

5 marks
Did your answer earn the marks?

Question 14

5 marks
Did your answer earn the marks?

Question 15

6 marks
Did your answer earn the marks?

Question 16

2 marks
Did your answer earn the marks?
Mark my answers

Keep going

Worksheets are written for Revision Library and come with a full mark scheme; a few English packs quote an out-of-copyright text, and name it on the page. Exam board names and specification codes say which qualification a pack suits: we are not affiliated with, endorsed by or approved by any exam board, and no past-paper question is reproduced here. Rights queries: hello@revisionlibrary.co.uk