This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Edit Distance Problem”.

1. Which of the following methods can be used to solve the edit distance problem?

a) Recursion

b) Dynamic programming

c) Both dynamic programming and recursion

d) None of the mentioned

View Answer

Explanation: Both dynamic programming and recursion can be used to solve the edit distance problem.

2. The edit distance satisfies the axioms of a metric when the costs are non-negative.

a) True

b) False

View Answer

Explanation: d(s,s) = 0, since each string can be transformed into itself without any change.

d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.

d(s1, s2) = d(s2, s1)

d(s1, s3) <= d(s1, s2) + d(s2, s3)

Thus, the edit distance satisfies the axioms of a metric.

3. Which of the following is an application of the edit distance problem?

a) Approximate string matching

b) Spelling correction

c) Similarity of DNA

d) All of the mentioned

View Answer

Explanation: All of the mentioned are the applications of the edit distance problem.

4. In which of the following cases will the edit distance between two strings be zero?

a) When one string is a substring of another

b) When the lengths of the two strings are equal

c) When the two strings are equal

d) The edit distance can never be zero

View Answer

Explanation: The edit distance will be zero only when the two strings are equal.

5. Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.

a) True

b) False

View Answer

Explanation: Consider the strings “abcd” and “efghi”. The string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. The cost of transformation is 5, which is equal to the length of the larger string.

6. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?

a) 3

b) 4

c) 5

d) 6

View Answer

Explanation: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. So, the edit distance is 4.

7. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?

a) 0

b) 4

c) None of the mentioned

d) Cannot be determined

View Answer

Explanation: The empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. Thus, the edit distance is 4.

8. Consider the following dynamic programming implementation of the edit distance problem:

#include<stdio.h> #include<string.h> int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } _____________; } } return arr[len1][len2]; } int main() { char s1[] = "abcd", s2[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }

Which of the following lines should be added to complete the above code?

a) arr[i-1][j] = min

b) arr[i][j-1] = min

c) arr[i-1][j-1] = min

d) arr[i][j] = min

View Answer

Explanation: The line arr[i][j] = min completes the above code.

9. What is the time complexity of the above dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of two strings?

a) O(1)

b) O(m + n)

c) O(mn)

d) None of the mentioned

View Answer

Explanation: The time complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

10. What is the space complexity of the above dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?

a) O(1)

b) O(m + n)

c) O(mn)

d) None of the mentioned

View Answer

Explanation: The space complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

11. What is the output of the following code?

#include<stdio.h> #include<string.h> int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "abcd", s2[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }

a) 1

b) 2

c) 3

d) 4

View Answer

Explanation: The program prints the edit distance between the strings “abcd” and “defg”, which is 4.

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

#include<stdio.h> #include<string.h> int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "abcd", s2[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }

a) 1

b) 2

c) 3

d) 4

View Answer

Explanation: The value stored in arr[2][2] when the above code is executed is 2.

13. What is the output of the following code?

#include<stdio.h> #include<string.h> int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "pqrstuv", s2[] = "prstuv"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }

a) 1

b) 2

c) 3

d) 4

View Answer

Explanation: The code prints the edit distance between the two strings, which is 1.

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