Chapter 23 Check Point Questions
Section 23.2
▼23.2.1
Describe how an insertion sort works. What is the time complexity for an insertion sort?
▼23.2.2
Use Figure 23.1 as an example to show how to apply an insertion sort
on {45, 11, 50, 59, 60, 2, 4, 7, 10}.
▼23.2.3
If a list is already sorted, how many comparisons will the insertionSort method perform?
Section 23.3
▼23.3.1
Describe how a bubble sort works. What is the time complexity for a bubble sort?
▼23.3.2
Use Figure 23.3 as an example to show how to apply a bubble sort on {45, 11, 50, 59, 60, 2, 4, 7, 10}.
▼23.3.3
If a list is already sorted, how many comparisons will the bubbleSort method perform?
Section 23.4
▼23.4.1
Describe how a merge sort works. What is the time complexity for a merge sort?
▼23.4.2
Use Figure 23.4 as an example to show how to apply a merge sort on {45, 11, 50, 59, 60, 2, 4, 7, 10}.
▼23.4.3
What is wrong if lines 6-15 in Listing 23.6, MergeSort.java,
are replaced by the following code?
// Merge sort the first half int[] firstHalf = new int[list.length / 2 + 1]; System.arraycopy(list, 0, firstHalf, 0, list.length / 2 + 1); mergeSort(firstHalf); // Merge sort the second half int secondHalfLength = list.length - list.length / 2 - 1; int[] secondHalf = new int[secondHalfLength]; System.arraycopy(list, list.length / 2 + 1, secondHalf, 0, secondHalfLength); mergeSort(secondHalf);
Section 23.5
▼23.5.1
Describe how quick sort works. What is the time complexity for a quick sort?
▼23.5.2
Why is quick sort more space efficient than merge sort?
▼23.5.3
Use Figure 23.7 as an example to show how to
apply a quick sort on {45, 11, 50, 59, 60, 2, 4, 7, 10}.
▼23.5.4
If lines 37-38 in the QuickSort program is removed, will it still work?
Give a counter example to show that it will not work.
Section 23.6
▼23.6.1
What is a complete binary tree? What is a heap? Describe how to remove the root from a heap and how to add a new object to a heap.
▼23.6.2
When a heap in Figure 23.11a is stored in a list, what is index for element 44? What is the index of parent for 44 and what is the index of left and right children of 44?
▼23.6.3
Add the elements 4, 5, 1, 2, 9, and 3 into a heap in this order.
Draw the diagrams to show the heap after each element is added.
▼23.6.4
Show the steps of creating a heap using {45, 11, 50, 59, 60, 2, 4, 7, 10}.
▼23.6.5
Show the heap after the root in the heap in Figure 23.15c is removed.
▼23.6.6
Given the following heap, show the steps of removing all nodes from the heap.
▼23.6.7
Which of the following statements are wrong?
1 Heap<Object> heap1 = new Heap<>(); 2 Heap<Number> heap2 = new Heap<>(); 3 Heap<BigInteger> heap3 = new Heap<>(); 4 Heap<Calendar> heap4 = new Heap<>(); 5 Heap<> heap5 = new Heap<>();
▼23.6.8
Modify line 12 in Listing 23.10 so that the elements are sorted in a non-increasing order.
▼23.6.9
What is the return value from invoking the remove method if the heap is empty?
▼23.6.10
What is the time complexity of inserting a new element into a heap and what is the time complexity of deleting an element from a heap?
▼23.6.11
What is the height of an empty heap?
What is the height of a heap with only one element?
What is the height of a non-empty heap?
What is the height of a heap with 16, 17, and 512 elements?
If the height of a heap is 5, what is the maximum number of nodes
in the heap?
Section 23.7
▼23.7.1
Can you sort a list of strings using a bucket sort?
▼23.7.2
Show how the radix sort works using the numbers 454, 34, 23, 43, 74, 86, and 76.
Section 23.8
▼23.8.1
Describe how external sort works. What is the complexity of the external sort algorithm?
▼23.8.2
Ten numbers {2, 3, 4, 0, 5, 6, 7, 9, 8, 1} are stored in the external file largedata.dat. Trace the SortLargeFile program by hand with MAX_ARRAY_SIZE 2.