Programming algorithms practice questions.

A program must find one surname in an array of 1000 surnames. Which condition has to hold before a binary search may be used on that array?

• The array must hold no repeated surnames
• The array must already be sorted on the surname
• The array must hold fewer items than a collection
• The array must be indexed from 1 rather than 0

Answer: The array must already be sorted on the surname

A binary search decides after every comparison which half of the array can be thrown away, and that decision is only valid if the values are in order. Repeated values, the index base and the size of the array make no difference to whether the method works.

A sorted array holds 16 values. What is the greatest number of values a binary search has to examine before it can decide whether a given value is present?

• 4
• 8
• 5
• 16

Answer: 5

Each comparison at most halves the part still to be searched: 16 to 8 to 4 to 2 to 1, and the single remaining value must itself be compared, giving five examinations. Stopping at four counts the halvings and forgets that the last survivor still has to be checked.

Which statement correctly distinguishes a selection sort from a bubble sort?

• A selection sort makes at most one exchange per pass
• A selection sort never compares two neighbouring items
• A selection sort works only on data that is already sorted
• A selection sort needs a second array to hold the result

Answer: A selection sort makes at most one exchange per pass

A selection sort searches the unsorted part for the smallest remaining item and swaps it into place once per pass, while a bubble sort may swap many times in the same pass. Both work in the original array and both compare pairs, so the other statements describe neither method.

A list of readings arrives almost in ascending order, with only two readings out of place. Which behaviour of an insertion sort makes it a good choice here?

• It rereads the whole list once for every item it places
• It always makes the same number of exchanges for a given length
• It splits the list in half before it starts placing items
• It stops moving an item as soon as it meets a smaller one

Answer: It stops moving an item as soon as it meets a smaller one

An insertion sort walks each new item backwards only until it meets a smaller item, so on almost ordered data nearly every item stops immediately and hardly anything moves. It is the selection sort whose comparison count is fixed by the length alone.

A recursive subprogram is written without a base case. What happens when it is called?

• It calls itself again and again until the call stack is exhausted
• It returns the value zero because no result was ever assigned
• It runs exactly once and then returns to the calling statement
• It is rejected before it runs because the definition is incomplete

Answer: It calls itself again and again until the call stack is exhausted

The base case is the only thing that stops a recursive definition, so without it every call makes another call and the memory holding the unfinished calls fills up. The definition is syntactically fine, which is why the problem only shows itself at run time.

A linear search runs over an array that happens to be sorted in ascending order. When may the search stop early even though the target has not been found?

• As soon as two consecutive equal values are reached
• As soon as a value greater than the target is reached
• As soon as the middle element of the whole array is reached
• As soon as half of the elements have been examined

Answer: As soon as a value greater than the target is reached

Once a larger value appears, every remaining value is at least as large, so the target cannot be further on and the search can report failure immediately. This shortcut is only available because the data are sorted, which is also the condition that makes a binary search possible and far faster.