# Quiz 14: Sorting and Searching

Computing

Q 1Q 1

What type of algorithm places elements in order?
A) sorting
B) searching
C) insertion
D) deletion

Free

Multiple Choice

A

Q 2Q 2

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.

Free

Multiple Choice

B

Q 3Q 3

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

Free

Multiple Choice

B

Q 4Q 4

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.

Free

Multiple Choice

Q 5Q 5

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.

Free

Multiple Choice

Q 6Q 6

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.

Free

Multiple Choice

Q 7Q 7

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.

Free

Multiple Choice

Q 8Q 8

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

Free

Multiple Choice

Q 9Q 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.

Free

Multiple Choice

Q 10Q 10

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.

Free

Multiple Choice

Q 11Q 11

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.

Free

Multiple Choice

Q 12Q 12

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 tellFree

Multiple Choice

Q 13Q 13

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

Free

Multiple Choice

Q 14Q 14

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

Free

Multiple Choice

Q 15Q 15

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

Free

Multiple Choice

Q 16Q 16

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

^{n}D) n^{2}Free

Multiple Choice

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

^{2}D) n^{3}Free

Multiple Choice

Q 18Q 18

Suppose an algorithm requires a total of 3n

^{3}+ 2n^{2}- 3n + 4 visits. In big-Oh notation, the total number of visits is of what order? A) n^{2}* n^{2}B) n^{2}C) n^{6}D) n^{3}Free

Multiple Choice

Q 19Q 19

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

Free

Multiple Choice

Q 20Q 20

In big-Oh notation, suppose an algorithm requires an order of n

^{3}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.Free

Multiple Choice

Free

Multiple Choice

Free

Multiple Choice

Q 23Q 23

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

Free

Multiple Choice

Q 24Q 24

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

Free

Multiple Choice

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

Free

Multiple Choice

Q 26Q 26

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

^{2}) B) O(1) C) log n D) O(log n^{2})Free

Multiple Choice

Q 27Q 27

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

Free

Multiple Choice

Q 28Q 28

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

Free

Multiple Choice

Q 29Q 29

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

Free

Multiple Choice

Q 30Q 30

In general, the expression ____ means that f grows no faster than g.
A) f(n) = log g
B) f(n) = log g

^{2}C) f(n) = O(g(n)) D) g(n) = O(f(n))Free

Multiple Choice

Q 31Q 31

Find the simplest order of growth of the following expression: (n

^{3}+ n + 3)^{2}. A) θ(n^{5}) B) θ(2^{n}) C) θ(n^{6}) D) θ(n^{9})Free

Multiple Choice

Q 32Q 32

Find the simplest order of growth of the following expression: n

^{3}+ log(n^{5}). A) θ(n^{3}) B) θ(n^{3}+ log(n)) C) θ(log(n^{5})) D) θ(n^{ }+ log(n))Free

Multiple Choice

Q 33Q 33

Choose the order of the following growth rates, from slowest to fastest: θ(n

^{3}), θ(nlog(n)), θ(n^{3/2}), θ(2^{n}). A) θ(n log(n)), θ(n^{3/2}), θ(n^{3}), θ(2^{n}) B) θ(n^{3}), θ(n log(n)), θ(n^{3/2}), θ(2^{n}) C) θ(n^{3/2}), θ(n log(n)), θ(n^{3}), θ(2^{n}) D) θ(2^{n}), θ(n^{3}), θ(n^{3/2}), θ(n log(n))Free

Multiple Choice

Q 34Q 34

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

Multiple Choice

Q 35Q 35

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

Free

Multiple Choice

Q 36Q 36

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

Free

Multiple Choice

Q 37Q 37

What is the worst-case performance of insertion sort?
A) O(n)
B) O(n

^{2}) C) O(log (n)) D) O(n log (n))Free

Multiple Choice

Q 38Q 38

If the array is already sorted, what is the performance of insertion sort?
A) O(n)
B) O(n

^{2}) C) O(log n) D) O(n log n)Free

Multiple Choice

Q 39Q 39

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

Free

Multiple Choice

Q 40Q 40

How many times can an array with 4,096 elements be cut into two equal pieces?
A) 16
B) 12
C) 10
D) 8

Free

Multiple Choice

Q 41Q 41

How many times can an array with 729 elements be cut into three equal pieces?
A) 4
B) 5
C) 6
D) 7

Free

Multiple Choice

Q 42Q 42

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

Free

Multiple Choice

Q 43Q 43

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

Free

Multiple Choice

Q 44Q 44

In the textbook, we found that the number of element visits for merge sort totaled n + 5nlog

_{2}n. Let's consider sorting 1024 elements. How many visits are needed? A) 1.024 B) 6,144 C) 51,200 D) 52,224Free

Multiple Choice

Q 45Q 45

In the textbook, we found that the number of element visits for merge sort totaled n + 5n log

_{2}_{ }n. Which of the following is the appropriate big-Oh notation for merge sort? A) 5n log_{2}_{ }n B) n + log_{2}_{ }n C) n + 5n D) n log_{2}_{ }nFree

Multiple Choice

Q 46Q 46

Selection sort has O(n

^{2}) 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,000Free

Multiple Choice

Q 47Q 47

Merge sort has a O(n log

_{2}(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 longerFree

Multiple Choice

Free

Multiple Choice

Q 49Q 49

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

Free

Multiple Choice

Q 50Q 50

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.

Free

Multiple Choice

Q 51Q 51

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.

Free

Multiple Choice

Q 52Q 52

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

Free

Multiple Choice

Q 53Q 53

Which sort algorithm starts by partitioning the array and selecting a pivot element?
A) merge sort
B) quicksort
C) selection sort
D) insertion sort

Free

Multiple Choice

Q 54Q 54

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

Free

Multiple Choice

Q 55Q 55

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

Free

Multiple Choice

Q 56Q 56

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

Free

Multiple Choice

Q 57Q 57

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

Free

Multiple Choice

Q 58Q 58

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

Free

Multiple Choice

Q 59Q 59

In the worst case, quicksort is a(n) ____ algorithm.
A) O(n)
B) O(log(n))
C) O(n

^{2}) D) O(n log n)Free

Multiple Choice

Q 60Q 60

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

^{2}) B) O(log n) C) O(n) D) O(log n^{2})Free

Multiple Choice

Q 61Q 61

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

Free

Multiple Choice

Q 62Q 62

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.

Free

Multiple Choice

Q 63Q 63

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

^{2}Free

Multiple Choice

Q 64Q 64

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

^{2}Free

Multiple Choice

Free

Multiple Choice

Q 66Q 66

If you implement a recursive linear search, its performance will be ____.
A) O(n)
B) O(n

^{2}) C) O(log (n)) D) O(n log (n))Free

Multiple Choice

Free

Multiple Choice

Q 68Q 68

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

Free

Multiple Choice

Q 69Q 69

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

Free

Multiple Choice

Q 70Q 70

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.

Free

Multiple Choice

Q 71Q 71

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

Free

Multiple Choice

Q 72Q 72

A binary search is generally ____ a linear search.
A) slower than
B) equal to
C) less efficient than
D) faster than

Free

Multiple Choice

Q 73Q 73

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

Free

Multiple Choice

Q 74Q 74

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.

Free

Multiple Choice

Q 75Q 75

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)

Free

Multiple Choice

Q 76Q 76

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)

Free

Multiple Choice

Q 77Q 77

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

^{2}). C) Its running time will be O(log (n)). D) Its running time will be O(n log (n)).Free

Multiple Choice

Q 78Q 78

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.

Free

Multiple Choice

Q 79Q 79

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

^{2}). C) Its running time will be O(log (n)). D) Its running time will be O(n log (n)).Free

Multiple Choice

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

^{2}). C) Its running time will be O(log (n)). D) Its running time will be O(n log (n)).Free

Multiple Choice

Q 81Q 81

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

^{2}). C) Its running time will be O(log (n)). D) Its running time will be O(1).Free

Multiple Choice

Q 82Q 82

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

Free

Multiple Choice

Q 83Q 83

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

^{2}). C) Its running time will be O(log (n)). D) Its running time will be O(n log (n)).Free

Multiple Choice

Q 84Q 84

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

^{2}). C) Its running time will be O(log (n)). D) Its running time will be O(n log (n)).Free

Multiple Choice

Q 85Q 85

An algorithm that cuts the work in half in each step is an ____ algorithm.
A) O(n)
B) O(n

^{2}) C) O(log (n)) D) O(n log (n))Free

Multiple Choice

Q 86Q 86

The code segment below prints some of the elements in an array with size n. Select an expression to complete the code segment so that the resulting algorithm has O(log n) running time. for __________________________
{
System.out.println(array[j]);
}
A) (int j = 0; j < array.length; j = j + 2)
B) (int j = 1; j < array.length; j = j * 2)
C) (int j = 0; j < array.length / 2; j++)
D) (int j = 0; j < array.length; j++)

Free

Multiple Choice

Q 87Q 87

The code segment below displays a pattern of asterisks. Select an expression to complete the code segment so that the resulting algorithm has O(n) running time. for (int k = 0; k < n; k++)
{
For _______________________
{
System.out.print("*");
}
System.out.println();
}
A) (int j = n; j > 0; j = j / 2)
B) (int j = n; j > 0; j--)
C) (int j = 1; j < k; j++)
D) (int j = 1; j <= 10; j++)

Free

Multiple Choice

Q 88Q 88

The code segment below displays a table of numbers. Select an expression to complete the code segment, so that the resulting algorithm has O(n

^{2}) running time. for (int k = 1; k <= n; k++) { For _______________________ { System.out.print(j + " "); } System.out.println(); } A) (int j = n; j > 0; j = j / 2) B) (int j = 1; j < k; j = j * 2) C) (int j = 0; j < k; j++) D) (int j = 1; j <= 200; j++)Free

Multiple Choice

Q 89Q 89

Assume that names is an array of String objects that has been initialized with a large number of elements. Select the statement that would sort the elements in names in ascending alphabetic order.
A) Arrays.sort(names, 0, names.length - 1);
B) Arrays.sort(names);
C) Collections.sort(names, 0, names.length - 1);
D) Collections.sort(names);

Free

Multiple Choice

Q 90Q 90

Assume that bands is an ArrayList of String objects which contains a number of elements in ascending order. Select a statement to complete the code segment below, which invokes the Java library binarySearch method to search for the string "Beatles". If the list does not already contain the string, it should be inserted in an appropriate location so that the list remains sorted.
Int index = Collections.binarySearch(bands, "Beatles");
If (index < 0)
{
__________________________
}
A) bands.add(-1 * index + 1, "Beatles");
B) bands.add(index + 1, "Beatles");
C) bands.add(-1 * index, "Beatles");
D) bands.add(-1 - index, "Beatles");

Free

Multiple Choice

Q 91Q 91

The sort method of the Arrays class sorts arrays containing objects of classes that implement the ____ interface.
A) Sortable
B) Ordered
C) Array
D) Comparable

Free

Multiple Choice

Q 92Q 92

The ____ class contains a sort method that can sort array lists.
A) Sorting
B) Arrays
C) Collections
D) Linear

Free

Multiple Choice

Q 93Q 93

The binarySearch method of the Collections class returns a value in the form of -k - 1 when the target item you are searching for was not found in the array. What does k represent?
A) It is the position of an existing item, and indicates that your target item should come after this existing item.
B) It is the position of an existing item, and indicates that your target item should come before this existing item.
C) It represents the number of times the array was accessed by the binarySearch method, and can be used for analyzing performance.
D) Nothing - it is an arbitrary value.

Free

Multiple Choice

Q 94Q 94

Given the following code snippet for searching an array:
Int[] arr = {3, 8, 12, 14, 17};
Int newVal = 15;
Int pos = Arrays.binarySearch(arr, newVal);
What value will pos have when this code is executed?
A) 5
B) -5
C) 6
D) -6

Free

Multiple Choice

Q 95Q 95

Given the following code snippet for searching an array:
Int[] arr = {23, 25, 29, 34, 42};
Int newVal = 15;
Int pos = Arrays.binarySearch(arr, newVal);
What value will pos have when this code is executed?
A) 0
B) 1
C) -1
D) -2

Free

Multiple Choice

Q 96Q 96

If a call to the Arrays static method binarySearch returns a value of -10, what can be concluded?
I the element is not in the array
II the element is at index 10
III the element can be inserted at index 9
A) I
B) II
C) III
D) I and III

Free

Multiple Choice

Q 97Q 97

If a call to the Arrays static method binarySearch returns a value of 7, what can be concluded?
I the element is not in the array
II the element is at index 7
III the element occurs 7 times in the array
A) I
B) II
C) III
D) II and III

Free

Multiple Choice

Q 98Q 98

If the Arrays static method binarySearch is called on an array of 10 elements and returns a value of 10, what can be concluded?
I the element is not found
II that value cannot be returned from method binarySearch
III if added, the element would be the largest element in the array
A) I
B) II
C) III
D) I and III

Free

Multiple Choice

Q 99Q 99

If you want to use the Comparable interface, you must implement a single method called ____.
A) comparable
B) compareTo
C) comparator
D) compare

Free

Multiple Choice

Q 100Q 100

Which of the following classes implement the Comparable interface?
I Date
II Collections
III String
A) I
B) I and II
C) I and III
D) II and III

Free

Multiple Choice

Q 101Q 101

Suppose the call obj1.compareTo(obj2) returns 0. What can definitely be concluded from the return value?
I obj1 and obj2 are the same object
II obj1 and obj2 objects cannot be compared
III the properties of obj1 and obj2 that are being compared have identical values
A) I
B) II
C) I and III
D) III

Free

Multiple Choice

Q 102Q 102

Which of the following arrays can be used in a call to the Arrays.sort method?
I Any array with primitive numeric data, such as int, double, …
II Arrays of String or numeric wrapper classes like, Integer, Double, …
III Any class that implements the Comparable interface
A) I
B) II
C) I and II
D) I, II and III

Free

Multiple Choice

Q 103Q 103

Suppose objects a and b are from a user-defined class that implements the Comparable interface. Which condition tests the compareTo method's return value to determine that a will precede b when the sort method is called?
A) a.compareTo(b) == -1
B) a.compareTo(b) == 0
C) a.compareTo(b) < 0
D) a.compareTo(b) > 0

Free

Multiple Choice

Q 104Q 104

Suppose objects a and b are from a user-defined class that implements the Comparable interface. What must be true about the return value of a.compareTo(b) for the compareTo method that this class implements?
A) It must return 1 if a comes before b, 0 if they are the same, and -1 if a comes after b.
B) It must return -1 if a comes before b, 0 if they are the same, and 1 if a comes after b.
C) It must return a positive value if a comes before b, 0 if they are the same, and a negative value if a comes after b.
D) It must return a negative value if a comes before b, 0 if they are the same, and a positive value if a comes after b.

Free

Multiple Choice

Q 105Q 105

Suppose you wish to implement the Comparable interface to allow your Vehicle class to compare Auto objects only. Which of the following is the correct way to do this?
A) public class Auto implements Comparable
B) public class Vehicle implements Comparable
C) public class Vehicle implements Comparable
D) public class Vehicle implements Comparable(Auto)

Free

Multiple Choice

Q 106Q 106

Suppose a developer gets class XYZ files and documentation from a subcontractor. This class does not implement the Comparable interface. What must be true in order for the developer to sort an array of XYZ objects without modifying the xyz class?
A) The XYZ class must implement the Sortable interface.
B) XYZ objects must be randomly distributed.
C) XYZ objects must be ordered.
D) The developer must supply a comparator object belonging to a class that implements the Comparator interface.

Free

Multiple Choice

Q 107Q 107

Suppose you wish to sort an array list of objects, but the object class does not implement the Comparable interface. Because you are not allowed to modify this class, you decide to provide a comparator object that implements the Comparator interface. Which method must you implement from this interface to achieve your objective?
A) the sort method.
B) the compare method.
C) the compareTo method.
D) the compareObject method.

Free

Multiple Choice

Q 108Q 108

When your class implements a comparator object, you must implement the compare method. What must be true about the return value from this method when comparing two objects, a and b with a call to a.compare(b)?
A) It must return 1 if a comes before b, 0 if they are the same, and -1 if a comes after b.
B) It must return -1 if a comes before b, 0 if they are the same, and 1 if a comes after b.
C) It must return a positive value if a comes before b, 0 if they are the same, and a negative value if a comes after b.
D) It must return a negative value if a comes before b, 0 if they are the same, and a positive value if a comes after b.

Free

Multiple Choice

Q 109Q 109

Complete the following code that is intended to provide a comparator interface that will be used to create an object that implements the Comparator interface so that object can compare Auto objects. ___________________________
{
Int compare(Auto a, Auto
A) public class Comparator
B) public class Comparator implements Comparator
B); }
C) public interface Auto
D) public interface Comparator

Free

Multiple Choice