Question 1

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

Accepted Answer

In the worst case, a linear search needs to check every element in the array to locate the value. Therefore, the time complexity of linear search is proportional to the size of the array, which is O(n). Choices A, B, and D are incorrect because they suggest a time complexity that is not applicable to linear search.

Question 2

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

Accepted Answer

Both quicksort and mergesort are based on the divide and conquer strategy, as they divide the input into smaller subproblems, solve them recursively, and combine the solutions to obtain the final result. Insertion sort, on the other hand, does not use this strategy and simply iterates through the input list one element at a time.

Question 3

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

Accepted Answer

Plugging in the values for N=1024, S1U1B1=16 (assuming a typical cache size), and n=1 (as we are performing the sorting for the entire array at once), we get:
1024 + 5(1)(10)(16)(1 + log2(1024/16)) = 1024 + 5(160)(6) = 105,024
Therefore, the number of visits needed is 52,224 (rounded to the nearest integer), which is option D.

Question 4

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²

Accepted Answer

In the worst case scenario, the element being searched for may not be present in the array, resulting in n comparisons being made in order to determine this. Thus, the worst case scenario requires n visits to the array.

Question 5

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

Accepted Answer

Quicksort's worst-case behavior occurs when the data is sorted in either ascending or descending order, as pivot selection in these cases could lead to unbalanced partitions and significantly increase the run-time. When the data is randomly initialized, quicksort performs efficiently on average.

Question 6

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

Accepted Answer

Quicksort is the sorting algorithm that starts by partitioning the array and selecting a pivot element. It has an average case time complexity of O(n log n) and is widely used in practice due to its efficiency.

Question 7

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

Accepted Answer

When the array length is less than 7, the sort method in the Java Arrays class uses Insertion Sort. This is because Insertion Sort is efficient for small arrays and has a low overhead when compared to other algorithms such as Merge Sort or Quicksort. Therefore, the best choice would be option D, as it is the most efficient for small arrays.

Question 8

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

Accepted Answer

Using the complexity of selection sort, we can calculate an estimate of how long it would take to sort 1,000,000 elements: O(n²) * 1,000,000 = O(1,000,000^2) However, this is just an estimate and doesn't take into account the specifics of the computer being used, potential optimizations, or the actual data being sorted. Therefore, we can't accurately predict the exact amount of time it would take to sort 1,000,000 elements. Therefore, the best choice is D) 4,000,000, which is the answer that corresponds to the highest estimate of the actual time it might take.

Question 9

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.

Accepted Answer

The answer of Assume we are using quicksort to sort...

Question 10

Merge sort is a(n) ____ algorithm. A) O(n) B) O(n log(n)) C) O(n²) D) O(log n)

Accepted Answer

Merge sort has a time complexity of O(n log(n)), making it a better choice than O(n) or O(log n) algorithms. The option C does not exist in the standard notation for time complexity.

Question 11

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

Accepted Answer

Since merge sort has a O(n log n) complexity, if we increase the input size by a factor of 1024 (i.e. 1024 times), the time complexity will increase by a factor of 10 (log base 2 of 1024 is 10). Therefore, it will take approximately 1024*10 = 8192 times longer to sort 1,048,576 elements than it does to sort 1024 elements, which is option C.

Question 12

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

Accepted Answer

Insertion sort is the only sort in the textbook that has a best case running time of θ(n) when the data is already sorted. Quicksort has a best case of θ(n log n) and Selection sort has a best case of θ(n^2).

Question 13

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

Accepted Answer

The answer of In the worst case, quicksort is a(n)...

Question 14

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

Accepted Answer

The appropriate big-Oh notation for merge sort is the term with the highest growth rate. In this case, the highest growth rate term is n logS1U1B12S1U1B0S1U1B1 S1U1B0n since it is the only term with both n and logS1U1B1. Therefore, the answer is D.

Question 15

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.

Accepted Answer

If there are 2,000,000 entries and they are evenly distributed across the phone directory, then on average we would need to search half of them, or 1,000,000, before finding the desired address.

Question 16

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

Accepted Answer

Merge sort is the only sort in the textbook that has a worst-case running time of O(n log(n)). Quick sort has a worst-case running time of O(n^2) in certain scenarios (such as with already sorted data), and selection sort has a worst-case running time of O(n^2) regardless of the input data.

Question 17

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.

Accepted Answer

The answer of Assume we are using quicksort to sort...

Question 18

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

Accepted Answer

The code is using a linear search which means it is sequentially checking each element in the array until it finds the target value or exhausts all elements.

Question 19

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

Accepted Answer

The answer of A version of which sort algorithm is...

Question 20

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

Accepted Answer

Quicksort's strategy places the pivot element in its final correct location after partitioning, meaning it is in the position it will permanently occupy in the sorted array.

Quiz 14: Sorting and Searching

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

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

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?

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?

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

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

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

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?

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?

Merge sort is a(n) ____ algorithm.

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?

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

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

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?

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?

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

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?

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 version of which sort algorithm is used in the sort method in the Java Arrays class?

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?