Searching and Sorting

Sample questions

Real questions from this chapter, as the app sets them. Tap Answer to see the answer and working.

Section A · multiple choice

1. 1.

   Binary search can be used only when the list is:

   1. made of even numbers
   2. unsorted
   3. short
   4. sorted

   Answer

   (d) sorted

2. 2.

   Linear search checks the items one by one from the left. How many items are checked when searching 77, 80, 72, 54, 74, 71, 94, 63, 97 for 58?

   1. 5
   2. 8
   3. 9
   4. 10

   Answer

   (c) 9

   58 is not there, so all 9 are checked

3. 3.

   Binary search: number the positions 1, 2, 3, …; check the middle position (the whole part of (low + high) ÷ 2); if the target is smaller, search the left half, if larger, the right half. How many items are checked when searching 2, 13, 27, 37, 41, 51, 58, 63, 87, 88 for 51?

   1. 4
   2. 3
   3. 2
   4. 6

   Answer

   (b) 3

   checked: 41, 63, 51

Section B · short answer

1. 4.

   Why must a list be sorted before binary search?

   Answer

   Binary search throws away the half that cannot hold the target; that only works if smaller items are on one side and larger on the other.

2. 5.

   Bubble sort compares neighbours from left to right in each pass, swapping any pair in the wrong order. Write 31, 57, 15, 55, 8, 41 after 3 passes, separated by commas.

   Answer

   15, 8, 31, 41, 55, 57

   swaps per pass: 4, 3, 1

Section C · long answer

1. 6.

   Explain binary search step by step for finding 23 in 4, 8, 15, 16, 23, 42, 50.

   Answer

   Middle (4th) is 16; 23 is larger, so search 23, 42, 50; middle is 42; 23 is smaller, so search 23; found in 3 checks.

Fresh sheets for your child

In the app, every Searching and Sorting sheet is new: the app remembers the questions your child has already had and leaves them out. Print the sheet as a PDF, or use notebook mode and write the answers in a notebook.

Coming soon for Android and iPhone.

More Class 9 Computational Thinking and AI