Exam practice
Every question from the end of every unit, with hints and answers to open. After you check an answer, mark how you did, and come back to the ones you didn’t get.
12 questions
Unit 3 · Algorithms: Searching and Sorting
Draw the flowchart symbols for: i. start or stop ii. a process iii. input or output iv. a decision v. a procedure vi. a connector. Say what each is used for.
Answer
- i.Start or stop: a rounded box (an oval, or a rectangle with round ends). Where the algorithm begins and ends.
- ii.Process: a rectangle. A step that does something, such as setting or working out a value:
total = total + marks. - iii.Input or output: a parallelogram. Asking the user for a value, or showing one:
INPUT marks,OUTPUT total. - iv.Decision: a diamond. A question with a yes-or-no answer, with two arrows out, labeled Yes and No:
marks ≥ 35? - v.Procedure: a rectangle with a second line down each side. A job that has its own flowchart elsewhere:
SORT the list. - vi.Connector: a small circle with a letter in it. It joins two parts of a flowchart, so a long arrow isn’t needed: an arrow into circle A carries on from the other circle A.
Write pseudocode for an algorithm that asks for 10 marks, one at a time, and outputs how many of them are 35 or more. Then draw its flowchart.
Answer
Pseudocode
SET passed TO 0FOR i FROM 1 TO 10 INPUT marks IF marks ≥ 35 THEN SET passed TO passed + 1 END IFEND FOROUTPUT passedThe flowchart: Start → process passed = 0, i = 1 → decision i ≤ 10?. Yes → input INPUT marks → decision marks ≥ 35?; Yes → process passed = passed + 1 → process i = i + 1; No → straight to i = i + 1. From i = i + 1 an arrow goes back up to i ≤ 10?. When i ≤ 10? is No → output OUTPUT passed → Stop. (In a flowchart a FOR loop is drawn with its counter: set it before the loop, test it in a decision, and add 1 at the end of each round.)
The list is 4, 9, 13, 18, 25, 31, 36, 42, 50. Show the steps of a linear search and of a binary search for 36, with low, high and middle for the binary search. How many comparisons does each make?
Answer
Linear search compares 4, 9, 13, 18, 25, 31, 36: found at position 6 after 7 comparisons.
Binary search:
| Look | low | high | middle | Number there | So |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 25 | smaller than 36: low = 5 |
| 2 | 5 | 8 | 6 | 36 | equal: found at position 6 |
2 comparisons.
Using the same list, show the binary search for 20, which isn’t in it. How does the algorithm know when to stop?
Answer
| Look | low | high | middle | Number there | So |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 25 | bigger than 20: high = 3 |
| 2 | 0 | 3 | 1 | 9 | smaller: low = 2 |
| 3 | 2 | 3 | 2 | 13 | smaller: low = 3 |
| 4 | 3 | 3 | 3 | 18 | smaller: low = 4 |
Now low is 4 and high is 3: low has passed high, so no positions are left where 20 could be. The loop’s condition, low <= high, is false, and the algorithm says 20 is not in the list, after 4 comparisons.
Explain why binary search needs a sorted list. Give an example of a list and a target for which it gives the wrong answer when the list isn’t sorted.
Answer
At each look, binary search throws away half of what is left. It may do that only because the list is sorted: if the middle item is smaller than the target, everything to its left is smaller still, so the target can’t be there. In a list that isn’t sorted, the target may be in the half that is thrown away.
Example: the list 52, 38, 71, 45, 60, 12, 85 and the target 60. The middle (position 3) is 45, smaller than 60, so the search looks only to the right: 60, 12, 85. The middle of those is 12, smaller than 60, so it looks only at 85, which is bigger: nothing is left, and it says 60 is not in the list, although it is. (Exactly which items are missed depends on the list; this one is the program in the careful box.)
Sort 29, 14, 35, 8 from smallest to biggest with bubble sort. Show the list after each pass, and count the comparisons and swaps.
Answer
- Pass 1: 29, 14 swap → 14, 29, 35, 8; 29, 35 in order; 35, 8 swap → 14, 29, 8, 35.
- Pass 2: 14, 29 in order; 29, 8 swap → 14, 8, 29, 35; 29, 35 in order → 14, 8, 29, 35.
- Pass 3: 14, 8 swap → 8, 14, 29, 35; 14, 29 and 29, 35 in order → 8, 14, 29, 35.
- Pass 4: no swaps, so the list is sorted.
4 passes of 3 comparisons: 12 comparisons and 4 swaps. (The smallest, 8, moved only one place to the left in each pass, which is why it took so many passes.)
Sort the same list, 29, 14, 35, 8, with insertion sort. Show the list after each item is placed, count the comparisons and swaps, and compare with your answer to f.
Answer
| Item placed | Comparisons | List after it |
|---|---|---|
| 14 | 29 > 14: swap (front reached) | 14, 29, 35, 8 |
| 35 | 29 < 35: stop | 14, 29, 35, 8 |
| 8 | 35 > 8 swap; 29 > 8 swap; 14 > 8 swap (front reached) | 8, 14, 29, 35 |
1 + 1 + 3 = 5 comparisons and 4 swaps. Bubble sort made the same 4 swaps but 12 comparisons. Insertion sort moved 8 to the front in one go, while bubble sort moved it one place per pass.
Write the output of this program, and say what it does.
values = [6, 2, 9, 4]count = 0for i in range(len(values) - 1): if values[i] > values[i + 1]: count = count + 1print(count)Answer
Output
2It compares each pair of neighbors, as one pass of a bubble sort does, without swapping: 6 > 2 (count 1), 2 > 9 no, 9 > 4 (count 2). It counts how many pairs of neighbors are in the wrong order. If it printed 0, the list would be sorted: this is a quick way to check whether a list is in order.
A student’s linear search is meant to print where a name is, but for a list of 5 names it stops with IndexError: list index out of range. Find the mistake and correct it.
names = ["Asha", "Binod", "Chhiring", "Dipa", "Esha"]target = "Kopila"i = 0found = Falsewhile i <= len(names) and not found: if names[i] == target: found = True else: i = i + 1print(found)Answer
The condition on line 5 is i <= len(names), so the loop also goes round when i is 5. Positions run only from 0 to 4, so names[5] on line 6 is the IndexError. It happens only when the name isn’t in the list (Kopila isn’t): a found name stops the loop earlier, so ordinary tests would all pass. Correct line 5 to
while i < len(names) and not found:Now it prints False for Kopila. The edge test “a name not in the list” finds this bug.
Choose eight tests for a program that sorts a list of numbers: at least two ordinary, four edge and one wrong. Give each one’s expected result.
Answer
For example:
| Kind | Input | Expected |
|---|---|---|
| ordinary | 52, 38, 71, 45, 60 | 38, 45, 52, 60, 71 |
| ordinary | 8, 3, 5 | 3, 5, 8 |
| edge: already sorted | 1, 2, 3, 4 | 1, 2, 3, 4 (and no swaps) |
| edge: backwards | 9, 7, 5, 3 | 3, 5, 7, 9 |
| edge: one item | 45 | 45 |
| edge: no items | (an empty list) | an empty list, with no error |
| edge: two the same | 5, 2, 5, 1 | 1, 2, 5, 5 (both 5s kept) |
| wrong | [52, "thirty", 71] |
a message that every item must be a number, not a crash |
Edge tests are where most sorting bugs show: a loop that goes one position too far fails on every list, and one that stops too early may only fail on a backwards list.
Your school’s library has 4,000 books on a list sorted by title. Explain to a younger student, without using code, why finding a title with binary search needs at most 12 looks, and how many a linear search could need.
Answer
Open the list in the middle and read that title. If the one you want comes before it, you never need to look at the second half again; if it comes after, never at the first half. One look has thrown away about 2,000 titles. The next look, in the middle of the half that is left, throws away about 1,000 more, then 500, 250… Each look throws away the title looked at and half of the rest, so at the very most the titles left go 4,000 → 2,000 → 1,000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0: after 11 looks at most 1 title is left, and the 12th look checks it. (Put the other way: 12 looks can search up to 4,095 titles.) A linear search, starting at the top and reading every title, could need all 4,000 looks, if the book is last or isn’t there.
Bubble sort and insertion sort both sorted a list of 6 numbers and made 7 swaps. Bubble sort made 20 comparisons and insertion sort 11. Explain what a comparison and a swap are, why the number of swaps is the same, and which sort did less work.
Answer
A comparison is looking at two items to see which is bigger; a swap is changing two neighbors’ places. Both sorts swap only neighbors that are in the wrong order, and each such swap puts exactly one pair of numbers right, so both make one swap for every pair that started in the wrong order: 7 here. Insertion sort did less work: it made 9 fewer comparisons, because it stops moving each number as soon as it meets a smaller one, while bubble sort keeps comparing every pair of neighbors in every pass, including the passes over parts already in order.