Searching And Sorting Arrays Test Bank Chapter 8

Starting Out with C++ from Control Structures to Objects, 9e (Gaddis)

Chapter 8 Searching and Sorting Arrays

TRUE/FALSE

1. The bubble sort is an easy way to arrange data in ascending order but it cannot arrange data in descending order.

2. The number of comparisons made by a binary search is expressed in powers of two.

3. On average, an item is just as likely to be found near the beginning of an array as near the end.

4. A linear search can only be implemented with integer values.

5. Before you can perform a selection sort, the data must be stored in ascending order.

6. Before you can perform a bubble sort, the data must be stored in descending order.

7. You are more likely to find an item by using a binary search than by using a linear search.

8. If you are using the bubble sort algorithm to sort an array in descending order, the smaller values move toward the end.

9. A selection sort and a binary search can be applied to STL vectors as well as arrays.

10. The linear search repeatedly divides the portion of an array being searched in half.

MULTIPLE CHOICE

1. A __________ algorithm is a method of locating a specific item of information in a larger collection of data.

2. The advantage of a linear search is its

3. A __________ search is more efficient than a __________ search.

4. A binary search begins with the __________ element of an array.

5. The __________ sort usually performs fewer exchanges than the __________ sort.

6. Array elements must __________ before a binary search can be performed.

7. Using a linear search to find a value that is stored in the last element of an array that contains 20,000 elements, __________ elements must be compared.

8. A(n) __________ search uses a loop to sequentially step through an array.

9. Data that is to be sorted in ascending order is ordered

10. Regardless of the algorithm being used, a search through an array is always performed

11. When an array is sorted from highest to lowest, it is said to be in

12. The __________ is adequate for searching through small arrays.

13. Algorithms used to arrange random data in some order are __________ algorithms.

14. Assume you have two integer variables, num1 and num2. Which of the following is the correct way to swap the values in these two variables?

15. The following function should swap the values contained in two integer variables, num1 and num2. What, if anything, is wrong with this function?

void swap(int num1, int num2)

{

int temp = num2;

num2 = num1;

num1 = temp;

}

16. The following is the pseudocode for which type of algorithm?

Set found to false

Set position to -1

Set index to 0

While found is false and index < number of elements

If list[index] is equal to search value

found = true

position = index

End If

Add 1 to index

End While

Return position

17. The following is the pseudocode for which type of algorithm?

Set first to 0

Set last to the last subscript in the array

Set found to false

Set position to -1

While found is not true and first is less than or equal to last

Set middle to the subscript halfway between array[first] and array[last]

If array[middle] equals the desired value

Set found to true

Set position to middle

Else If array[middle] is greater than the desired value

Set last to middle - 1

Else

Set first to middle + 1

End If

End While

Return position

18. The following is the pseudocode for which type of algorithm?

For maxElement = each subscript in the array, from the last to the first

For index = 0 To maxElement - 1

If array[index] > array[index + 1]

swap array[index] with array[index + 1]

End If

End For

End For

19. The following is the pseudocode for which type of algorithm?

For start = each array subscript, from the first to the next-to-last

minIndex = start

minValue = array[start]

For index = start + 1 To size - 1

If array[index] < minValue

minValue = array[index]

minIndex = index

End If

End For

swap array[minIndex] with array[start]

End For

20. What is the output after the following code executes?

int numerator = 5;

int denominator = 25;

int temp = 0;

temp = numerator;

numerator = denominator;

denominator = temp;

cout << numerator << "/" << denominator << " = " <<

(numerator/denominator) << endl;