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) Greedy algorithm
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) Longest decreasing subsequence
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(n2)
c) O(n3)
d) O(2n)
View Answer
Explanation: The time complexity of the brute force algorithm used to find the longest common subsequence is O(2n).
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 following 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”?
#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[] = " abcedfg", str2[] = "bcdfh"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }
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 following 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”?
#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[] = " abcedfg", str2[] = "bcdfh"; int ans = lcs(str1,str2); printf("%d",ans); return 0; }
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) fgmna
View Answer
Explanation: The length of the longest common subsequence is 4. But ‘fgmna’ is not the longest common subsequence as its length is 5.
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 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]
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Computer Science Books
- Practice Data Structure MCQ
