Data Structure Multiple Choice Questions on “Longest Common Subsequence”.
1. Which of the following methods can be used to solve the longest common subsequence problem? Answer: c 2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence? 3. Which of the following problems can be solved using the longest subsequence problem? 4. Longest common subsequence is an example of ____________ Answer: b 5. What is the time complexity of the brute force algorithm used to find the longest common subsequence? Answer: d 6. Consider the following dynamic programming implementation of the longest common subsequence problem: Which of the following lines completes the above code? Answer: b 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”? a) O(n) Answer: d 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”? a) O(n) Answer: d 9. What is the output of the following code? a) 3 10. Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ? Answer: d 11. What is the value stored in arr[2][3] when the following code is executed? a) 1 Answer: a 12. What is the output of the following code? a) 3 Answer: d
a) Recursion
b) Dynamic programming
c) Both recursion and dynamic programming
d) Greedy algorithm
Clarification: Both recursion and dynamic programming can be used to solve the longest subsequence problem.
a) 9
b) 8
c) 7
d) 6
Answer: c
Clarification: The longest common subsequence is “PRTPQRS” and its length is 7.
a) Longest increasing subsequence
b) Longest palindromic subsequence
c) Longest bitonic subsequence
d) Longest decreasing subsequence
Answer: b
Clarification: 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.
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer
Clarification: Longest common subsequence is an example of 2D dynamic programming.
a) O(n)
b) O(n2)
c) O(n3)
d) O(2n)
Clarification: The time complexity of the brute force algorithm used to find the longest common subsequence is O(2n).#include
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].
Clarification: The line, arr[i][j] = 1 + arr[i – 1][j – 1] completes the above code.#include
b) O(m)
c) O(m + n)
d) O(mn)
Clarification: The time complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).#include
b) O(m)
c) O(m + n)
d) O(mn)
Clarification: The space complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).#include
b) 4
c) 5
d) 6
Answer: b
Clarification: The program prints the length of the longest common subsequence, which is 4.
a) hgmq
b) cfnq
c) bfmq
d) fgmna
Clarification: The length of the longest common subsequence is 4. But ‘fgmna’ is not the longest common subsequence as its length is 5.#include
b) 2
c) 3
d) 4
Clarification: The value stored in arr[2][3] is 1.#include
b) 2
c) 1
d) 0
Clarification: The program prints the length of the longest common subsequence, which is 0.