Data Structure Questions and Answers – Catalan Number using Dynamic Programming

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

Answer: d
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) 42
View Answer

Answer: d
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 not an application 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) Creation of head and tail for a given number of tosses
View Answer

Answer: d
Explanation: Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines are the applications of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal’s triangle.
advertisement
advertisement

4. Which of the following methods can be used to find the nth Catalan number?
a) Recursion
b) Binomial coefficients
c) Dynamic programming
d) Recursion, Binomial Coefficients, Dynamic programming
View Answer

Answer: d
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:

Note: Join free Sanfoundry classes at Telegram or Youtube
#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

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

6. Which of the following implementations of Catalan numbers has the smallest time complexity?
a) Dynamic programming
b) Binomial coefficients
c) Recursion
d) All have equal time complexity
View Answer

Answer: b
Explanation: The time complexities are as follows:
Dynamic programming: O(n2)
Recursion: Exponential
Binomial coefficients: O(n).

7. What is the output of the following code?

advertisement
#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

Answer: c
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 have equal space complexities
View Answer

Answer: a
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

Answer: b
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) Array index out of range
View Answer

Answer: c
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 Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.