AQA A Level · Computer Science 7517

Searching algorithms: Practice Questions

5 multiple-choice questions marked as you go, and 5 written questions with worked solutions. All on Searching algorithms.

10 questions24 marksFree, no account

Question 1

1 mark

A linear search is performed on an array of 1,000 elements to find a value that is not present in the data. How many comparisons will the algorithm perform?

Question 2

1 mark

An array contains 2,048 sorted integers. In the worst-case scenario, how many comparisons will a binary search algorithm perform to determine if a value is in the array?

Question 3

1 mark

A programmer is choosing between a Binary Search and a Binary Tree Search for a system where the data is frequently updated with new items. What is a key disadvantage of the Binary Tree Search compared to the standard Binary Search in this specific context?

Question 4

1 mark

A programmer is searching for a value in a sorted array using the binary search algorithm. If the array contains 1,000,000 elements, what is the maximum number of comparisons required to find the target or determine it is not present?

Question 5

1 mark

A binary search tree (BST) contains \(n\) nodes. In the worst-case scenario, what is the time complexity of searching for a specific key if the tree is not balanced?

Question 6

2 marks

An algorithm is designed to find the shortest path between two points on a map represented as an unweighted graph. Identify which graph-traversal algorithm is most appropriate and state its Big-O time complexity if the graph has \(V\) vertices and \(E\) edges.

Write your answer out first, then check it against the worked solution.

Question 7

3 marks

A programmer needs to locate a specific integer in a sorted array containing 1,024 elements. Explain why a binary search is significantly more efficient than a linear search in the worst-case scenario for this dataset.

Write your answer out first, then check it against the worked solution.

Question 8

5 marks

A binary search tree (BST) is used to store \(n\) elements. Explain the conditions under which the search time complexity would degrade from \(O(\log n)\) to \(O(n)\).

Write your answer out first, then check it against the worked solution.

Question 9

3 marks

Consider the following list of sorted names: [Alice, Bob, Charlie, David, Edward, Fiona, George].

(a) Trace the steps of a binary search to find the name 'Fiona'. Identify the middle element chosen at each step.
(b) What is the maximum number of comparisons needed for a binary search on a list of 128 elements?

Write your answer out first, then check it against the worked solution.

Question 10

6 marks

Evaluate the efficiency of searching in a Binary Search Tree (BST) compared to a Binary Search on a sorted array.

(a) Under what condition does the time complexity of a BST search degrade from \(O(\log n)\) to \(O(n)\)?
(b) Describe how tree-traversal can be used to re-balance a tree to maintain \(O(\log n)\) performance.

Write your answer out first, then check it against the worked solution.

* The content provided by thinka is generated by AI and may not always be accurate or up-to-date. Please use it as a supplementary resource and verify with official materials.

You've seen the model answer. Now get yours marked.

This page can show you how a good answer looks. It cannot tell you what your answer was missing. thinka marks your written work against the real mark scheme in about 15 seconds.

Get My Answers Marked Back to the notes

Want more questions like these? Get a fresh set on this topic, graded as you go.