Name:     ID: 
 
Email: 

Chap8-2020  100 points

True/False  10 points
Indicate whether the statement is true or false.
 

 1. 
A recursive method without a base case leads to infinite recursion.
 

 2. 
Some problems are easier to solve recursively than iteratively.
 

 3. 
Merge sort and quick sort are more time efficient than insertion sort and selection sort.
 

 4. 
Recursion can be used when sorting an array of elements.
 

 5. 
A recursive sort typically divides the list into smaller sublists which are sorted recursively.
 

 6. 
The pivot value selected in a quick sort should be the smallest element in the list.
 

 7. 
A recursive method that doesn't return anything with result in infinite recursion.
 

 8. 
If method f1 calls method f2 calls method f3, we have indirect recursion.
 

 9. 
Traversing a maze is much easier to do iteratively than recursively.
 

 10. 
The recursive method to solve the Towers of Hanoi is usable only if the parameter for the number of disks is 7 or smaller.
 

Multiple Choice    4 points each
Identify the choice that best completes the statement or answers the question.
 

 11. 
For questions 11 – 12, use the following recursive method.
public int Rec (int x, int y)
{
      if (x == y)
                    return 0;
else
    return Rec (x-1, y) + 1;
}
If the method is called as Rec (8, 3), what is returned?  
a.
11
b.
8
c.
5
d.
3
e.
24
 

 12. 
Calling this method will result in infinite recursion if which condition below is initially true?
a.
(x = = y)
b.
(x != y)
c.
(x > y)
d.
(x < y)
e.
(x = = 0 && y != 0)
 

 13. 
int Rec(int x, int y)
{
  if(x == 0)
    return y;
  else
    return Rec(x - 1,  x + y);
}
what will be returned by the function call Rec(5,2)
a.
10
b.
17
c.
21
d.
24
e.
30
 

 14. 

  public int mystery(int a, int b)
{
        if (b == 0)        
            return 0;
        else if (b % 2 == 0)
            return mystery(a + a, b / 2);
        else                
            return mystery(a + a, b / 2) + a;
  }

What is the result of mystery (2, 25)?
a.
20
b.
25
c.
30
d.
40
e.
50
 

 15. 

  public int mystery(int a, int b)
{
        if (b == 0)        
            return 0;
        else if (b % 2 == 0)
            return mystery(a + a, b / 2);
        else                
            return mystery(a + a, b / 2) + a;
  }

What is the result of mystery (3, 35)?
a.
35
b.
70
c.
90
d.
100
e.
105
 

 16. 
Look at square numbers again:
square(1) = 1
square(N) = square(N-1) + 2N -1
Which Java method below successfully implements this definition?
a.
int square( int N )
{
  if ( N<1 )
  {
    return 1;
  }
  else
  {
    return N*N;
}
b.
int square( int N )
{
  if ( N==1 )
  {
    return 1;
  }
  else
  {
    return square(N-1) + 2*N - 1; 
  }
}
c.
int square( int N )
{
  if ( N=1 )
  {
    return 1;
  }
  else
  {
    return square(N-1) + 2*N - 1; 
  }
}
d.
int square( int N )
{
  if ( N==1 )
  {
    return 1;
  }
  else
  {
    return square(N); 
  }
}
e.
Non of the obove
 

 17. 
Look at square numbers one more time:

square(1) = 1
square(N) = square(N-1) + 2N -1
Assume the definition has been implemented correctly. How many activations will there be on the activation chain if main() calls square(5)?
a.
1
b.
3
c.
5
d.
7
e.
9
 

 18. 
Consider the following recursive method.
public int recur(int n)
{
   if (n <= 10)
      return n  *  2;
  else
     return recur(recur(n / 3));
} 
What is the value returned as a result of the call recur(27)?
a.
8
b.
9
c.
16
d.
18
e.
12
 

 19. 
public void MyRec(int n)
{
    if (n > 0)
        System.out.print(n);
        MyRec(n-1);
     else
        System.out.print(n); 
  }

What is the value returned as a result of the call MyRec(4)?

a.
3
b.
4
c.
4 3 2 1
d.
0 1 2 3 4
e.
4 3 2 1 0
 

 20. 
public static int mystery(int n)
{
   if (n == 0)
      return 1;
   else
      return 3 * mystery (n - 1);
}
Given the following method declaration, what value is returned as the result of the call mystery(5)?
a.
9
b.
18
c.
27
d.
81
e.
243
 

 21. 
public static int product(int n)
{
   if (n <= 1)
      return 1;
   else
      return n * product(n - 2);
}
Given the following method declaration, what value is returned as the result of the call product(5)?
a.
1
b.
10
c.
15
d.
25
e.
125
 

 22. 
public static int f(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else return f(n-1) + f(n-2);
}
Given the following method declaration, what value is returned as the result of the call f(5)?
a.
0
b.
1
c.
5
d.
8
e.
There is no result because of infinite recursion.
 

 23. 
public static int redo(int i, int j)
{
   if (i==0)
      return 0;
   else
      return redo( i / j ,  j) + 1;
}
Given the following method declaration, what will redo(82, 3) return?
a.
4
b.
5
c.
6
d.
7
e.
The method never returns due to infinite recursion
 

 24. 
public static boolean check(String s)
{
   return  (s.length() >= 2 &&  (s.charAt(0) == s.charAt(1) ||  check(s.substring(1) ) );
}

Given the following method declaration, this method will return true if and only if:
a.
The string s contains two or more of the same characters.
b.
The string s starts with two or more of the same characters.
c.
The string s contains two or more of the same character that are next to each other.
d.
 The string s ends with two or more of the same characters
e.
The methd will never be true
 

 25. 

public int func (int n)
        {
             if (n == 1)
                return 1;
             else
               return  func (n - 1);
        }

What is the output of this program when func(20)?
a.
1
b.
19
c.
20
d.
11
e.
non of the obove
 

 26. 

public static int equation (int a)
     {
        if (a <=5)
        return 12;
        else
        return equation (a-2)  *  equation(a-1);
     } 
What is the ourput of the program when equation(6)
a.
5
b.
125
c.
144
d.
169
e.
225
 

 27. 
public static int mystery (int a)
    {
     
     if (a < = 0)
            return 0;
     int x = mystery (a - 2);
          return  a + x;
    }
What will the otput if  a=3
a.
2
b.
3
c.
4
d.
5
e.
6
 

FRQ 24 points
 

 28. 
See Jotonce for FRQ
 



 
         Start Over