Data Structure Questions and Answers-Catalan Number using Dynamic Programming

 

 Help authour, Buy PDF Ebook   >>>Click Here<<<

Data Structure Questions and Answers-Catalan Number using Dynamic Programming

Click on any option to know the CORRECT ANSWERS

Question 1
Which of the following is NOT a Catalan number?
A
1
B
5
C
14
D
43
Education Questions answers

Question 1 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.

Question 2
Which of the following numbers is the 6th Catalan number?
A
14
B
429
C
132
D
None of the mentioned
UPSC Questions answers

Question 2 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.

Question 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
Bank exam Questions answers

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

Question 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
Biology Questions answers

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

Question 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];
GK Questions answers

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

There are 5 questions to complete.

 

 Download all FREE PDF Ebook >>>CLICK HERE<<<