Java How to Program, 11/e Multiple Choice Test Bank 1 of 4
Chapter 19: Searching, Sorting and Big O
Section 19.1 Introduction
19.1 Q1: Which of the following is a way to sort data?
a. Alphabetically.
b. In increasing numerical order.
c. Based on an account number.
Section 19.2 Linear Search
19.2 Q1: How many comparisons will the linear search algorithm make if the search key is not in an array of 10
elements?
a. 0.
b. 10.
c. 9.
d. 5.
Efficiency of Linear Search
19.2 Q2: Which of the following is not a name for a big O run time?
a. Constant run time.
b.Variable run time.
c. Linear run time.
d. Quadratic run time.
19.2 Q3: What is the efficiency of linear search?
a. O(1).
b. O(log n).
c. O(n).
d. O(n2).
Section 19.3 Big O Notation
19.3 Q1: Big O notation describes ________.
a. the amount of memory required by an algorithm.
b. the difficulty of writing an algorithm to solve a specific problem.
c. an algorithm’s efficiency in terms of the work required to solve a problem.
d. the length of an algorithm for solving a specific problem.
Section 19.3.1 O(1) Algorithms
19.3.1 Q1: A searching algorithm that’s O(1)________.
a. requires one comparison
b. does not necessarily require only one comparison
c. can search only an array of one item.
d. None of the above.
Section 19.3.2 O(n) Algorithms
19.3.2 Q1: An O(n) algorithm is referred to as having a _______ run time.
a. constant
b. linear
c. quadratic
d. negative
19.3.2 Q2: Big O highlights ________ factors and ignores terms that become unimportant with ________ n values.
a. insignificant, low
b. insignificant, high
c. dominant, low
Section 19.3.3 O(n2) Algorithms
19.3.3 Q1: Big O notation is concerned with the growth rate of algorithm run times, so ________.
a. constants are dominant
b. constants are ignored
c. constant terms are emphasized
d. constants with large values are more important than those with low values
19.3.3 Q2: The linear search algorithm runs in ________time.
a. quadratic
b. O(n)
c. constant
d. nonlinear
Section 19.3.4 Big O of the Linear Search
19.3.4 Q1: The worst case in linear search is that every element must be checked to determine whether the search
key exists, which occurs if the search key ________.
a. is the last array element
b. is not present
c. is the last array element or is not present
d. None of the above.
Section 19.4 Binary Search
19.4.1 Q1: Which of the following statements is true?
a. The binary search algorithm is less efficient than the linear search, but it requires that the array be sorted.
b. The binary search algorithm is more efficient than the linear search, but it requires that the array be unsorted.
c. The binary search algorithm is more efficient than the linear search, but it requires that the array be sorted.
d. The binary search algorithm is less efficient than the linear search, but it requires that the array be unsorted.
Section 19.4.1 Binary Search Implementation
19.4.1 Q1: Using a binary search, what is the maximum number of comparisons required to find a search key in a
31-element sorted array?
a. 4.
Java How to Program, 11/e Multiple Choice Test Bank 3 of 4
b. 5.
c. 32.
d. 1.
19.4.1 Q2: Which of the following is a negative of binary search?
a. It requires significantly more memory than linear search.
b. It is slower than linear search.
c. The data must be in sorted order.
d. None of the above.
Section 19.4.2 Efficiency of Binary Search
19.4.2 Q1: What is the term used for binary search’s run time?
a. Linear run time.
b. Quadratic run time.
c. Constant run time.
d. Logarithmic run time.
Section 19.5 Sorting Algorithms
19.5 Q1: Different sorting algorithms on a particular array produce the same result; the choice of algorithm affects
________ of the program that implements the algorithm.
a. only the run time
b. the run time and the memory use
c. only the memory use
d. neither the run time nor the memory use
Section 19.6 Selection Sort
Section 19.6.1 Selection Sort Implementation
19.6.1 Q1: What does the first pass of selection sort do?
a. Splits the array into two approximately equal pieces.
b. Orders the first two elements of the array.
c. Partitions the array into two unequal pieces depending on whether each element in the array is greater or less
that some pivot element.
Section 19.6.2 Efficiency of the Selection Sort
19.6.2 Q1: What is the efficiency of selection sort?
a. O(n2).
b. O(n log n).
c. O(n).
d. O(1).
Section 19.7 Insertion Sort
Section 19.7.1 Insertion Sort Implementation
19.7.1 Q1: What does each iteration of the insertion sort algorithm do?
a. Each iteration takes the next smallest element and inserts it at the beginning of the array.
b. Each iteration takes the next element in the unsorted portion of the array and inserts it into the sorted portion.
c. Sorted subarrays are inserted into the larger array.
d. Each iteration determines the location of a pivot and inserts it into place.
Section 19.7.2 Efficiency of the Insertion Sort
19.7.2 Q1: How much faster is insertion sort with a 15-element array than with a 60-element array?
a. 60 times.
b. 4 times.
c.15 times.
d. 19 times.
Section 19.8 Merge Sort
Section 19.8.1 Merge Sort Implementation
19.8.1 Q1: What is the base case for the recursive merge sort algorithm?
a. Any array that is already sorted.
b. A two-element array.
c. A one-element array.
Section 19.8.2 Efficiency of the Merge Sort
19.8.2 Q1: What is the efficiency of merge sort?
a. O(log n).
b. O(n).
c. O(n log n).
d. O(n2).
19.8.2 Q2: Which of the following sorting algorithms is the fastest?
a. Selection sort.
b. Insertion sort.
c. Merge sort.
d. They all run at roughly the same speed.
Section 19.9 Big O Summary for This Chapter’s Searching and
Sorting Algorithms
(No questions.)
Section 19.10 Massive Parallelism and Parallel Algorithms
(No questions.)