Deck 14: Sorting and Searching

Question 1

Consider the sort method for selection sort shown below: public static void sort (int[]
A) {
For (int i = 0; i < a.length - 1; i++)
{
Int minPos = minimumPosition(i);
Swap(minPos, i);
}
}
Suppose we modify the loop control to read int i = 1; i < a.length - 1; i++. What would be the result?

A) An exception would occur
B) The sort would not consider the last array element.
C) The sort would not consider the first array element.
D) The sort would still work correctly.

Answer 1

C

Question 2

Consider the sort method shown below for selection sort: public static void sort (int[]
A) {
For (int i = 0; i < a.length - 1; i++)
{
Int minPos = minimumPosition(i);
Swap(minPos, i);
}
}
Suppose we modify the call to the swap method call to read swap(i, minPos). What would be the result?

A) An exception would occur.
B) The sort would produce incorrect results.
C) The sort would work, but sort backwards.
D) The sort would produce correct results.

Answer 2

D

Question 3

Consider an array with n elements. If we visit each element n times, how many total visits will there be?

A) n
B) 2n
C) nⁿ
D) n²

Answer 3

D

Question 4

Suppose an algorithm requires a total of 3n³ + 2n² - 3n + 4 visits. In big-Oh notation, the total number of visits is of what order?

A) n² * n²
B) n²
C) n⁶
D) n³

Question 5

In each iteration, selection sort places which element in the correct location?

A) The smallest in the array.
B) The smallest element not yet placed in prior iterations.
C) The largest element in the array.
D) A random element.

Question 6

Suppose an array has n elements. We visit element #1 one time, element #2 two times, element #3 three times, and so forth. How many total visits will there be?

A) 2n
B) n(n+1)/2
C) n²
D) n³

Question 7

Consider the swap method shown below from the SelectionSorter class. If we modified it as shown in the swap2 method shown below, what would be the effect on the sort method? private static void swap(int[] a, int i, int j)
{
Int temp = a[i];
A[i] = a[j];
A[j] = temp;
}
Private static void swap2(int[] a, int i, int j)
{
A[i] = a[j];
A[j] = a[i];
}

A) There would be no effect.
B) Some array elements would be overwritten.
C) It would sort the array in reverse order.
D) It would still be correct, but run a little faster.

Question 8

In big-Oh notation, suppose an algorithm requires an order of n³ element visits. How does doubling the number of elements affect the number of visits?

A) It doubles the number of visits.
B) It quadruples the number of visits.
C) It triples the number of visits.
D) It number of visits goes up by a factor of eight.

Question 9

After 9 iterations of selection sort working on an array of 10 elements, what must hold true?

A) The largest element is correctly placed by default.
B) One more iteration is needed to complete the sort.
C) The smallest element is incorrectly placed.
D) The largest element is incorrectly placed.

Question 10

After one iteration of selection sort working on an array of 10 elements, what must hold true?

A) The array cannot be sorted.
B) One element must be correctly placed.
C) At least two elements are correctly placed.
D) The largest element is correctly placed.

Question 11

The largestPosition method below returns the index of the largest element in the tail range of an array of integers. Select the expression that would be needed to complete the selectionSort method below, so that it sorts the elements in descending order. /**
Finds the largest element in the tail range of an array.
@param a the array to be searched
@param from the first position in a to compare
@return the position of the largest element in range a[from]..a[a.length - 1]
*/
Private static int largestPosition(int[] a, int from)
{
Int maxPos = from;
For (int j = from + 1; j < a.length; j++)
{
If (a[j] > a[maxPos])
{
MaxPos = j;
}
}
Return maxPos;
}
Public static void selectionSort(int[]
A) {
For ____________________________________
{
Int maxPos = largestPosition(a, i);
ArrayUtil.swap(a, maxPos, i);
}
}

A) (int i = 0; i < a.length - 1; i++)
B) (int i = 0; i < a.length; i++)
C) (int i = a.length; i > 0; i--)
D) (int i = a.length - 1; i > 0; i--)

Question 12

Consider the minimumPosition method from the SelectionSorter class. Complete the code to write a maximumPosition method that returns the index of the largest element in the range from index from to the end of the array. private static int minimumPosition(int[] a, int from)
{
Int minPos = from;
For (int i = from + 1; i < a.length; i++)
{
If (a[i] < a[minPos]) { minPos = i; }
}
Return minPos;
}
Private static int maximumPosition(int[] a, int from)
{
Int maxPos = from;
For (int i = from + 1; i < a.length; i++)
{
________________
}
Return maxPos;
}

A) if(a[i] > a[maxPos]) { maxPos = i; }
B) if(a[i] == a[maxPos]) { maxPos = i; }
C) if(a[i] < a[maxPos]) { maxPos = i; }
D) if(a[i] <= a[maxPos]) { maxPos = i; }

Question 13

After 5 iterations of selection sort working on an array of 10 elements, what must hold true?

A) 5 more iterations are always necessary to complete the sort
B) 4 more iterations are always necessary to complete the sort
C) 5 more iterations may be needed to complete the sort
D) 4 more iterations may be needed to complete the sort

Question 14

The performance of an algorithm is most closely related to what?

A) The total number of element visits
B) The total number of elements
C) The type of elements
D) The number of lines of code in the method

Question 15

Suppose you wanted to test your sort on an array filled with different elements each time the code is run. What is an efficient technique for creating an array of 1,000 elements for each run?

A) Run the program many times, entering different values for the array elements.
B) Make a file with many sets of values and loop through them, sorting each one.
C) Use the Random class to generate array elements, sorting each set in a loop.
D) Create many different arrays with different elements in the program code and sort each array.

Question 16

What type of algorithm places elements in order?

A) sorting
B) searching
C) insertion
D) deletion

Question 17

Consider the sort method shown below for selection sort: public static void sort(int[]
A) {
For (int i = 0; i < a.length - 1; i++)
{
Int minPos = minimumPosition(i);
Swap(minPos, i);
}
}
Suppose we modify the loop condition to read i < a.length. What would be the result?

A) An exception would occur.
B) The sort would work, but run one more iteration.
C) The sort would work but with one less iteration.
D) The sort would work exactly the same as before the code modification.

Question 18

In big-Oh notation, when we consider the order of the number of visits an algorithm makes, what do we ignore?
I power of two terms
II the coefficients of the terms
III all lower order terms

A) I
B) II
C) I and II
D) II and III

Question 19

Which selection sort iteration guarantees the array is sorted for a 10-element array?

A) 9^th iteration
B) 10^th iteration
C) 1^st iteration
D) impossible to tell

Question 20

The code segment below is designed to add the elements in an array of integers. Select the expression needed to complete the code segment so that it calculates the running time elapsed. long start = System.currentTimeMillis();
Int sum = 0;
For (int k = 0; k < values.length; k++)
{
Sum = sum + values[k];
}
Long runningTime = ____________________________;

A) System.currentTimeMillis()
B) System.currentTimeMillis() - start
C) System.currentTimeMillis() + start
D) runningTime + start - System.currentTimeMillis()

Question 21

Which sort algorithm starts by cutting the array in half and then recursively sorts each half?

A) insertion sort
B) selection sort
C) merge sort
D) quicksort

Question 22

In Big-Oh notation, selection sort is a(n) ____ algorithm.

A) O(n²)
B) O(1)
C) log n
D) O(log n²)

Question 23

Which function has a faster growth rate: θ(n^1/2) or θ(log(n))?

A) θ(log(n))
B) θ(n^1/2)
C) They are the same.
D) They can't be compared.

Question 24

Choose the order of the following growth rates, from slowest to fastest: θ(n³), θ(nlog(n)), θ(n^3/2), θ(2ⁿ).

A) θ(n log(n)), θ(n^3/2), θ(n³), θ(2ⁿ)
B) θ(n³), θ(n log(n)), θ(n^3/2), θ(2ⁿ)
C) θ(n^3/2), θ(n log(n)), θ(n³), θ(2ⁿ)
D) θ(2ⁿ), θ(n³), θ(n^3/2), θ(n log(n))

Question 25

How many comparisons does selection sort make when sorting an array of length n?

A) n
B) log(2n)
C) n( n + 1) / 2
D) n

Question 26

Find the simplest order of growth of the following expression: (n³ + n + 3)².

A) θ(n⁵)
B) θ(2ⁿ)
C) θ(n⁶)
D) θ(n⁹)

Question 27

How large does n need to be so 0.3n² is greater than 2.5n - 3?

A) 3
B) 5
C) 7
D) 9

Question 28

What is the worst-case performance of insertion sort?

A) O(n)
B) O(n²)
C) O(log (n))
D) O(n log (n))

Question 29

Which of the following completes the selection sort method minimumPosition()? private static int minimumPosition(int[] a, int from)
{
Int minPos = from;
For (int i = from + 1; i < a.length; i++)
{
________________
}
Return minPos;
}

A) if (a[i] > a[minPos]) { minPos = i; }
B) if (a[i] < a[minPos]) { minPos = i; }
C) if (a[i] < a[j]) { minPos = i; }
D) if (a[i] < a[minPos]) { i = minPos; }

Question 30

Which sort algorithm starts with an initial sequence of size 1, which is assumed to be sorted, and increases the size of the sorted sequence in the array in each iteration?

A) insertion sort
B) selection sort
C) merge sort
D) quicksort

Question 31

Find the simplest order of growth of the following expression: n³ + log(n⁵).

A) θ(n³)
B) θ(n³+ log(n))
C) θ(log(n⁵))
D) θ(n + log(n))

Question 32

How many times can an array with 4,096 elements be cut into two equal pieces?

A) 16
B) 12
C) 10
D) 8

Question 33

What is the smallest value of n for which n² > 3n + 4?

A) 6
B) 5
C) 4
D) 3

Question 34

If f(n) = O(g(n)) and g(n) = O(f(n)), what else must be true?
I f(n) = Ω(g(n))
II g(n) = Ω(f(n))
III f(n) = θ(g(n))

A) I
B) II
C) I and II
D) I, II, and III

Question 35

Which notation, big-Oh, theta, or omega describes the growth rate of a function?
I big-Oh
II theta
III omega

A) I
B) II and III
C) I and II
D) I, II, and III

Question 36

If the array is already sorted, what is the performance of insertion sort?

A) O(n)
B) O(n²)
C) O(log n)
D) O(n log n)

Question 37

In general, the expression ____ means that f grows no faster than g.

A) f(n) = log g
B) f(n) = log g²
C) f(n) = O(g(n))
D) g(n) = O(f(n))

Question 38

When the size of an array increases by a factor of 100, the time required by selection sort increases by a factor of ____.

A) 2,000
B) 5,000
C) 10,000
D) 12,000

Question 39

Consider the following code snippet: public static void sort(int[]
A) {
For (int i = 1; i < a.length; i++)
{
Int next = a[i];
Int j = i;
While (j > 0 && a[j - 1] > next)
{
A[j] = a[j - 1];
J--;
}
A[j] = next;
}
}
What sort algorithm is used in this code?

A) insertion sort
B) selection sort
C) merge sort
D) quicksort

Question 40

If you increase the size of a dataset fivefold, how much longer does it take to sort it with the selection sort algorithm?

A) Approximately 5 times longer
B) Approximately 20 times longer
C) Approximately 25 times longer
D) Approximately 100 times longer

Question 41

How many times can an array with 729 elements be cut into three equal pieces?

A) 4
B) 5
C) 6
D) 7

Question 42

In the worst case, quicksort is a(n) ____ algorithm.

A) O(n)
B) O(log(n))
C) O(n²)
D) O(n log n)

Question 43

In the textbook, we found that the number of element visits for merge sort totaled n + 5n log₂ n. Which of the following is the appropriate big-Oh notation for merge sort?

A) 5n log₂ n
B) n + log₂ n
C) n + 5n
D) n log₂ n

Question 44

A version of which sort algorithm is used in the sort method in the Java Arrays class?

A) merge sort
B) quicksort
C) selection sort
D) insertion sort

Question 45

Which of the sorts in the textbook are based on the strategy of divide and conquer?
I quicksort
II mergesort
III insertion sort

A) I
B) II
C) III
D) I and II

Question 46

Which of the sorts in the textbook can be characterized by the fact that even in the worst case the running time will be O(n log(n)))?
I quicksort
II selection sort
III merge sort

A) I
B) II
C) III
D) I and III

Question 47

When does quicksort's worst-case run-time behavior occur?
I when the data is randomly initialized in the array
II when the data is in ascending order
III when the data is in descending order

A) I
B) II
C) III
D) II and III

Question 48

Selection sort has O(n²) complexity. If a computer can sort 1,000 elements in 4 seconds, approximately how many seconds will it take the computer to sort 1,000 times that many, or 1,000,000 elements?

A) 16
B) 1,000
C) 1,000,000
D) 4,000,000

Question 49

In the worst case, a linear search locates a value in an array of length n in ____ steps.

A) O(n²)
B) O(log n)
C) O(n)
D) O(log n²)

Question 50

Which sort algorithm starts by partitioning the array and selecting a pivot element?

A) merge sort
B) quicksort
C) selection sort
D) insertion sort

Question 51

In the textbook, we found that the number of element visits for merge sort totaled n + 5nlog₂n. Let's consider sorting 1024 elements. How many visits are needed?

A) 1.024
B) 6,144
C) 51,200
D) 52,224

Question 52

Which sort algorithm is used in the sort method in the Java Arrays class when the array length is less than 7?

A) merge sort
B) quicksort
C) selection sort
D) insertion sort

Question 53

Assume we are using quicksort to sort an array in ascending order. What can we conclude about the indexes of two pivot elements placed in consecutive recursive calls?

A) They are randomly located.
B) They are in different halves of the array.
C) They are both in the same half of the array.
D) They are adjacent.

Question 54

Assume we are using quicksort to sort an array in ascending order. What can we conclude about the elements to the left of the currently placed pivot element?

A) They are all sorted.
B) They are all less than or equal to the pivot element.
C) They are all greater than or equal to the pivot element.
D) None can equal the pivot element.

Question 55

Merge sort is a(n) ____ algorithm.

A) O(n)
B) O(n log(n))
C) O(n²)
D) O(log n)

Question 56

Which of the sorts in the textbook can be characterized by the fact that the best case will have a running time of θ(n) if the data is already sorted?
I quicksort
II selection sort
III insertion sort

A) I
B) II
C) III
D) I and III

Question 57

The merge sort algorithm presented in section 14.4, which sorts an array of integers in ascending order, uses the merge method which is partially shown below. Select the condition that would be needed to complete the method so that the elements are sorted in descending order. private static void merge(int[] first, int[] second, int[]
A) {
Int iFirst = 0;
Int iSecond = 0;
Int j = 0;
While (iFirst < first.length && iSecond < second.length)
{
If (_____________________________)
{
A[j] = first[iFirst];
IFirst++;
}
Else
{
A[j] = second[iSecond];
ISecond++;
}
J++;
}
// rest of the method follows here
}

A) first[iFirst] < second[iSecond]
B) iFirst < iSecond
C) first[iFirst] > second[iSecond]
D) iFirst > iSecond

Question 58

Merge sort has a O(n log₂(n)) complexity. If a computer can sort 1,024 elements in an amount of time x, approximately how much longer will it take the computer to sort 1,024 times that many, or 1,048,576 elements?

A) 1,024 times longer
B) 2,048 times longer
C) 8,192 times longer
D) 1,048,576 times longer

Question 59

Assume we are using quicksort to sort an array in ascending order. Into which array location does quicksort's strategy place a pivot element after partitioning?

A) lowest index in array still available
B) highest index in array still available
C) closer to its correct final location
D) its final correct location

Question 60

In the textbook, we determined that the merge method requires a total of 5n visits. We found that the number of visits required to sort an array of n elements is T(n) = T(n / 2) + T(n / 2) + 5n. What does T(n / 2) describe?

A) the total number of visits to merge sort an array of n elements
B) half the number of visits to merge sort an array of n elements
C) the total number of visits to merge sort an array of n / 2 elements
D) half the number of visits to merge sort an array of n / 2 elements

Question 61

Suppose we are using binary search on an array with approximately 1,000,000 elements. How many visits should we expect to make in the worst case?

A) 1
B) 16
C) 20
D) 30

Question 62

Given an ordered array with 15 elements, how many elements must be visited in the worst case of binary search?

A) 8
B) 4
C) 3
D) 2

Question 63

Which of the following statements about running times of algorithms is correct?

A) An algorithm that is O(1) means that only one comparison takes place.
B) When determining the running time, constants are not taken into consideration.
C) When determining the running time, lower-order terms must be taken into consideration.
D) An algorithm that is O(n) means that the number of comparisons does not grow as the size of the array increases.

Question 64

Another name for linear search is ____ search.

A) sorted
B) sequential
C) random
D) binary

Question 65

Can you search the following array using binary search?
Int[] A = {6, 5, 4, 2, 0, 1, -1, -17};

A) Yes. Binary search can be applied to any array.
B) No. Binary search can be applied to a sorted array only.
C) Yes, but the algorithm runs slower because the array is in descending order.
D) No, negative numbers are not allowed because they indicate that a value is not present.

Question 66

The partial linear search method below is designed to search an array of String objects. Select the expression that would be needed to complete the method. public static int search(String[] a, String item)
{
For (int i = 0; i < a.length; i++)
{
If ( ____________________________ )
{
Return i;
}
Return -1;
}
}

A) a[i] == item
B) a[i].compareTo(item)
C) a[i].equals(item)
D) a[i].indexOf(item)

Question 67

The partial binary search method below is designed to search an array of String objects sorted in ascending order. Select the expression that would be needed to complete the method. public static int search(String[] a, int low, int high, String item)
{
If (low <= high)
{
Int mid = (low + high) / 2;
Int result = ____________________________;
If (result == 0)
{
Return mid;
}
Else if (result < 0)
{
Return search(a, mid + 1, high, item);
}
Else
{
Return search(a, low, mid - 1, item);
}
}
Return -1;
}

A) a[low].compareTo(item)
B) item.equals(a[mid])
C) item.compareTo(a[mid])
D) a[mid].compareTo(item)

Question 68

Given an ordered array with 31 elements, how many elements must be visited in the worst case of binary search?

A) 16
B) 8
C) 5
D) 4

Question 69

The following code is an example of a ___ search. public static int search(int[] a, int v)
{
For (int i = 0; i < a.length; i++)
{
If (a[i] == v) { return i; }
}
Return -1;
}

A) sorted
B) binary
C) linear
D) random

Question 70

A portion of your program includes the loop shown in the code snippet below to examine the elements of an array arr:
Int count = 0;
Int targetVal = 70;
For (int i = 0; i < arr.length; i++)
{
If (arr[i] >= targetVal)
{
Count++;
}
}
What can you conclude about the running time of this section of code?

A) Its running time will be O(n).
B) Its running time will be O(n²).
C) Its running time will be O(log (n)).
D) Its running time will be O(n log (n)).

Question 71

The analysis for the number of visits in a binary search begins with the equation, T(n) = T(n / 2) + 1. What does the number 1 represent in this equation?

A) One element visit before a recursive call on one half of the array.
B) The total number of recursions required.
C) The fact that the number of elements is odd.
D) The fact that we search either the left half or the right half, but not both.

Question 72

If an element is present in an array of length n, how many element visits, in the worst case, are necessary to find it using a linear search?

A) n / 2
B) n
C) 2n
D) n²

Question 73

A portion of your program implements a loop in which each step contains a fixed number of actions. What can you conclude about the running time of this section of code?

A) Its running time will be O(n).
B) Its running time will be O(n²).
C) Its running time will be O(log (n)).
D) Its running time will be O(n log (n)).

Question 74

If an element is present in an array of length n, how many element visits, on average, are necessary to find it using a linear search?

A) n / 2
B) n
C) 2n
D) n²

Question 75

Suppose you have a phone number and need to find the address that it corresponds to. If there are 2,000,000 entries, how many do you expect to search in a printed phone directory before finding the address you are looking for?

A) Approximately 50,000 records.
B) Approximately 75,000 records.
C) Approximately 1,000,000 records.
D) Approximately 1,200,000 records.

Question 76

Binary search is an ____ algorithm.

A) O(n)
B) O(n²)
C) O(log n)
D) O(n log n)

Question 77

If you implement a recursive linear search, its performance will be ____.

A) O(n)
B) O(n²)
C) O(log (n))
D) O(n log (n))

Question 78

The method findLargest examines the elements of an array arr which contains non-negative values public static int findLargest(int[] arr)
{
Int curLargest = -1;
For (int i = 0; i < arr.length; i++)
{
If (arr[i] >= curLargest)
{
CurLargest = arr[i];
}
}
Return curLargest;
}
What can you conclude about the running time of this section of code?

A) Its running time will be O(n).
B) Its running time will be O(n²).
C) Its running time will be O(log (n)).
D) Its running time will be O(n log (n)).

Question 79

A search technique where, in each step, you split the size of the search in half is called a____ search.

A) random
B) binary
C) linear
D) merging

Question 80

A binary search is generally ____ a linear search.

A) slower than
B) equal to
C) less efficient than
D) faster than