2.3.1 Algorithms Exam Questions
Paper 2 · Algorithms & Programming · 17 past paper questions · 60 marks
Exam questions for 2.3.1 Algorithms
17 OCR past paper questions (60 marks) with mark schemes
Answer each question, reveal the mark scheme, then award yourself marks. Scores and answers are saved in this browser so you can see which topics need more work.
Download Questions & Mark Scheme (PDF)Past paper questions
- Question 1H446/02 · June 20243 marks
The following strings are stored in an array. Explain how a linear search would search the array for the index that stores "clouds".
"rainbow" "moon" "sun" "stars" "clouds" "tornado" Show mark scheme
Start at the first element (index 0) / Compare each element with 'clouds' / Move to the next element if not found / Continue until found or end of array reached / Return the index when found (3 marks)Mark yourself: how many marks did you get?/ 3 - Question 2H446/02 · June 20241 mark
State why a binary search cannot be used on an unsorted array.
Show mark scheme
The data is not sorted / Binary search requires sorted data / Cannot determine which half to search (1 mark)Mark yourself: how many marks did you get?/ 1 - Question 3H446/02 · June 20245 marks
Show how an insertion sort will sort the given data into ascending alphabetical order: rainbow, moon, sun, stars, clouds, tornado
Show mark scheme
Pass 1: moon, rainbow, sun, stars, clouds, tornado Pass 2: moon, rainbow, sun, stars, clouds, tornado Pass 3: moon, rainbow, stars, sun, clouds, tornado Pass 4: clouds, moon, rainbow, stars, sun, tornado Pass 5: clouds, moon, rainbow, stars, sun, tornado (5 marks - 1 per correct pass)Mark yourself: how many marks did you get?/ 5 - Question 4H446/029 marks
Compare the use of three algorithms with different Big O complexities. Include: meaning of constant, logarithmic, linear and exponential complexity, how each scales, which is most suitable for data ranging from 2 to 2 billion items.
Show mark scheme
Levels of response (9 marks) Constant O(1): Same time regardless of input Logarithmic O(log n): Doubles input = one more step Linear O(n): Time proportional to input Exponential O(2^n): Doubles with each additional input Algorithm 3 (Log time, Log space) best for large datasets as it scales wellMark yourself: how many marks did you get?/ 9 - Question 5H446/025 marks
Describe how a merge sort works.
Show mark scheme
Divide the list into two halves / Recursively divide until single elements / Compare elements and merge in order / Continue merging sublists / Until one sorted list remains (5 marks - 1 per point)Mark yourself: how many marks did you get?/ 5 - Question 6H446/02 · June 20232 marks
Give one benefit and one drawback of using a merge sort instead of a bubble sort.
Show mark scheme
Benefit: More efficient O(n log n) vs O(n²) / Better for large datasets / Consistent performance Drawback: Requires additional memory / More complex to implement / Overkill for small lists (2 marks)Mark yourself: how many marks did you get?/ 2 - Question 7H446/02 · June 20232 marks
Give two characteristics of a tree data structure.
Show mark scheme
Has a root node / Nodes connected by edges / Hierarchical structure / No cycles / Each node has at most one parent / Nodes can have children (2 marks)Mark yourself: how many marks did you get?/ 2 - Question 8H446/02 · June 20234 marks
Draw the binary search tree when the data 22, 13, 5, 36, 55, 14, 8 is entered in the order given.
Show mark scheme
Root: 22 Left subtree: 13, then 5 (left of 13), 14 (right of 13), 8 (right of 5) Right subtree: 36, then 55 (right of 36) (4 marks - correct structure and placement)Mark yourself: how many marks did you get?/ 4 - Question 9H446/02 · June 20232 marks
Describe how a leaf node is deleted from a binary search tree.
Show mark scheme
Find the node to delete / Update parent's pointer to null / The node is removed from the tree / No restructuring needed for leaf nodes (2 marks)Mark yourself: how many marks did you get?/ 2 - Question 10H446/02 · June 20234 marks
Describe how a binary search tree can be searched for a value.
Show mark scheme
Start at root node / Compare target with current node / If less, go to left child / If greater, go to right child / If equal, found / If null reached, not in tree (4 marks)Mark yourself: how many marks did you get?/ 4 - Question 11H446/02 · June 20234 marks
Identify the order that the nodes will be visited in a depth-first (post-order) traversal of this binary search tree.
Show mark scheme
A, F, C, L, T, P, H 1 mark for visiting A first 1 mark for then visiting F, C 1 mark for then visiting L, T, P 1 mark for visiting H last (4 marks)Mark yourself: how many marks did you get?/ 4 - Question 12H446/02 · June 20232 marks
Explain how backtracking is used in depth-first (post-order) traversals.
Show mark scheme
After visiting a subtree, return to parent node / Continue with unvisited subtrees / Uses stack to remember path / Allows exploration of all branches (2 marks)Mark yourself: how many marks did you get?/ 2 - Question 13H446/02 · June 20236 marks
A graph is a type of data structure. An example graph is shown in Fig. 1. Show how Dijkstra's algorithm can be used on the graph shown in Fig. 1 to find the shortest path from start node A to end node G. You must state the nodes on the final path and the distance of this path. Show your working.
Fig. 1 Show mark scheme
1 mark for the final path: A, D, G 1 mark for the final distance: 14 1 mark for each section of working shown, or equivalent: A; then B, C and D; then E and F; then G. For the mark for G there must be a clear indication that G reached from E (19) is overwritten by G reached from D (14). Nodes should appear in alphabetical order if they are added as the algorithm progresses, but allow other orderings. Allow an equivalent textual description. (6 marks)Node Distance travelled Previous node A 0 - B 5 A C 2 A D 10 A E 7 B F 15 E G 19, then 14 E, then D Mark yourself: how many marks did you get?/ 6 - Question 14H446/02 · June 20232 marks
A program stores data in a linked list. The current contents of the linked list are shown in Fig. 3, along with the linked list pointers. State the purpose of headPointer and freeListPointer in the linked list shown in Fig. 3.
headPointer 1 freeListPointer 4 location data pointer 0 "blue" 6 1 "red" 0 2 "green" 8 3 "orange" NULL 4 5 5 7 6 "grey" 2 7 9 8 "purple" 3 9 NULL Fig. 3 Show mark scheme
headPointer: Points to the first item in the list / Starting point for traversal freeListPointer: Points to the first available/empty location / Where new items can be added (2 marks)Mark yourself: how many marks did you get?/ 2 - Question 15H446/02 · June 20231 mark
A program stores data in a linked list. The current contents of the linked list are shown in Fig. 3, along with the linked list pointers. State the meaning of the pointers with the value NULL in the linked list shown in Fig. 3.
headPointer 1 freeListPointer 4 location data pointer 0 "blue" 6 1 "red" 0 2 "green" 8 3 "orange" NULL 4 5 5 7 6 "grey" 2 7 9 8 "purple" 3 9 NULL Fig. 3 Show mark scheme
Indicates end of list / No more items to follow / Pointer doesn't point to anything (1 mark)Mark yourself: how many marks did you get?/ 1 - Question 16H446/02 · June 20234 marks
Describe how a new item is added to a linked list.
Show mark scheme
Find the free location using freeListPointer / Store the new data there / Update the new node's pointer / Update the previous node's pointer / Update freeListPointer to next free space (4 marks)Mark yourself: how many marks did you get?/ 4 - Question 17H446/024 marks
A linked list is stored in an array called linkedList. Each element has a data field and a pointer field, headPointer holds the index of the first node, and a pointer of NULL marks the end of the list. Write a pseudocode function findNode(toFind) that returns the position of the first node whose data is equal to toFind, or -1 if it is not in the list.
Show mark scheme
currentNode = headPointer while(currentNode != NULL) if linkedList[currentNode].data == toFind then return currentNode else currentNode = linkedList[currentNode].pointer return -1 (4 marks - initialization, loop, comparison, pointer update)Mark yourself: how many marks did you get?/ 4
- 1Big O: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) - know examples
- 2Binary search: Requires sorted data; O(log n); Trace with low/high/mid
- 3Sorting: Bubble/Insertion O(n²), Merge/Quick O(n log n)
- 4A* algorithm: f(n) = g(n) + h(n); g=actual distance, h=heuristic
- •Practice answering questions under timed conditions
- •Check your answers against the mark scheme carefully
- •Focus on understanding the marking points, not just memorising answers
- •Review past paper questions from multiple years to spot patterns