495 Multiple Choice 1. Which algorithm requires time directly proportional to the size of the in- a) linear search b) binary search c) merge sort put? d) selection sort 2. Approximately how many iterations will binary search need to find a value in a list of 512 items? a) 512 b) 256 c) d) 3 3. Recursions on sequences often use this as a base case; a) b) 1 C) an empty sequence d) None 4. An infinite recursion will result in a) a program that "hangs" b) a broken computer c) a reboot d) a run-time exception 5. The recursive Fibonacci function is inefficient because a) it does many repeated computations b) recursion is inherently inefficient compared to iteration c) calculating Fibonacci numbers is intractable d) fibbing is morally wrong 6. Which is a quadratic time algorithm? a) linear search b) binary search c) Tower of Hanoi d) selection sort 7. The process of combining two sorted sequences is called a) sorting b) shuffling c) dovetailing d) merging 8. Recursion is related to the mathematical technique called a) looping b) sequencing c) induction d) contradiction 9. How of size 5? many steps would be needed to solve the Tower of Hanoi for a tower a) 5 b) 10 c) 25 d) 31 10. Which of the following is not true of the halting problem? a) It was studied by Alan Turing. b) It is harder than intractable. c) Someday a clever algorithm may be found to solve it. d) It involves a program that analyzes other programs