Show the steps of a binary search for 40 in the list [3, 9, 14, 21, 27, 33, 40, 48, 52].
From Paper 2: Algorithms and programming
3(b)4 marks
Show each pass of an insertion sort on [5, 2, 8, 1, 9].
From Paper 2: Algorithms and programming
3(c)5 marks
Describe how merge sort works and state its time complexity.
From Paper 2: Algorithms and programming
3(d)4 marks
Explain the meaning of O(1), O(n), O(n²) and O(2ⁿ), giving an example of each.
From Paper 2: Algorithms and programming
3(e)4 marks
Explain how A* search differs from Dijkstra's algorithm.
From Paper 2: Algorithms and programming
3(f)6 marks
Write pseudocode for push(item) and pop() for a stack stored in an array of size 10 with a pointer top (initially −1), including checks for overflow and underflow.
From Paper 2: Algorithms and programming
3(g)5 marks
Describe how a new node is inserted into an ordered linked list.
From Paper 2: Algorithms and programming
3(h)4 marks
The values 50, 30, 70, 20, 40, 60, 80 are inserted into a binary search tree in that order. Describe where 65 would be inserted and why.
From Paper 2: Algorithms and programming
3(i)4 marks
A graph has edges A–B, A–C, B–D, C–D, C–E, D–F. Give the order of a breadth-first traversal from A (visit neighbours alphabetically) and name the data structure used.
From Paper 2: Algorithms and programming
4(c)10 marks
Write a function findSeats(row, n) that returns the index of the first seat of the first block of n adjacent free seats in the given row, or −1 if there is none.
From Paper 2: Algorithms and programming
4(f)9 marks
The chain wants to allocate seats so that groups are kept together and as few single seats as possible are left empty. Discuss how backtracking or heuristic methods could be used to solve this problem.
Score 0 / 59 · 0 of 11 marked
This paper is written by Plasmo in the style of the OCR A-Level Computer Science exam. It is not a past paper and is not produced or endorsed by the exam board.