Deck 13: Recursion, Complexity, and Searching and Sorting

Question 1

Given two methods that perform the same task, the one that is quadratic is preferable to the one that is linear.

Answer 1

False

Question 2

Complexity analysis is concerned with determining an algorithm's efficiency.

Answer 2

True

Question 3

The call stack contains, among other things, the method's local variables.

Answer 3

False

Question 4

A large storage area known as a(n) activation record is created at program startup. ____________________

Question 5

In a(n) infinite recursion, the algorithm never reaches its stopping state. ____________________

Question 6

Recursion is measured by looking at how the run time and memory usage of an algorithm vary as a function of the quantity of data processed.

Question 7

In order to use a(n) binary search, the list must be sorted in ascending order. ____________________

Question 8

Computer scientists use expressions such as O(n) to express the linear relationship between an array's length and the execution time.

Question 9

Given a recursive definition of some process, it is usually easy to write a recursive method that implements it.

Question 10

A(n) ____ algorithm is one that refers to itself.

A) recursive
B) iterative
C) complex
D) infinite

Question 11

Using a binary search, finding a value from a list of a million entries involves at most 20 steps.

Question 12

In a linear equation, the best-, worst-, and average-case behaviors are O(1).

Question 13

A recursive step, in which the method calls itself, must ____.

A) include a call to the method
B) be tail-recursive
C) include a binary search algorithm
D) eventually lead to the stopping state

Question 14

The big-O value O(1) is named logarithmic. ____________________

Question 15

A recursive method must have a well-defined ____.

A) factorial
B) recursive step
C) stopping state
D) stack

Question 16

Recursion and iteration can never be used in place of each other.

Question 17

sum(n) =n+sum(n-1), where n>1 is an example of a(n) ____ algorithm.

A) recursive
B) iterative
C) complex
D) infinite

Question 18

When a method returns, its activation record is removed from the top of the stack.

Question 19

sum(n) =1+2+3+...+n, where n>1 is an example of a(n) ____ algorithm.

A) recursive
B) iterative
C) complex
D) infinite

Question 20

Because the summation algorithm must visit each number in the array, no matter how the numbers are ordered, the algorithm is always linear. ____________________

Question 21

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

A) stack
B) merge
C) activation record
D) big-O

Question 22

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

Question 23

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.

Question 24

The ____ search algorithm is O(log n).

A) binary
B) linear
C) recursive
D) iterative

Question 25

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

Question 26

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

Question 27

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

Question 28

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

Question 29

____ is an extra array used during the merge process.

A) mergeSortHelper
B) tempSpace
C) copyBuffer
D) mergeBuffer

Question 30

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.

Question 31

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

A) Mondrian
B) fractal
C) abstract
D) Euclidean

Question 32

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

Question 33

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

Question 34

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

Question 35

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

A) complex
B) iterative
C) infinite
D) tail-recursive

Question 36

The constant big-O value is ____.

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

Question 37

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

Question 38

The logarithmic big-O value is ____.

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

Question 39

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

Question 40

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

A) quickSort
B) binarySort
C) mergeSort
D) bubbleSort

Question 41

Identify the letter of the choice that best matches the phrase or definition.
a.Activation record
b.Stack
c.Quadratic
d.Exponential
e.copyBuffer
When a method returns, its activation record is removed from the top of the ____.

Question 42

The big-O value O(n) is named ____________________.

Question 43

Identify the letter of the choice that best matches the phrase or definition.
a.Activation record
b.Stack
c.Quadratic
d.Exponential
e.copyBuffer
The name of the big-O value O(2 to the nth power).

Question 44

In a quicksort algorithm, the middle of an array is called the ____________________.

Question 45

Identify the letter of the choice that best matches the phrase or definition.
a.Activation record
b.Stack
c.Quadratic
d.Exponential
e.copyBuffer
Contains, among other things, the value returned by the method.

Question 46

Identify the letter of the choice that best matches the phrase or definition.
a.Activation record
b.Stack
c.Quadratic
d.Exponential
e.copyBuffer
The name of the big-O value O(n squared).

Question 47

Identify the letter of the choice that best matches the phrase or definition.
a.Activation record
b.Stack
c.Quadratic
d.Exponential
e.copyBuffer
During the merge sort process, smaller items are copied to here.