Ch14 Full Test Bank - Problem Solving With Recursion

Chapter 14 - Problem Solving with Recursion

True/False (10)

1. The Towers of Hanoi problem cannot be solved iteratively.
2. Computing the nth Fibonacci number is more efficient with iteration than with recursion.
3. The first rule of the Tower of Hanoi problem states that each disk you move must be a bottom-most disk.
4. The solution to the Towers of Hanoi is O(2ⁿ).
5. The definition of an identifier includes the word identifier.
6. An expression such as a + b c is called infix notation.
7. The expression a + b c written in postfix notation is a b + c
8. An iterative solution to the Towers of Hanoi problem moves fewer disks than the recursive solution.
9. The n-queens problem requires an n x n chessboard and uses the rules of chess to create a solution.
10. The rules of a language are called its grammar.

Short Answer (8)

1. Explain why the recursive Fibonacci program is so inefficient.
2. Provide the algorithm for the recursive solution to compute the nth Fibonacci number.

Algorithm Fibonacci (n)
if (n <= 1)
return 1
else
return Fibonacci(n-1) + Fibonacci(n-2)

1. Provide the Java code for the iterative solution to compute the nth Fibonacci number.

static int IterFibonacci (int n)

{

int previous = 0;

int next = 1;

int result = 0;

for (int i = 0; i < n; i++)

{

result = previous + next;

previous = next;

next = result;

}

return result;

}

1. List the three rules for the Tower of Hanoi problem.

1. Move one disk at a time. Each disk you move must be a topmost disk.

2. No disk may rest on top of a disk smaller than itself.

3. You can store disks on the second pole temporarily, as long as you observe rules 1 and 2.

1. Convert the following to postfix: a + b c / d
2. Convert the following to infix: a b c d / +
3. Convert the following to prefix: (a + b) c
4. Assume a = 2; b = 3; c = 18; and d = 9.

What is the value of the following postfix expression: a b + c d / -

Multiple Choice (22) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. The solution to the Towers of Hanoi starting with three poles requires
   1. 7 moves
   2. 3 moves
   3. 6 moves
   4. 9 moves
2. The solution to the Towers of Hanoi problem
   1. grows exponentially
   2. grows linearly
   3. grows quadratically
   4. is independent of the number of discs
3. The solution to the Towers of Hanoi problem with n discs requires
   1. 2ⁿ – 1 moves
   2. 2ⁿ moves
   3. 2ⁿ + 1 moves
   4. n2 -1 moves
4. The solution to the Towers of Hanoi problem with 20 discs requires approximately
   1. 1,000,000 moves
   2. 1,000 moves
   3. 10,000 moves
   4. 1,000,000,000 moves
5. A Java identifier can be defined by the rule
   1. <identifier> = <letter> |<identifier><letter> | <identifier><digit>
   2. <identifier> = <digit><digit><letter> | <identifier><letter> | <identifier><digit>
   3. <identifier> = <digit><letter><identifier> | <letter><letter> | <identifier><digit>
   4. all of the above
6. A special case of indirect recursion, where Method A calls Method B, and Method B calls Method A, is called ____.
   1. mutual recursion
   2. infinite recursion
   3. backtrack recursion
   4. all of the above
7. A(n) ____ allows you to check whether a given string is in a language.
   1. recognition algorithm
   2. prefix expression
   3. exhaustive search
   4. indirect recursion algorithm
8. A(n) ____ technique checks all possible choices for a solution.
   1. brute-force
   2. mutual recursion
   3. indirect recursion
   4. exhaustive recursion
9. Identify the prefix version of this infix expression: A B + C D
   1. + a b c d
   2. + a b c d
   3. + a b + c d
   4. + a b c d
10. Identify the postfix version of this infix expression: (a + b) (c / d)
    1. a b + c / d
    2. a b c d + /
    3. a b + c d /
    4. c d / a b +
11. What is the value of the following postfix expression: a b c + d –

Assume a = 10, b = 6, c = 2, and d = 5

• 1. 17
  2. -7
  3. 125
  4. None of the above.

1. What is the value of the following postfix expression: a b - c d / +

Assume a = 10, b = 6, c = 12, and d = 2

• 1. 10
  2. 6
  3. 12
  4. The answer cannot be determined

1. What is the value of the following postfix expression: a b - c - d / +

Assume a = 10, b = 6, c = 12, and d = 2

• 1. 10
  2. 6
  3. 12
  4. The answer cannot be determined

1. Provide the missing line of pseudocode:

isIdentifier(s: string): boolean

{

if (s is of length 1) // Base case

{

if (s is a letter)

return true

else

return false

}

else if (the last character of s is a letter or a digit)

//Provide this line of code

else

return false

}

• 1. return isIdentifier(s minus its last character)
  2. return isIdentifier(s)
  3. return s minus its last character
  4. None of the above

1. Convert the following prefix expression to infix: - a + b c / - d e + - f g h
   1. (a-b+c) (d-e) / (f-g+h)
   2. (a+b-c) (d+e) / (f-g-h)
   3. (a-b+c) (d/e) - (f-g+h)
   4. The expression cannot be converted
2. Convert the following prefix expression to infix: / - a b + - c d e
   1. ( (a-b) / ( (c-d) + e) )
   2. ( (a+b) / ( (c+d) + e) )
   3. ( (a/b) - ( (c+d) - e) )
   4. The expression cannot be converted
3. The efficiency for solving the Towers of Hanoi problem recursively is
   1. O(2ⁿ)
   2. O(n²)
   3. O(n)
   4. O(log n)
4. The rate of growth for the Towers of Hanoi problem as the number of disks increases is
   1. exponential
   2. quadratic
   3. linear
   4. constant
5. What is the value of this postfix expression: 1 2 3 4 + 5
   1. 70
   2. 19
   3. 15
   4. This is not a valid postfix expression
6. Convert the following infix expression to postfix: x ^ y / (5 z) + 10
   1. x y ^ 5 z / 10 +
   2. y x ^ 5 z 10 / +
   3. x y 5 z ^ / 10 +
   4. x y z 5 ^ / 10 +
7. Convert the following infix expression to postfix: ( (8-2) (7+3) ) ^ 2
   1. 8 2 – 7 3 + 2 ^
   2. 8 2 ^ 7 3 + 2 -
   3. 2 ^ 8 2 – 7 3 + +
   4. 8 2 – 7 3 + 2 ^
8. What is the value of this postfix expression: 1 2 3 + 4 + 5
   1. 70
   2. 19
   3. 15
   4. This is not a valid postfix expression