Question 1

In a quicksort algorithm, the iterative approach requires a data structure called a(n) ____.
A) stack
B) merge
C) activation record
D) big-O

Accepted Answer

The iterative approach in quicksort algorithm requires a stack data structure to keep track of the subarrays that still need to be sorted. The stack is used to store the starting and ending indices of the subarrays.

Question 2

A(n) ____ is a GUI control that allows the user to select a value within a range of values.
A) buffer
B) slider
C) degree
D) option button

Accepted Answer

A slider is a GUI control that allows the user to select a value within a given range. It is typically represented as a horizontal or vertical bar with a draggable indicator that moves along the bar as the user moves it. The position of the indicator corresponds to a specific value within the range, which can be used to control various aspects of the application.

Question 3

FIGURE 13-2 
-Leslie knows that the array will be sorted ____.
A) if the tag at the left end of the array is greater than the tag at the right end of the array.
B) when the pivot is 0
C) when all of the subparts contain a single value
D) all of the above.

Accepted Answer

An array is considered sorted when it has been divided into subparts such that each subpart contains a single value, indicating that the sorting algorithm has successfully organized the array into a sequence where each element is in its correct position. Options A and B do not necessarily indicate a sorted array; the position of a single tag or a pivot value of 0 does not guarantee the entire array is sorted.

Question 4

The ____ search algorithm is O(log n).
A) binary
B) linear
C) recursive
D) iterative

Accepted Answer

The binary search algorithm has O(log n) time complexity, which is more efficient than linear or recursive search algorithms. Iterative search is not a specific type of algorithm and can refer to both linear and binary search, so it cannot be considered the best choice.

Question 5

execution time = O(n) is an example of big-O ____________________.

Accepted Answer

The answer of execution time = O(n) is an example...

Question 6

When a method is called, an activation ____________________ is added to the top of the call stack.

Accepted Answer

The answer of When a method is called, an activation...

Question 7

A(n) ____ search starts at the beginning of an array and looks at consecutive elements until the search value is located or the end of the array is reached.
A) binary
B) linear
C) recursive
D) iterative

Accepted Answer

A linear search, also known as sequential search, checks every element in the array until the desired value is found or the end of the array is reached. It is a simple search algorithm and is best used for small arrays or unsorted arrays.

Question 8

FIGURE 13-1 
-Figure 13-1 above shows an example of ____.
A) the trace of an iterative method
B) a big-O notation
C) activation records on the call stack
D) infinite recursion

Accepted Answer

The figure shows the activation records on the call stack, which is typically used to keep track of function calls and their parameters in a program's memory during execution. It does not depict an iterative method, big-O notation, or infinite recursion.

Question 9

____ is an extra array used during the merge process.
A) mergeSortHelper
B) tempSpace
C) copyBuffer
D) mergeBuffer

Accepted Answer

The answer of ____ is an extra array used during...

Question 10

mergeSortHelper is a private method that ___.
A) implements the merging process
B) is called by clients
C) hides the extra parameter required by recursive calls
D) all of the above.

Accepted Answer

mergeSortHelper is typically a private method used internally within a class to manage the recursive calls of the merge sort algorithm, often hiding extra parameters from the public interface.

Question 11

A(n) ____ object uses a highly repetitive or recursive pattern.
A) Mondrian
B) fractal
C) abstract
D) Euclidean

Accepted Answer

A fractal object is characterized by its highly repetitive or recursive pattern, in which smaller and smaller details within the object are identical or similar to the overall shape. Mondrian, abstract, and Euclidian do not have this specific characteristic.

Question 12

A ____ sort algorithm computes the middle position of an array and recursively sorts its left and right subarrays, merges to two sorted subarrays into a single sorted array, then stops when the subarrays can no longer be subdivided.
A) stack
B) merge
C) quick
D) recursive

Accepted Answer

The description of the algorithm matches the merge sort algorithm. The other options (stack, quick, recursive) do not accurately describe the algorithm.

Question 13

____________________ analysis is used to answer the question: what is the effect on the method of increasing the quantity of data processed?

Accepted Answer

The answer of ____________________ analysis is used to answer the...

Question 14

Jarrod knows that if the length of his list is 4 to 7, the maximum number of steps needed to do a binary search is ____.
A) 1
B) 3
C) 4
D) 7

Accepted Answer

The maximum number of steps needed for a binary search is log(base 2) n. In this case, n can range from 4 to 7, so the maximum possible value of log(base 2) n is log(base 2) 7, which is approximately 2.8. Since we can't have a fractional number of steps, we round up to the nearest integer, which is 3. Therefore, the maximum number of steps needed for a binary search in this scenario is 3.

Question 15

An algorithm is ____ if no work is done in the algorithm after a recursive call.
A) complex
B) iterative
C) infinite
D) tail-recursive

Accepted Answer

Tail recursion is a technique where the last operation of the recursive function is a recursive call. This means that no operation is executed after the recursive call, making it easier for the compiler to optimize and potentially avoid stack overflow errors. Therefore, a tail-recursive algorithm is one in which no work is done after a recursive call.

Question 16

The constant big-O value is ____.
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)

Accepted Answer

The constant big-O value, O(1), means that the algorithm has a constant runtime regardless of the input size. This is the best choice because it is the fastest option and does not depend on the input size. Option B and D have linear or superlinear runtimes which can be slow for large inputs, and option C has a logarithmic runtime which is slower than constant time.

Question 17

The general idea behind a ____ algorithm is to break an array into two parts, then rearrange the elements so the larger values are at one end and the smaller values at the other, then repeat until the subparts contain a single value.
A) linear
B) complex
C) binary
D) quicksort

Accepted Answer

The description matches the implementation of the quicksort algorithm.

Question 18

The logarithmic big-O value is ____.
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)

Accepted Answer

The logarithmic big-O value is represented by O(log n). As n increases, the number of operations required to complete a task increases at a slower rate, making it more efficient than O(n) or O(n log n). Therefore, C is the best choice.

Question 19

A stack overflow error occurs when ____.
A) a user terminates a program early
B) the Java interpreter runs out of memory
C) an exception is thrown
D) an algorithm reaches its stopping state

Accepted Answer

A stack overflow error occurs when the Java interpreter runs out of memory. This can happen when a method calls itself recursively without a base case, causing an infinite loop that fills up the stack memory.

Question 20

FIGURE 13-2 
-Figure 13-2 above shows subarrays generated during calls of ____.
A) quickSort
B) binarySort
C) mergeSort
D) bubbleSort

Accepted Answer

The subarrays generated in Figure 13-2 are typical of those generated during calls of mergeSort, which is a divide-and-conquer algorithm that recursively splits the given array into smaller sorted subarrays before merging them back together to obtain the final sorted array. The other sorting algorithms listed, quickSort, binarySort, and bubbleSort, do not typically generate subarrays in the same way as mergeSort.

Quiz 13: Recursion, Complexity, and Searching and Sorting

In a quicksort algorithm, the iterative approach requires a data structure called a(n) ____.

A(n) ____ is a GUI control that allows the user to select a value within a range of values.

FIGURE 13-2 -Leslie knows that the array will be sorted ____.

The ____ search algorithm is O(log n) .

execution time = O(n) is an example of big-O ____________________.

When a method is called, an activation ____________________ is added to the top of the call stack.

A(n) ____ search starts at the beginning of an array and looks at consecutive elements until the search value is located or the end of the array is reached.

FIGURE 13-1 -Figure 13-1 above shows an example of ____.

____ is an extra array used during the merge process.

mergeSortHelper is a private method that ___.

A(n) ____ object uses a highly repetitive or recursive pattern.

A ____ sort algorithm computes the middle position of an array and recursively sorts its left and right subarrays, merges to two sorted subarrays into a single sorted array, then stops when the subarrays can no longer be subdivided.

____________________ analysis is used to answer the question: what is the effect on the method of increasing the quantity of data processed?

Jarrod knows that if the length of his list is 4 to 7, the maximum number of steps needed to do a binary search is ____.

An algorithm is ____ if no work is done in the algorithm after a recursive call.

The constant big-O value is ____.

The general idea behind a ____ algorithm is to break an array into two parts, then rearrange the elements so the larger values are at one end and the smaller values at the other, then repeat until the subparts contain a single value.

The logarithmic big-O value is ____.

A stack overflow error occurs when ____.

FIGURE 13-2 -Figure 13-2 above shows subarrays generated during calls of ____.