Deck 3: Recursion: the Mirrors

Question 1

A recursive method that computes the number of groups of k out of n things has the precondition that ______.

A)n is a positive number and k is a nonnegative number
B)n is a nonnegative number and k is a positive number
C)n and k are nonnegative numbers
D)n and k are positive numbers

Answer 1

C

Question 2

A ______ is a mathematical formula that generates the terms in a sequence from previous terms.

A)local environment
B)pivot item
C)base case
D)recurrence relation

Answer 2

D

Question 3

The factorial of zero is ______.

A)-1
B)0
C)1
D)2

Answer 3

C

Question 4

What would happen if a negative value is passed to a method that returns the factorial of the value passed to it?

A)the method will calculate the correct value for the factorial of the number
B)the method will calculate a negative value for the factorial of the number
C)the method would terminate immediately
D)an infinite sequence of recursive calls will occur

Question 5

In the box trace for a recursive method,a new box is created each time ______.

A)the method is called
B)the method returns a value
C)the object is created
D)the object is initialized

Question 6

In a recursive method that writes a string of characters in reverse order,the base case is ______.

A)a string with a length of 0
B)a string whose length is a negative number
C)a string with a length of 3
D)a string that is a palindrome

Question 7

Which of the following is NOT a precondition for an array that is to be sorted by a recursive binary search algorithm? (first is the index of the first item in the array,last is the index of the last item in the array,and SIZE is the maximum size of the array)

A)SIZE <= first
B)0 <= first
C)last <= SIZE - 1
D)anArray[first] <= anArray[first + 1] <= … <= anArray[last]

Question 8

How many bases cases will be required in a recursive solution that solves a problem by solving two smaller problems of the same type?

A)0
B)1
C)2
D)3

Question 9

A class method is defined as ______.

A)static
B)abstract
C)private
D)protected

Question 10

The base case for a recursive definition of the factorial of n is ______.

A)factorial (-1)
B)factorial (0)
C)factorial (1)
D)factorial (n - 1)

Question 11

The factorial of n is equal to ______.

A)n - 1
B)n - factorial (n-1)
C)factorial (n-1)
D)n * factorial (n-1)

Question 12

If the value being searched for by a recursive binary search algorithm is in the array,which of the following is true?

A)the algorithm cannot return a nonpositive number
B)the algorithm cannot return a nonnegative number
C)the algorithm cannot return a zero
D)the algorithm cannot return a negative number

Question 13

When you solve a problem by solving two or more smaller problems,each of the smaller problems must be ______ the base case than the original problem.

A)closer to
B)farther to
C)either closer to or the same "distance" from
D)either farther to or the same "distance" from

Question 14

The midpoint of a sorted array can be found by ______,where first is the index of the first item in the array and last is the index of the last item in the array.

A)first / 2 + last / 2
B)first / 2 - last / 2
C)(first + last)/ 2
D)(first - last)/ 2

Question 15

An array is a(n)______.

A)class
B)method
C)object
D)variable

Question 16

In a recursive solution,the ______ terminates the recursive processing.

A)local environment
B)pivot item
C)base case
D)recurrence relation

Question 17

In the box trace,each box roughly corresponds to a(n)______.

A)recursive relation
B)activation record
C)base case
D)pivot item

Question 18

In the box trace,each box contains all of the following EXCEPT ______.

A)the values of the references and primitive types of the method's arguments
B)the method's local variables
C)the method's class variables
D)a placeholder for the value returned by each recursive call from the current box
E)the value of the method itself

Question 19

Which of the following is a precondition for a method that accepts a number n and computes the nth Fibonacci number?

A)n is a negative integer
B)n is a positive integer
C)n is greater than 1
D)n is an even integer

Question 20

The number of ways to choose k out of n things is ______.

A)the number of ways to choose k - 1 out of n - 1 things
B)the number of ways to choose k out of n - 1 things
C)the sum of the number of ways to choose k - 1 out of n - 1 things and the number of ways to choose k out of n - 1 things
D)the product of the number of ways to choose k - 1 out of n - 1 things and the number of ways to choose k out of n - 1 things

Question 21

A recursive solution can have more than one base cases.

Question 22

In the recursive solution to the Towers of Hanoi problem,the number of disks to move ______ at each recursive call.

A)decreases by 1
B)increases by 1
C)decreases by half
D)increases by half

Question 23

The binary search algorithm can be applied to an unsorted array.

Question 24

A recursive solution that finds the factorial of n generates ______ recursive calls.

A)n-1
B)n
C)n+1
D)n*2

Question 25

In the Fibonacci sequence,which of the following integers comes after the sequence 1,1,2,3?

A)3
B)4
C)5
D)6

Question 26

An iterative method always calls itself.

Question 27

Every recursive method must have a base case.

Question 28

When constructing a recursive solution,you should assume that a recursive call's postcondition is true if its precondition is true.

Question 29

The base case for a recursive solution to the kth smallest item problem cannot be predicted in advance.

Question 30

A recursive solution solves a problem by solving a smaller instance of the same problem.

Question 31

A binary search starts at the beginning of the collection of items.

Question 32

For anArray = <2,3,5,6,9,13,16,19>,what is the value returned by a recursive binary search algorithm if the value being searched for is 10?

A)-1
B)0
C)1
D)10

Question 33

A recursive solution that finds the factorial of n always reduces the problem size by ______ at each recursive call.

A)1
B)2
C)half
D)one-third

Question 34

In the recursive solution to the kth smallest item problem,the problem size decreases by ______ at each recursive call.

A)1
B)at least 1
C)half
D)at least half

Question 35

A recursive binary search algorithm always reduces the problem size by ______ at each recursive call.

A)1
B)2
C)half
D)one-third

Question 36

A method that is declared as static is an object method.

Question 37

In a sorted array,the kth smallest item is given by ______.

A)anArray[k-1]
B)anArray[k]
C)anArray[SIZE-k]
D)anArray[SIZE+k]

Question 38

An iterative solution involves loops.

Question 39

For anArray = <2,3,5,6,9,13,16,19>,what is the value returned by a recursive binary search algorithm if the value being searched for is 6?

A)1
B)3
C)4
D)6

Question 40

Which of the following is a base case for a recursive binary search algorithm? (first is the index of the first item in the array,last is the index of the last item in the array,and mid is the midpoint of the array).

A)last > first
B)first > last
C)0 <= first
D)last <= SIZE-1

Question 41

Why do some compilers automatically replace tail recursion with iteration?

Question 42

What are the two factors which contribute to the inefficiency of some recursive solutions?

Question 43

What is the box trace?

Question 44

What is the base case for the recursive solution to the Towers of Hanoi problem?

Question 45

What is an activation record?

Question 46

Why does the Fibonacci sequence have two base cases? In other words,would it be possible to write a correct recursive Fibonacci method that has only one base case?

Question 47

Write a recursive method that takes 3 parameters: an integer array a,and two integers first and last.The method will find the largest value in a between indices first and last,inclusive.That is,it will return the largest value in the part of the array a[first..last] .You may assume that first  last.

Question 48

How does a sequential search work?

Question 49

What is a tail-recursive method?

Question 50

Suppose a program contains a recursive method findFibonacci(int n),which computes the n-th Fibonacci number.Even if we know that a client method will never call findFibonacci( )with the values 1 or 2 as arguments,why does the implementation of findFibonacci( )still need to have base cases?

Question 51

What is a base case?

Question 52

What are the four questions that must be considered when constructing a recursive solution?

Question 53

When is the base case value == anArray[mid] (where mid is the midpoint of the array)reached in a recursive binary search algorithm?

Question 54

When is the base case first > last (where first is the index of the first item in the array and last is the index of the last item in the array)reached in a recursive binary search algorithm?

Question 55

What elements are included in a method's local environment?

Question 56

What is a pivot item?

Question 57

Suppose sa is a sorted array of integer values,and we wish to search for a number target in this array.If sa contains n elements,and we use the binary search strategy,what is the approximate maximum number of comparisons necessary to determine that the value target is or is not in the array? How would your answer change if the array were not sorted?

Question 58

Write a recursive method that takes a String parameter and prints out the characters of the string in reverse order.

Question 59

What is a recurrence relation?

Question 60

What are the two base cases for a recursive binary search algorithm?