**15.1** Which of the following best explains why the recursive Fibonacci function we wrote takes a really long time to complete when \( n \) is 40 or larger?

A) Recursive functions always take a really long time to finish.
B) It was recalculating the same values many times while running.
C) Fibonacci numbers just take a long time to figure out.
D) Because it was written in C++ - Java would have run faster.

---

**15.2** Which of the following best describes the operation of the quick sort algorithm?

A) Find the largest item in the array and move it to the end; repeat until the entire array is sorted.
B) Iterate through the array, swapping adjacent pairs of items that are out of order, continue until the entire array is sorted.
C) If the array has more than 1 item, split it in half, sort each half, and put the two halves together into one sorted array.
D) If the array has more than two items, choose an item and split the array into two lists: one that has all items smaller than that item, and one that has all items that are larger. Sort the two lists, and put everything back together into a sorted list.
E) None of these describe the operation of merge sort.

---

**15.3** Which of the following correctly declares x to be a pointer to a string?

A) string x;
B) string* x;
C) pointer to string x;
D) *string x;
E) x;

---

**15.4** Which of the following best describes the difference between an abstract data type and a data structure?

A) An abstract data type is written into a class, while a data structure is written in a program file.
B) A data structure is a description of the data elements and operations for a class, while an abstract data type is the implementation of a data structure.
C) An abstract data type is a description of the data elements and operations for a class, while a data structure is the implementation of an abstract data type.
D) An abstract data structure is written in Java, while a data structure is written in C++.

---

**15.5** Which of the following best describes the operation of the merge sort algorithm?

A) Find the largest item in the array and move it to the end; repeat until the entire array is sorted.
B) Iterate through the array, swapping adjacent pairs of items that are out of order; continue until the entire array is sorted.
C) If the array has more than 1 item, split it in half, sort each half, and put the two halves together into one sorted array.
D) If the array has more than two items, choose an item and split the array into two lists: one that has all items smaller than that item, and one that has all items that are larger. Sort the two lists, and put everything back together into a sorted list.
E) None of these describe the operation of merge sort.