250+ TOP MCQs on Minimum Insertions to form a Palindrome and Answers

Data Structure Assessment Questions and Answers on “Minimum Insertions to form a Palindrome”.

1. Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
a) Greedy algorithm
b) Recursion
c) Dynamic programming
d) Both recursion and dynamic programming
Answer: d
Clarification: Dynamic programming and recursion can be used to solve the problem.

2. In which of the following cases the minimum no of insertions to form palindrome is maximum?
a) String of length one
b) String with all same characters
c) Palindromic string
d) Non palindromic string
Answer: d
Clarification: In string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.

3. In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.
a) True
b) False

Answer: b
Clarification: In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. For example, consider the string “abc”. The string can be converted to “abcba” by inserting “a” and “b”. The number of insertions is two, which is equal to length minus one.

4. Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: b
Clarification: The string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. Thus, only one insertion is required.

5. Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: a
Clarification: The given string is already a palindrome. So, no insertions are required.

6. Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
a) Minimum number of jumps problem
b) Longest common subsequence problem
c) Coin change problem
d) Knapsack problems
View Answer

Answer: b
Clarification: A variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.

7. Consider the following dynamic programming implementation:

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return _____________;
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

Which of the following lines should be added to complete the code?
a) arr[len][len]
b) len + arr[len][len]
c) len
d) len – arr[len][len]

Answer: d
Clarification: arr[len][len] contains the length of the longest palindromic subsequence. So, len – arr[len][len] gives the minimum number of insertions required to form a palindrome.

8. What is the time complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(mn)

Answer: c
Clarification: The time complexity of the above dynamic programming implementation is O(n2).

9. What is the space complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(mn)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation is O(n2).

10. What is the output of the following code?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The length of the longest palindromic subsequence is 3. So, the output will be 5 – 3 = 2.

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

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) 2
b) 3
c) 4
d) 5

Answer: a
Clarification: The value stored in arr[2][4] when the above code is executed is 2.

12. What is the output of the following code?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "efgfe";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) 0
b) 2
c) 4
d) 6

Answer: a
Clarification: Since the string “efgfe” is already a palindrome, the number of insertions required is 0.

& Algorithms.

and Answers.

Leave a Reply

Your email address will not be published. Required fields are marked *