This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Catalan Numbers”.
1. Which of the following forms a sequence of natural numbers that occur in different counting problems?
a) Chromatic number
b) Pascal triangle
c) Catalan numbers
d) Factorial of a number
View Answer
Explanation: In different counting problems like counting the number of binary search trees with n keys and counting the number of full binary trees, Catalan numbers can be used. They form a sequence of natural numbers.
2. What are the values of Catalan numbers for n = 0, 1, 2, 3, 4 and 5?
a) 1, 1, 2, 5, 14, 42
b) 0, 1, 2, 5, 14, 42
c) 0, 1, 2, 3, 14, 42
d) 1, 1, 2, 3, 14, 42
View Answer
Explanation: The recursive formula for Catalan numbers is given by C0 = 1 and Cn+1 = \(\Sigma_{i=0}^{n}\)(Ci Cn-1) for all n >= 0. Hence, by solving the given formula for n = 0, 1, 2, 3, 4 and 5, we get the Catalan numbers as 1, 1, 2, 5, 14 and 42.
3. What is the output of the following code in python, if the input is given as 8?
def CatalanNumber(n): if n<= 1 : return 1 result=0 for x in range(n): result = result + CatalanNumber(x) * CatalanNumber(n-x-1) return result n=int(input("Enter the number:")) answer=CatalanNumber(n) print(" ", answer)
a) 1432
b) 1430
c) 1438
d) 1462
View Answer
Explanation: The given code in python gives the value for nth Catalan number. Hence, the output of the following program will be the value for Catalan number n = 8, which is 1430. The above program is the recursive implementation of Catalan numbers.
Output: Enter the number: 8 1430
4. Consider the following algorithm for finding the nth Catalan number using dynamic approach. which of the following steps best fills the blank?
1) create and initialize a variable 'n' and an array 'c' 2) initialize the first two values of array as 1 3) _______________________ 4) return c[n]
a) Traverse the array from 2 to n one by one and update the value as c[j] * c[i-j-1]
b) Traverse the array from 2 to n one by one and update the value as c[i] * c[i-j-1]
c) Traverse the array from 2 to n one by one and update the value as c[j] * c[i-1]
d) Traverse the array from 2 to n one by one and update the value as c[i] * c[j-1]
View Answer
Explanation: For finding the nth Catalan number using dynamic approach, first initialize a variable and an array, which will store the Catalan numbers. Initialize the first two values of the array as 1 and then traverse the array till n, starting from 2 and update the value as c[j] * c[i-j-1]. In the end, simply return the value of nth value of the array.
5. Dynamic programming approach can be used to implement Catalan numbers.
a) True
b) False
View Answer
Explanation: In the recursive implementation of Catalan numbers, the work is repeated many times. We keep on calculating the same values again and again. Hence, the dynamic programming approach can be used as there are overlapping subproblems.
6. Which of the following is the time complexity of implementing Catalan numbers using dynamic programming?
a) O(n)
b) O(n2)
c) O(1)
d) O(log n)
View Answer
Explanation: To implement Catalan numbers using the dynamic programming approach, we use an array or a vector to store the intermediate results. Here, the space complexity will be O(n). Hence, it will take O(n2) time using the iterative approach.
7. Which of the following is the time complexity of finding nth Catalan numbers using binomial coefficient?
a) O(n)
b) O(n2)
c) O(1)
d) O(log n2)
View Answer
Explanation: To find the nth Catalan numbers using binomial coefficient, the following formula can be used Cn = \(\frac{1}{n+1} \begin{pmatrix}
2n \\
n \\
\end{pmatrix}\). The loop runs starting from 0 till n. Hence, the time complexity to find nth Catalan number using binomial coefficient will take O(n) time.
8. Which of the following is an application of the Catalan numbers?
a) Pre-order traversal
b) In-order traversal
c) Counting the number of possible BST
d) Detecting cycle in a graph
View Answer
Explanation: The Catalan number = (2n)! / ((n + 1)! * n!), is equal to the number of the possible binary search trees that can be formed using n different keys. Hence, the Catalan number can be used to find the number of possible BST.
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.
- Check Programming Books
- Check Computer Science Books
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
