A-Level Computer Science Practice: Algorithms

What precondition must be satisfied before performing a binary search on a list?

What is the maximum number of comparisons binary search needs to find an element in a sorted array of 1000 elements?

An interpolation search is performed on a sorted array of uniformly distributed integers: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]. The target value is 60. What is the position probed first?

During one pass of bubble sort on the array [5, 3, 8, 1, 4], what is the state after the first complete pass?

Which sorting algorithm has O(n log n) worst-case time complexity and is a stable sort?

A quick sort partition on [7, 2, 9, 4, 3, 8] uses the first element (7) as pivot. After partitioning, what are the left partition, pivot position, and right partition?

What is the key difference between BFS and DFS in terms of the data structure used and exploration order?

For a graph with V vertices and E edges, what is the space complexity of an adjacency matrix versus an adjacency list?

Which algorithm is used to find a minimum spanning tree (MST) and what principle does it follow?

Which of the following correctly orders time complexities from most efficient to least efficient?

An algorithm has time complexity O(n^2). If the input size doubles from n to 2n, approximately how much longer will the algorithm take?

What is the difference between Big-O, Big-Omega, and Big-Theta notation?

Merge sort is an example of which algorithm design paradigm?

Which statement correctly describes a greedy algorithm and its limitations?

What distinguishes dynamic programming from plain recursion, and what type of problem does it solve?

What is the output of this recursive function when called with f(4)? FUNCTION f(n): IF n == 0 THEN RETURN 1 ELSE RETURN n _ f(n - 1)

What is the time complexity of the recursive Fibonacci function fib(n) that returns fib(n-1) + fib(n-2) with base cases fib(0)=0, fib(1)=1?

A recursive function to compute the sum of array elements is: sum(arr, n) = arr[n-1] + sum(arr, n-1), with base case sum(arr, 0) = 0. What is the space complexity of this function?