Data Structure Questions and Answers on Reverse of a String using Recursion

1. Consider the following iterative implementation used to reverse a string:

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(______)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}

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

a) i > j
b) i < len
c) j > 0
d) i < j

Answer: d

Explanation: The line “i < j” should be inserted to complete the above code.

2. What is the output of the following code?

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(i < j)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}
int main()
{
      char s[100] = "reverse";
      reverse_string(s);
      printf("%s",s);
      return 0;
}

a) ersevre
b) esrever
c) eserver
d) eresevr

Answer: b

Explanation: The program reverses the string “reverse” and prints “esrever”.

3. What is the time complexity of the above code used to reverse a string?

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

Answer: b

Explanation: The time complexity of the above code used to reverse a string is O(n).

4. What does the following code do?

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(i < j)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}
int main()
{
      char s[100] = "abcdefg";
      char t[100];
      strcpy(t,s);
      reverse_string(s);
      if(strcmp(t,s) == 0)
        printf("Yes");
      else
        printf("No");
      return 0;
}

a) Copies a string to another string
b) Compares two strings
c) Reverses a string
d) Checks if a string is a palindrome

Answer: d

Explanation: The main purpose of the above code is to check if a string is a palindrome.

5. What is the output of the following code?

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(i < j)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}
int main()
{
      char s[100] = "rotator";
      char t[100];
      strcpy(t,s);
      reverse_string(s);
      if(strcmp(t,s) == 0)
        printf("Yes");
      else
        printf("No");
      return 0;
}

a) Yes
b) No
c) Runtime error
d) Compile time error

Answer: a

Explanation: The program checks if a string is a palindrome. Since the string rotator is a palindrome, it prints “yes”.

6. Consider the following recursive implementation used to reverse a string:

void recursive_reverse_string(char *s, int left, int right)
{
     if(left < right)
     {
         char tmp = s[left];
         s[left] = s[right];
         s[right] = tmp;
         _________;
     }
}

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

a) recursive_reverse_string(s, left+1, right+1)
b) recursive_reverse_string(s, left-1, right-1)
c) recursive_reverse_string(s, left+1, right-1)
d) recursive_reverse_string(s, left-1, right+1)

Answer: c

Explanation: The line “recursive_reverse_string(s, left+1, right-1)” should be inserted to complete the above code.

7. What is the output of the following code?

#include
#include
void recursive_reverse_string(char *s, int left, int right)
{
     if(left < right)
     {
         char tmp = s[left];
         s[left] = s[right];
         s[right] = tmp;
         recursive_reverse_string(s, left+1, right-1);
     }
}
int main()
{
     char s[100] = "recursion";
     int len = strlen(s);
     recursive_reverse_string(s,0,len-1);
     printf("%s",s);
     return 0;
}

a) recursion
b) nsoirucer
c) noisrcuer
d) noisrucer

Answer: d

Explanation: The program prints the reversed string of “recursion”, which is “noisrucer”.

8. How many times is the function recursive_reverse_string() called when the following code is executed?

#include
#include
void recursive_reverse_string(char *s, int left, int right)
{
     if(left < right)
     {
         char tmp = s[left];
         s[left] = s[right];
         s[right] = tmp;
         recursive_reverse_string(s, left+1, right-1);
     }
}
int main()
{
     char s[100] = "madam";
     int len = strlen(s);
     recursive_reverse_string(s,0,len-1);
     printf("%s",s);
     return 0;
}

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

Answer: a

Explanation: The function recursive_reverse_string() is called 3 times when the above code is executed.

9. What is the time complexity of the above recursive implementation used to reverse a string?

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

Answer: b

Explanation: The time complexity of the above recursive implementation used to reverse a string is O(n).

10. For which of the following cases will the reversal of a string be equal to the original string?

a) Palindromic strings
b) Strings of length 1
c) Empty String
d) All of the mentioned

Answer: d

Explanation: For all of the above mentioned strings, the reversal of the string will be equal to the original string.