This set of Data Structure Multiple Choice Questions & Answers focuses on “Catalan Number using Dynamic Programming”.

1. Which of the following is NOT a Catalan number?

a) 1

b) 5

c) 14

d) 43

View Answer

Explanation: Catalan numbers are given by: (2n!)/((n+1)!n!).

For n = 0, we get C0 = 1.

For n = 3, we get C3 = 5.

For n = 4, we get C4 = 14.

For n = 5, we get C3 = 42.

2. Which of the following numbers is the 6th Catalan number?

a) 14

b) 429

c) 132

d) None of the mentioned

View Answer

Explanation: Catalan numbers are given by: (2n!)/((n+1)!n!).

First Catalan number is given by n = 0.

So the 6th Catalan number will be given by n = 5, which is 42.

3. Which of the following is/are applications of Catalan numbers?

a) Counting the number of Dyck words

b) Counting the number of expressions containing n pairs of parenthesis

c) Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines

d) All of the mentioned

View Answer

Explanation: Catalan numbers are used in all of the above applications.

4. Which of the following methods can be used to find the nth Catalan number?

a) Recursion

b) Binomial coefficients

c) Dynamic programming

d) All of the mentioned

View Answer

Explanation: All of the mentioned methods can be used to find the nth Catalan number.

5. The recursive formula for Catalan number is given by Cn = ∑Ci*C(n-i).

Consider the following dynamic programming implementation for Catalan numbers:

#include<stdio.h> int cat_number(int n) { int i,j,arr[n],k; arr[0] = 1; for(i = 1; i < n; i++) { arr[i] = 0; for(j = 0,k = i - 1; j < i; j++,k--) ______________________; } return arr[n-1]; } int main() { int ans, n = 8; ans = cat_number(n); printf("%d\n",ans); return 0; }

Which of the following lines completes the above code?

a) arr[i] = arr[j] * arr[k];

b) arr[j] += arr[i] * arr[k];

c) arr[i] += arr[j] * arr[k].

d) arr[j] = arr[i] * arr[k];

View Answer

Explanation: The line arr[i] += arr[j] * arr[k] reflects the recursive formula Cn = ∑Ci*C(n-i).

6. Which of the following implementations of Catalan numbers has the smallest time complexity?

a) Dynamic programming

b) Binomial coefficients

c) Recursion

d) All of the mentioned

View Answer

Explanation: The time complexities are as follows:

Dynamic programming: O(n

^{2})

Recursion: Exponential

Binomial coefficients: O(n).

7. What is the output of the following code?

#include<stdio.h> int cat_number(int n) { int i,j,arr[n],k; arr[0] = 1; for(i = 1; i < n; i++) { arr[i] = 0; for(j = 0,k = i - 1; j < i; j++,k--) arr[i] += arr[j] * arr[k]; } return arr[n-1]; } int main() { int ans, n = 8; ans = cat_number(n); printf("%d\n",ans); return 0; }

a) 42

b) 132

c) 429

d) 1430

View Answer

Explanation: The program prints the 8th Catalan number, which is 429.

8. Which of the following implementations of Catalan numbers has the largest space complexity(Don’t consider the stack space)?

a) Dynamic programming

b) Binomial coefficients

c) Recursion

d) All of the mentioned

View Answer

Explanation: The space complexities are as follows:

Dynamic programming: O(n)

Recursion: O(1)

Binomial coefficients: O(1).

9. What will be the value stored in arr[5] when the following code is executed?

#include<stdio.h> int cat_number(int n) { int i,j,arr[n],k; arr[0] = 1; for(i = 1; i < n; i++) { arr[i] = 0; for(j = 0,k = i - 1; j < i; j++,k--) arr[i] += arr[j] * arr[k]; } return arr[n-1]; } int main() { int ans, n = 10; ans = cat_number(n); printf("%d\n",ans); return 0; }

a) 14

b) 42

c) 132

d) 429

View Answer

Explanation: The 6th Catalan number will be stored in arr[5], which is 42.

10. Which of the following errors will occur when the below code is executed?

#include<stdio.h> int cat_number(int n) { int i,j,arr[n],k; arr[0] = 1; for(i = 1; i < n; i++) { arr[i] = 0; for(j = 0,k = i - 1; j < i; j++,k--) arr[i] += arr[j] * arr[k]; } return arr[n-1]; } int main() { int ans, n = 100; ans = cat_number(n); printf("%d\n",ans); return 0; }

a) Segmentation fault

b) Array size too large

c) Integer value out of range

d) None of the mentioned

View Answer

Explanation: The 100th Catalan number is too large to be stored in an integer. So, the error produced will be integer value out of range.(It will be a logical error and the compiler wont show it.)

**Sanfoundry Global Education & Learning Series – Data Structure.**

To practice all areas of Data Structure, __here is complete set of 1000+ Multiple Choice Questions and Answers__.