Test Bank Answers 5e - In Introduction To Sorting Ch.15

Chapter 15 - In Introduction to Sorting

True/False (12)

1. Sorting a chain of linked nodes is usually easier than sorting an array
2. Objects in an array to be sorted must be of the same class.
3. Exchanging two objects in an array requires the compareTo method.
4. The recursive selection sort performs the same operators as the iterative method.
5. Performance of the selection sort depends on how scrambled the data is before starting.
6. You cannot partition a chain of linked nodes.
7. Selection sort is efficient for large arrays.
8. Insertion sort is not efficient for large arrays.
9. Shell sort is based on insertion sort.
10. The final step of shell sort is a selection sort.
11. Implementing the insertion sort for an array of elements is generally difficult.
12. Implementing the insertion sort for a linked chain of nodes is generally difficult.

Short Answer (5)

1. Given the following array, show the array after 2 iterations of selection sort. Assume the array is to be sorted in ascending order.
   
   8 14 2 9 5 16 1

1 14 2 9 5 16 8
second iteration
1 2 14 9 5 16 8

1. Given the following array, show the array after 2 iterations of insertion sort. Assume the array is to be sorted in ascending order.
   
   14 8 2 9 5 16 1

8 14 2 9 5 16 1
second iteration
2 8 14 9 5 16 1

1. Given the following array of 5 elements, trace the selection sort algorithm one iteration at a time. Assume the array is to be sorted in ascending order.

24 7 3 18 5

3 7 24 18 5
3 5 24 18 7
3 5 7 18 24
3 5 7 18 24 (no swap necessary but the iteration happens)

1. Given the following array of 5 elements, trace the insertion sort algorithm one iteration at a time. Assume the array is to be sorted in ascending order.
   
   24 7 3 18 5

7 24 3 18 5
3 7 24 18 5
3 7 18 24 5
3 5 7 18 24

1. Why does repeatedly using even values for the spaces in shell sort not work as efficiently as always adjusting the space value to an odd number?

Multiple Choice (27) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. Arranging items into ascending or descending order is called
   1. sorting
   2. organizing
   3. arranging
   4. linking
2. Java sorting implementations sort objects that implement the _____ interface.
   1. Comparable
   2. Sortable
   3. Hierarchical
   4. All of the above
3. Selecting the smallest element of an array and swapping it with the first entry is an operation in which sorting method?
   1. selection sort
   2. insertion sort
   3. shell sort
   4. all of the above
4. Given the following array elements, what does the array look like after one iteration of selection sort, arranging items in ascending order?
   14 5 7 19 23 4 12 21
   1. 4 5 7 19 23 14 12 21
   2. 4 14 5 7 19 23 12 21
   3. 4 5 7 12 14 19 21 23
   4. 14 5 7 19 23 4 12 21
5. Given the following array elements, what does the array look like after two iterations of selection sort, arranging items in ascending order?
   92 42 73 19 86 33 7 60
   1. 7 19 73 42 86 33 92 60
   2. 7 19 92 42 73 86 33 60
   3. 7 19 42 73 86 33 92 60
   4. 92 42 73 19 86 33 7 60
6. What is the base case in the recursive selection sort method?
   1. the array has only one element
   2. the array is found to be sorted
   3. the array is empty
   4. there is no base case
7. What is the efficiency of the iterative selection sort method for an array of n items?
   1. O(n²)
   2. O(2ⁿ)
   3. O(n)
   4. O(n log n)
8. What is the efficiency of the recursive selection sort method for an array of n items?
   1. O(n²)
   2. O(2ⁿ)
   3. O(n)
   4. O(n log n)
9. The selection sort requires _____ comparisons for an array of n items.
   1. O(n²)
   2. O(2ⁿ)
   3. O(n)
   4. O(n log n)
10. The selection sort requires _____ swaps for an array of n items.
    1. O(n)
    2. O(n²)
    3. O(2ⁿ)
    4. O(n log n)
11. Dividing an array into parts is called
    1. partitioning
    2. dividing
    3. sorting
    4. separating
12. Given the following array elements, what does the array look like after one iteration of insertion sort, arranging items in ascending order?
    14 5 7 19 23 4 12 21
    1. 5 14 7 19 23 4 12 21
    2. 4 5 7 19 23 14 12 21
    3. 5 7 14 19 23 4 12 21
    4. 14 5 7 19 23 4 12 21
13. Given the following array elements, what does the array look like after two iterations of selection sort, arranging items in ascending order?
    92 42 73 19 86 33 7 60
    1. 7 19 73 42 86 33 92 60
    2. 42 73 92 19 86 33 7 60
    3. 19 42 73 92 86 33 7 60
    4. 92 42 73 19 86 33 7 60
14. Given the initial array of 9 elements what is the left partition at the beginning of insertion sort?
    
    42 96 13 19 86 33 7 60 51
    1. 42
    2. 42 92
    3. 42 96 13 19
    4. 42 96 13 19 86
15. What is the efficiency of the iterative selection sort method for an array of n items?
    1. O(n²)
    2. O(2ⁿ)
    3. O(n)
    4. O(n log n)
16. What is the efficiency of the iterative selection sort method for a chain of n linked nodes?
    1. O(n²)
    2. O(2ⁿ)
    3. O(n)
    4. O(n log n)
17. The O(n²) analysis of insertion sort is a(n) _______ analysis
    1. worst-case
    2. best-case
    3. average-case
    4. unknown
18. The best-case scenario for an insertion sort is
    1. the elements are already in sorted order
    2. the elements are in reverse sorted order
    3. the elements are in random order
    4. there is no best-case scenario
19. The best-case scenario for an selection sort is
    1. there is no best-case scenario
    2. the elements are in reverse sorted order
    3. the elements are in random order
    4. the elements are already in sorted order
20. The best-case performance for an array of n items using insertion sort is
    1. O(n)
    2. O(n²)
    3. O(1)
    4. there is no best-case
21. What is the efficiency of the insertion sort method for a chain of n linked nodes?
    1. O(n²)
    2. O(2ⁿ)
    3. O(n)
    4. O(n log n)
22. Shell sort works by
    1. using insertion sort on subarrays of equally spaced entries
    2. using insertion sort on subarrays of equal size consecutive entries
    3. iteratively searching for the smallest entry in subarrays of equally spaced entries
    4. iteratively searching for the smallest entry in subarrays of equal size consecutive entries
23. The worst-case performance for shell sort is
    1. O(n²)
    2. O(n^1.5)
    3. O(n^2.5)
    4. O(n3)
24. The average-case performance for shell sort is
    1. O(n^1.5)
    2. O(n²)
    3. O(n^2.5)
    4. O(n3)
25. The best-case performance for shell sort is
    1. O(n)
    2. O(1)
    3. O(n²)
    4. O(n log n)
26. Shell sort can be improved by
    1. adding 1 to the space when it is even
    2. using selection sort instead of insertion sort as the final step
    3. alternating insertion sort and selection sort each iteration
    4. you cannot improve the algorithm’s time efficiency
27. Which sorting algorithm is generally the slowest for a large number of items?
    1. selection sort
    2. insertion sort
    3. shell sort
    4. they are all the same