AQA A Level Computer Science 7517 : 3 - Fundamentals of Algorithms Exam Questions with 100% Correct Answers

Binary Search Tree Correct Answer A O(log(n)) algorithm to search a binary tree for a particular item by traversing the tree in the right direction until the item is found. Binary Search Correct Answer A O(log(n)) algorithm to search a sorted list for a particular item by repeatedly halving the sublist which could contain the item. Breadth-First Traversal Correct Answer A method of traversing a graph by using a queue to visit all the neighbours of the current node before doing the same to each of the neighbours until the entire graph has been explored. Bubble Sort Correct Answer A O(n2) sorting algorithm that iterates through a list, comparing each element to its successor and swapping elements if the successor is greater than the current element. This is repeated until no more swaps can be made. Depth-First Traversal Correct Answer A method of traversing a graph by using a stack to travel as far along one route as possible and then backtracking and doing the same for the remaining routes until the entire graph has been explored. Dijkstra's Shortest Path Algorithm Correct Answer An algorithm to find the shortest path between two nodes on a graph by using a priority queue to keep track of the shortest distance (cost) to each node from the starting node until the destination node is found. In-Order Traversal Correct Answer A traversal in the order: traverse the left subtree, visit/pop the node then traverse the right subtree. Infix Notation Correct Answer A mathematical notation where the operator is written between the operands. Linear Search Correct Answer A O(n) algorithm to search a list for a particular item by iterating through the list and checking each element until the required item is located, or the end of the list is reached. Merge Sort Correct Answer A O(n log(n)) divide-and-conquer sorting algorithm that recursively halves the list into sublists until all sublists are of length 1. The sublists are then merged back together in such a wa