OCR A2 Computer Science Algorithms Quiz

What is the A* Algorithm?

• A sorting algorithm that iterates through a list to find the smallest element.

• A generalisation of Dijkstra's algorithm that approximately finds the shortest path between two nodes.

• A method of traversing a graph by using a stack to travel as far along one route as possible.

• An algorithm to search a list for a particular item by iterating through the list and checking each element.

What does Big O Notation represent?

• The average time an algorithm takes to complete on any input size.

• The exact number of operations an algorithm will perform.

• A way of classifying algorithms based on their complexity by setting an upper bound for the worst case space or time complexity.

• The best case scenario for the time complexity of an algorithm.

What is the time complexity of Binary Search?

• O(n)

• O(n^2)

• O(log(n))

• O(n log(n))

Which algorithm uses a queue to visit all the neighbours of the current node before exploring each of the neighbours' neighbours?

• Depth-First Traversal

• Binary Search

• Breadth-First Traversal

• Insertion Sort

What is the time complexity of Bubble Sort?

• O(n)

• O(n log(n))

• O(log(n))

• O(n^2)

How does Depth-First Traversal differ from Breadth-First Traversal?

• Depth-First Traversal uses a queue, while Breadth-First Traversal uses a stack.

• Depth-First Traversal uses a stack, while Breadth-First Traversal uses a queue.

• Depth-First Traversal is a sorting algorithm, while Breadth-First Traversal is a searching algorithm.

• Depth-First Traversal is a searching algorithm, while Breadth-First Traversal is a sorting algorithm.

What is the goal of Dijkstra's Shortest Path Algorithm?

• To sort a list by repeatedly halving the sublist.

• To search a list for a particular item by iterating through the list.

• To find the shortest path between two nodes on a graph using a priority queue.

• To divide a list into sorted and unsorted sections and place elements in the correct position.

What is the time complexity of Insertion Sort?

• O(n)

• O(n^2)

• O(log(n))

• O(n log(n))

Which algorithm is described as a divide-and-conquer sorting algorithm that recursively halves the list into sublists?

• Merge Sort

• Linear Search

• Bubble Sort

• Binary Search

What does O(1) complexity indicate about an algorithm's execution time or required memory space?

• It grows exponentially with input size.

• It is directly proportional to the size of its input.

• It is constant, regardless of the input size.

• It grows logarithmically with input size.