6 exam-style questions with full mark schemes and model answers. Write your own answer and the AI examiner marks it against the mark scheme.
Learn this properly: What is an AlgorithmA library app stores the 5-digit membership numbers of its members in a list. A programmer must decide between a linear search and a binary search to find whether a particular membership number is in the list.
Discuss the advantages and disadvantages of each search algorithm for this task, and recommend which one the programmer should use if the membership numbers are stored in ascending order and the list is very large. (6 marks)
The numbers below are to be sorted into ascending order using a bubble sort, which compares adjacent pairs and swaps them if the left value is larger.
[8, 3, 6, 2]
(a) Show the state of the list after the first complete pass of the bubble sort. Write down each adjacent comparison and whether a swap happens. (3 marks)
(b) State how the algorithm knows it has finished (i.e. that the list is fully sorted). (1 mark)
A binary search is used to look for the value 40 in this sorted list. The first index is 0.
[3, 11, 18, 26, 33, 40, 51, 67]
The algorithm uses mid = (low + high) DIV 2, where DIV is integer division (it rounds down).
Show each step of the binary search until the value 40 is found. For each step give low, high, mid and the value at mid, and state how many comparisons with the target were made in total. (3 marks)
Two key techniques used when designing a solution to a large problem are decomposition and abstraction.
A team is designing a quiz app for a school. The app must let a teacher set questions, let pupils answer them, mark the answers, and display a leaderboard.
(a) State what is meant by decomposition, and give one example of how the quiz-app problem could be decomposed. (2 marks)
(b) State what is meant by abstraction. (1 mark)
A programmer compares the efficiency of linear search and binary search by counting the maximum number of comparisons needed.
A sorted list contains 64 items.
(a) State the maximum number of comparisons a linear search could make on this list. (1 mark)
(b) State the maximum number of comparisons a binary search could make on this list, and briefly explain your answer. (1 mark)
An algorithm can be represented as a flowchart using standard symbols.
Name the flowchart symbol (its shape) that is used to represent a decision. (1 mark)