Chapter 11 Recursion – absolute java test bank

Download  file with the answers

Chapter 11 Recursion - absolute java test bank

1 file(s)   106.44 KB

Not a member!
Create a FREE account here to get access and download this file with answers

Chapter 11
Recursion
 Multiple Choice
1) A recursive method is one that:
(a) Returns a value
(b) Initializes a set of variables
(c) Returns no value
(d) Invokes itself

2) All recursive methods must have a/an:
(a) starting case
(b) intermediate case
(c) stopping case
(d) none of the above

3) Pick the best answer
(a) Recursive methods may include a recursive call
(b) Recursive methods may not use iteration
(c) Recursive methods must include a recursive call
(d) none of the above

4) Recursion is:
(a) the ability of a program to repeat a block of code
(b) the ability of a method to call itself
(c) the ability of a method to call smaller methods
(d) the ability of a method to implement factorials

5) Regarding recursion, if a base case is never reached the result is:
(a) infinite recursion
(b) iteration
(c) termination
(d) all of the above

6) Infinite recursion:
(a) will happen when there is no base case
(b) will not happen when there is a base case
(c) will not happen if we use subproblems
(d) none of the above

7) The underlying data structure used by the computer during recursion is a:
(a) queue
(b) linked list
(c) tree
(d) stack

8) The stack is a ________________ data structure.
(a) first in – first out
(b) last in – last out
(c) last in – first out
(d) none of the above

9) The portion of memory in which a recursive computation is stored is called a/an:
(a) stack frame
(b) activation record
(c) all of the above
(d) none of the above

10) During recursion, if the stack attempts to grow beyond its limit, a _____________ occurs.
(a) Stack underflow
(b) Stack overflow
(c) Recursive underflow
(d) Recursive overflow

11) A recursive solution can be preferable to an iterative solution because:
(a) recursive method calls are faster than iterative looping
(b) recursive solutions may be easier to understand than iterative ones
(c) recursion uses less memory than iteration
(d) iteration should be avoided.

12) All recursive methods have a/an ____________ equivalent method.
(a) Iterative
(b) Selective
(c) Inherited
(d) None of the above

13) The following code for the method factorial() applies to the next two questions:

public static double factorial (double n)
{
if (n == 0)
{
return 1;
}
else
{
return n * factorial(n-1);
}
}

What is the value returned when the integer 3 is the argument to the factorial method?
(a) 2
(b) 4
(c) 6
(d) 8

14) What is the value returned when the integer 5 is the argument to the factorial method?
(a) 15
(b) 50
(c) 100
(d) 120

15) When defining recursive valued methods you should:
(a) Ensure there is no infinite recursion.
(b) Ensure each stopping case returns the correct value for that case.
(c) Ensure that the final value returned by the method is the correct value.
(d) All of the above

16) When defining recursive void methods you should:
(a) Ensure there is no infinite recursion.
(b) Ensure that each stopping case performs the correct action for that case.
(c) Ensure that if all recursive calls perform their actions correctly, then the entire case performs correctly.
(d) All of the above

17) The order of magnitude of the binary search algorithm is:
(a) linear
(b) exponential
(c) logarithmic
(d) quadratic

 True/False
1) A method definition that includes a call to itself is said to be recursive.

2) When a recursive call is encountered, computation is temporarily suspended; all of the information needed to continue the computation is saved and the recursive call is evaluated.

3) A base case must include a recursive call.

4) To keep track of recursion most computer systems us a structure called a queue.

5) A stack is a last-in/first-out memory structure.

6) Activation records are used to implement recursion.

7) A recursively written method will usually run slower and use more storage than an equivalent iterative version.

8) A recursive method must never return a value.

9) Binary search is a divide and conquer algorithm.

10) The binary search algorithm is extremely slow compared to an algorithm that simply tries all array elements in order.

11) The binary search algorithm has worst-case running time that is logarithmic.

 Short Answer/Essay
1) Write a recursive method to compute the power of xn for non-negative n.
Answer:
public static int power(int x, int n)
{
if(n < 0) { System.out.println(“Illegal argument to power”); System.exit(0); } if(n > 0)
return (power(x, n-1) * x);
else
return(1); //base case
}
2) Write an iterative method to compute the power of xn for non-negative n.
Answer:
public static int iterativePower(int x, int n)
{
int result = 1;
if(n < 0)
{
System.out.println(“Illegal argument to power”);
System.exit(0);
}
for(int i = 1; i <= n; ++i) result = result * x; return result; } 3) How does the computer system handle a recursive method call? Answer: When the computer encounters a recursive call, it temporarily stops its computation, saves all the information it needs to continue the computation later on, and proceeds to evaluate the recursive call. When the recursive call is completed, the computer returns to finish the outer computation. 4) Write a recursive method to print a string backwards. Answer: public static void writeBackwards(String s, int size) { if(size >0)
{
System.out.print(s.substring(size-1, size));
writeBackwards(s, size-1);
}
}
5) Write an iterative method to print a string backwards.
Answer:
public static void iterativeBackwards(String s)
{
for(int i = s.length()-1; i >= 0; i–)
System.out.print(s.charAt(i));
}
6) Write a recursive method to compute the factorial of a number.
Answer:
public static int factorial(int n)
{
if(n < 0)
{
System.out.println(“Sorry negative numbers not allowed.”);
System.exit(0);
}
if(n == 1) //base case
return(1);
else
return (n * factorial(n-1));
}
7) Write an iterative method to compute the factorial of a number.
Answer:
public static int iterativeFactorial(int n)
{
if(n < 0)
{
System.out.println(“Sorry negative numbers not allowed.”);
System.exit(0);
}

int result = 1;
for(int i = 1; i <= n; ++i)
{
result = result * i;
}
return result;
}
8) Explain the concept of divide and conquer.
Answer: Divide and conquer is a simple concept that involves breaking a problem into sub problems until the problem diminishes to a simple base case.
9) Explain how a sequential search works.
Answer: A sequential search works by examining every element in an array sequentially until the searched for key is located.
10) Explain how the binary search works.
Answer: Binary search works on arrays that are ordered. It computes the midpoint of the array and determines which half the search key lies in. It continues in this manner until either the search key is located or not found.
11) What is a base case?
Answer: A base case is a special case of a recursive solution that does not include a recursive call.
12) What are the criteria you must consider when formulating a recursive solution?
Answer: When formulating a recursive solution, you should ask yourself:
How can the problem be defined as a smaller problem of the same type?
How does each recursive call diminish the size of the problem?
What is the base case?
As the problem size diminishes, is the base case ever reached?

13) What is an activation record?
Answer: An activation record contains a methods local environment at the time of the call to the method.
14) What are the two base cases for a recursive binary search algorithm?
Answer: One base case for the recursive binary search algorithm is the key not found case in which the index of the first element of the array is greater than the index of the last element of the array. The second base case for the recursive binary search algorithm is when the key is found, which is represented by the key being equal to the value in the array at the current midpoint.
15) What are two factors that contribute to the inefficiency of some recursive solutions?
Answer: One factor that contributes to the inefficiency of some recursive solutions is the overhead associated with the recursive call. The other factor is the inherent inefficiency of some recursive algorithms.
16) What is a stack overflow?
Answer: A stack overflow is an error condition that occurs when too many recursive calls have been invoked depleting the stack space. A common cause of stack overflow is infinite recursion.