Deck 14: Sorting and Searching

Question 1

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; }

Answer 1

A

Question 2

What type of algorithm places elements in order?

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

Answer 2

A

Question 3

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.

Answer 3

B

Question 4

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 5

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

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

Question 6

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.

Question 7

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 8

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 9

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 10

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 11

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 12

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²

Question 13

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 14

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.

Question 15

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 16

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 17

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 18

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 19

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 20

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 21

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 22

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 23

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 24

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

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

Question 25

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

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

Question 26

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 27

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 28

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

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

Question 29

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 30

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 31

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 32

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 33

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 34

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 35

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 36

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 37

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 38

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 39

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 40

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 41

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 42

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 43

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 44

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 45

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 46

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 47

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 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

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 50

Merge sort is a(n) ____ algorithm.

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

Question 51

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 52

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 53

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 54

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 55

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 56

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 57

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 58

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 59

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 60

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 61

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 62

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 63

Binary search is an ____ algorithm.

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

Question 64

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 65

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 66

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 67

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 68

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 69

An algorithm that tests whether the first array element is equal to any of the other array elements would be an ____ algorithm.

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

Question 70

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 71

An algorithm that cuts the work in half in each step is an ____ algorithm.

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

Question 72

A binary search is generally ____ a linear search.

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

Question 73

Another name for linear search is ____ search.

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

Question 74

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 75

A portion of your program includes the loops shown in the code snippet below to examine the elements of two arrays, arr1 and arr2, both of length n:
Int matches = 0;
For (int i = 0; i < arr1.length; i++)
{
For (int j = 0; j < arr2.length; j++)
{
If (arr1[i].equals(arr2[j]))
{
Matches++;
}
}
}
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 76

The method checkArray examines an array arr:
Public static boolean checkArray(int[] arr)
{
If (arr[0] >= arr[arr.length -1])
{
Return true;
}
Return false;
}
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(1).

Question 77

A portion of your program includes the method shown in the code snippet below to examine the elements of an array arr:
Private int findElement(int[] arr, int newVal)
{
Int pos = Arrays.binarySearch(arr, newVal);
Return pos;
}
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 78

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 79

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 80

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)).