This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Longest Common Subsequence”.

1. Which of the following methods can be used to solve the longest common subsequence problem?

a) Recursion

b) Dynamic programming

c) Both recursion and dynamic programming

d) None of the mentioned

View Answer

Explanation: Both recursion and dynamic programming can be used to solve the longest subsequence problem.

2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

a) 9

b) 8

c) 7

d) 6

View Answer

Explanation: The longest common subsequence is “PRTPQRS” and its length is 7.

3. Which of the following problems can be solved using the longest subsequence problem?

a) Longest increasing subsequence

b) Longest palindromic subsequence

c) Longest bitonic subsequence

d) None of the mentioned

View Answer

Explanation: To find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string.

4. Longest common subsequence is an example of ____________

a) Greedy algorithm

b) 2D dynamic programming

c) 1D dynamic programming

d) Divide and conquer

View Answer

Explanation: Longest common subsequence is an example of 2D dynamic programming.

5. What is the time complexity of the brute force algorithm used to find the longest common subsequence?

a) O(n)

b) O(n^{2})

c) O(n^{3})

d) O(2^{n})

View Answer

Explanation: The time complexity of the brute force algorithm used to find the longest common subsequence is O(2

^{n}).

6. Consider the following dynamic programming implementation of the longest common subsequence problem:

#include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lcs(char *str1, char *str2) { int i,j,len1,len2; len1 = strlen(str1); len2 = strlen(str2); int arr[len1 + 1][len2 + 1]; for(i = 0; i <= len1; i++) arr[i][0] = 0; for(i = 0; i <= len2; i++) arr[0][i] = 0; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { if(str1[i-1] == str2[j - 1]) ______________; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len1][len2]; } int main() { char str1[] = " abcedfg", str2[] = "bcdfh"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }

Which of the following lines completes the above code?

a) arr[i][j] = 1 + arr[i][j].

b) arr[i][j] = 1 + arr[i – 1][j – 1].

c) arr[i][j] = arr[i – 1][j – 1].

d) arr[i][j] = arr[i][j].

View Answer

Explanation: The line, arr[i][j] = 1 + arr[i – 1][j – 1] completes the above code.

7. What is the time complexity of the above dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

a) O(n)

b) O(m)

c) O(m + n)

d) O(mn)

View Answer

Explanation: The time complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

8. What is the space complexity of the above dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

a) O(n)

b) O(m)

c) O(m + n)

d) O(mn)

View Answer

Explanation: The space complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

9. What is the output of the following code?

#include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lcs(char *str1, char *str2) { int i,j,len1,len2; len1 = strlen(str1); len2 = strlen(str2); int arr[len1 + 1][len2 + 1]; for(i = 0; i <= len1; i++) arr[i][0] = 0; for(i = 0; i <= len2; i++) arr[0][i] = 0; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { if(str1[i-1] == str2[j - 1]) arr[i][j] = 1 + arr[i - 1][j - 1]; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len1][len2]; } int main() { char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }

a) 3

b) 4

c) 5

d) 6

View Answer

Explanation: The program prints the length of the longest common subsequence, which is 4.

10. Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?

a) hgmq

b) cfnq

c) bfmq

d) all of the mentioned

View Answer

Explanation: The length of the longest common subsequence is 4 and all of the mentioned subsequences are the longest common subsequences with length 4.

11. What is the value stored in arr[2][3] when the following code is executed?

#include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lcs(char *str1, char *str2) { int i,j,len1,len2; len1 = strlen(str1); len2 = strlen(str2); int arr[len1 + 1][len2 + 1]; for(i = 0; i <= len1; i++) arr[i][0] = 0; for(i = 0; i <= len2; i++) arr[0][i] = 0; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { if(str1[i-1] == str2[j - 1]) arr[i][j] = 1 + arr[i - 1][j - 1]; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len1][len2]; } int main() { char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }

a) 1

b) 2

c) 3

d) 4

View Answer

Explanation: The value stored in arr[2][3] is 1.

12. What is the output of the following code?

#include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lcs(char *str1, char *str2) { int i,j,len1,len2; len1 = strlen(str1); len2 = strlen(str2); int arr[len1 + 1][len2 + 1]; for(i = 0; i <= len1; i++) arr[i][0] = 0; for(i = 0; i <= len2; i++) arr[0][i] = 0; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { if(str1[i-1] == str2[j - 1]) arr[i][j] = 1 + arr[i - 1][j - 1]; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len1][len2]; } int main() { char str1[] = "abcd", str2[] = "efgh"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }

a) 3

b) 2

c) 1

d) 0

View Answer

Explanation: The program prints the length of the longest common subsequence, which is 0.

**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__.