Introduction to C++ Programming

1 Which of the following statements are true?

A. Every recursive function must have a base case or a stopping condition.

B. Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.

C. Infinite recursion can occur if recursion does not reduce the problem in a manner that allows it to eventually converge into the base case.

D. Every recursive function must have a return value.

E. A recursive function is invoked differently from a non-recursive function.

2 Fill in the code to complete the following function for computing factorial.

   /** Return the factorial for a specified index */
   long factorial(int n)
   {
     if (n == 0) // Base case
       return 1;
     else
       return _____________; // Recursive call
   }

A. n * (n - 1)

B. n

C. n * factorial(n - 1)

D. factorial(n - 1) * n

3 Analyze the following recursive function.

   long factorial(int n)
   {
     return n * factorial(n - 1);
   }

A. Invoking factorial(0) returns 0.

B. Invoking factorial(1) returns 1.

C. Invoking factorial(2) returns 2.

D. Invoking factorial(3) returns 6.

E. The function runs infinitely and runs out of memory.

4 Which of the following statements are true?

A. The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series.

B. The Fibonacci series begins with 1 and 1, and each subsequent number is the sum of the preceding two numbers in the series.

C. The Fibonacci series begins with 1 and 2, and each subsequent number is the sum of the preceding two numbers in the series.

D. The Fibonacci series begins with 2 and 3, and each subsequent number is the sum of the preceding two numbers in the series.

5 Fill in the code to complete the following function for computing a Fibonnaci number.

   long fib(long index)
   {
     if (index == 0) // Base case
       return 0;
     else if (index == 1) // Base case
       return 1;
     else // Reduction and recursive calls
       return __________________;
   }

A. fib(index - 1)

B. fib(index - 2)

C. fib(index - 1) + fib(index - 2)

D. fib(index - 2) + fib(index - 1)

6 In the following function, what is the base case?

int xFunction(int n)
{
   if (n == 1)
     return 1;
   else
     return n + xFunction(n - 1);
}

A. n is 1.

B. n is greater than 1.

C. n is less than 1.

D. no base case.

7 What is the return value for xFunction(4) after calling the following function?

int xFunction(int n)
{
   if (n == 1)
     return 1;
   else
     return n + xFunction(n - 1);
}

A. 12

B. 11

C. 10

D. 9

8 Fill in the code to complete the following function for checking whether a string is a palindrome.

bool isPalindrome(const char * const s)
{
   if (strlen(s) <= 1) // Base case
     return true;
   else if _____________________________ // Base case
     return false;
   else
     return isPalindrome(substring(s, 1, strlen(s) - 2));
}

A. (s[0] != s[strlen(s) - 1])

B. (s[0] == s[strlen(s) - 1])

C. (s[0] <> s[strlen(s) - 1])

D. (s[0] = s[strlen(s) - 1])

9 Analyze the following code:

   #include <iostream>
   using namespace std;

   void xFunction(int x[], int length)
   {
     cout << " " << x[length - 1];
     xFunction(x, length - 1);
   }

   int main()
   {
     int x[] = {1, 2, 3, 4, 5};
     xFunction(x, 5);
   }

A. The program displays 1 2 3 4 6.

B. The program displays 1 2 3 4 5 and then raises an ArrayIndexOutOfBoundsException.

C. The program displays 5 4 3 2 1.

D. The program displays 5 4 3 2 1 and then raises an ArrayIndexOutOfBoundsException.

10 Fill in the code to complete the following function for checking whether a string is a palindrome.

bool isPalindrome(const char * const s, int low, int high)
{
   if (high <= low) // Base case
     return true;
   else if (s[low] != s[high]) // Base case
     return false;
   else
     return ____________________________;
}

bool isPalindrome(const char * const s)
{
   return isPalindrome(s, 0, strlen(s) - 1);
}

A. isPalindrome(s)

B. isPalindrome(s, low, high)

C. isPalindrome(s, low + 1, high)

D. isPalindrome(s, low, high - 1)

E. isPalindrome(s, low + 1, high - 1)

11 Fill in the code to complete the following function for sorting a list.

void sort(char list[], int high)
{
   if (high > 1)
   {
     // Find the largest element and its index
     int indexOfMax = 0;
     char max = list[0];
     for (int i = 1; i <= high; i++)
     {
       if (list[i] > max)
       {
         max = list[i];
         indexOfMax = i;
       }
     }

     // Swap the largest with the last element in the list
     list[indexOfMax] = list[high];
     list[high] = max;

     // Sort the remaining list
     sort(list, high - 1);
   }
}

void sort(char list[])
{
   ____________________________;
}

void sort(double[] list) {
   ___________________________;
}

A. sort(list)

B. sort(list, strlen(list))

C. sort(list, strlen(list) - 1)

D. sort(list, strlen(list) - 2)

12 Fill in the code to complete the following function for binary search.

int binarySearch(const int list[], int key, int low, int high)
{
   if (low > high) // The list has been exhausted without a match
     return -low - 1; // Return -insertion point - 1

   int mid = (low + high) / 2;
   if (key < list[mid])
     return binarySearch(list, key, low, mid - 1);
   else if (key == list[mid])
     return mid;
   else
     return binarySearch(list, key, mid + 1, high);
}

int binarySearch(const int list[], int key, int size)
{
   int low = 0;
   int high = size - 1;
   return __________________________;
}

A. binarySearch(list, key)

B. binarySearch(list, key, low + 1, high - 1)

C. binarySearch(list, key, low - 1, high + 1)

D. binarySearch(list, key, low, high)

15 Analyze the following two programs:

A:

   void xFunction(int length)
   {
     if (length > 1)
     {
       cout << (length - 1) << " ";
       xFunction(length - 1);
     }
   }

   int main()
   {
     xFunction(5);
   }

B:
   public static void xFunction(int length)
   {
     while (length > 1)
     {
       cout << (length - 1) << " ";
       xFunction(length - 1);
     }
   }

   int main()
   {
     xFunction(5);
   }

A. The two programs produce the same output 5 4 3 2 1.

B. The two programs produce the same output 1 2 3 4 5.

C. The two programs produce the same output 4 3 2 1.

D. The two programs produce the same output 1 2 3 4.

E. Program A produces the output 4 3 2 1 and Program B prints 4 3 2 1 1 1 .... 1 infinitely.

16 Which of the following statements are true?

A. Recursive functions run faster than non-recursive functions.

B. Recursive functions usually takes more memory space than non-recursive functions.

C. A recursive function can always be replaced by a non-recursive function.

D. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve.

Introduction to C++ Programming, Y. Daniel Liang

Chapter 8 Recursion