Question 1

Consider the sort method for selection sort shown below: public static void sort (int[]A) An exception would occur

Accepted Answer

The loop starts at index 1, so the first element (index 0) is not considered in the sorting process.

Question 2

Consider the sort method shown below for selection sort: public static void sort (int[]A) An exception would occur.

Accepted Answer

The sort would produce correct results.

Question 3

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

Accepted Answer

If each of the n elements is visited n times, the total number of visits is n multiplied by n, which equals n^2.

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?

Accepted Answer

In big-Oh notation, we consider the term with the highest degree, which is n^3 in this case. Therefore, the order is O(n^3).

Question 5

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

Accepted Answer

Selection sort places the smallest element not yet placed in prior iterations in the correct location.

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?

Accepted Answer

The total number of visits is the sum of the first n natural numbers, which is given by the formula n(n+1)/2.

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

Accepted Answer

The answer of Consider the swap method shown below from...

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?

Accepted Answer

Doubling the number of elements in an O(n^3) algorithm increases the number of visits by a factor of 2^3, which is 8.

Question 9

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

Accepted Answer

The answer of After 9 iterations of selection sort working...

Question 10

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

Accepted Answer

After one iteration of selection sort, the smallest element is placed at the beginning of the array, meaning one 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) (int i = 0; i < a.length - 1; i++)

Accepted Answer

The correct loop structure for selection sort in descending order is to iterate from the start to the second last element, hence option A is correct.

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

Accepted Answer

The correct answer is A because the maximumPosition method should return the index of the largest element in the range from index from to the end of the array. So, the code should compare each element in the range with the current maximum and update the maximum if a larger element is found.

Question 13

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

Accepted Answer

The answer of After 5 iterations of selection sort working...

Question 14

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

Accepted Answer

The performance of an algorithm is most closely related to the total number of element visits, as this typically reflects the algorithm's time complexity and efficiency.

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?

Accepted Answer

Using the Random class to generate array elements is efficient because it automates the process of creating different sets of elements for each run, ensuring variability and saving time compared to manual entry or pre-defined sets.

Question 16

What type of algorithm places elements in order?

Accepted Answer

Sorting algorithms are specifically designed to arrange elements in a particular order, such as ascending or descending.

Question 17

Consider the sort method shown below for selection sort: public static void sort(int[]A) An exception would occur.

Accepted Answer

The sort would work, but run one more iteration.

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

Accepted Answer

In big-Oh notation, we ignore the coefficients of the terms and all lower order terms to focus on the term with the highest growth rate.

Question 19

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

Accepted Answer

In selection sort, after the 9th iteration, the largest unsorted element is placed in its correct position, leaving the 10th element automatically sorted.

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 = ____________________________;

Accepted Answer

The expression needed to complete the code segment so that it calculates the running time elapsed is System.currentTimeMillis() - start. This expression subtracts the start time from the current time, giving the running time in milliseconds.

Quiz 14: Sorting and Searching