Algorithms - Worksheets, Questions and Revision
16 original exam-style questions - 8 pages of questions with a full mark scheme - free printable PDF.
Algorithms revision guideMore GCSE Computer Science practiceMock exams
This topic is chapter 9 of GCSE Computer Science Topic Workbook 1 and chapter 9 of GCSE Computer Science 10-Minute Tests.
2.1 Algorithms
total = 0
for i = 1 to 5
total = total + i
next i
print(total)
total <- 0
FOR i <- 1 TO 20
IF i / 2 = 0 THEN
total <- total + 1
ENDIF
NEXT i
OUTPUT totalFUNCTION 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 totalQuestion 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.