Data Structure Questions and Answers on Decimal to Binary Conversion using Recursion for Freshers

1. Which of the following is the binary representation of 100?

a) 1010010
b) 1110000
c) 1100100
d) 1010101

Answer: c

Explanation: 100 = 64 + 32 + 4 = 26 + 25 + 22 = 1100100.

2. Consider the following iterative code used to convert a decimal number to its equivalent binary:

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          _______;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 10;
     dec_to_bin(n);
     return 0;
}

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

a) n–
b) n /= 2
c) n /= 10
d) n++

Answer: b

Explanation: The line “n /= 2” should be inserted to complete the above code.

3. What is the output of the following code?

#include
void dec_to_bin(int n)
{
    int arr[31],len = 0,i;
    if(n == 0)
    {
        arr[0] = 0;
        len = 1;
    }
    while(n != 0)
    {
        arr[len++] = n % 2;
        n /= 2;
    }
    for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
    int n = 63;
    dec_to_bin(n);
    return 0;
}

a) 111111
b) 111011
c) 101101
d) 101010

Answer: a

Explanation: The program prints the binary equivalent of 63, which is 111111.

4. What is the output of the following code?

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          n /= 2;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 0;
     dec_to_bin(n);
     return 0;
}

a) 0
b) 1
c) Runtime error
d) Garbage value

Answer: a

Explanation: The program prints the binary equivalent of 0, which is 0.

5. What is the time complexity of the above code used to convert a decimal number to its binary equivalent?

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

Answer: d

Explanation: The time complexity of the above code used to convert a decimal number to its binary equivalent is O(logn).

6. Consider the following recursive implementation used to convert a decimal number to its binary equivalent:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
          return;
        __________;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = 100,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

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

a) arr[len] = n
b) arr[len] = n % 2
c) arr[len++] = n % 2
d) arr[len++] = n

Answer: c

Explanation: The line “arr[len++] = n % 2” should be inserted to complete the above code.

7. Consider the following code:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}

Which of the following lines is the base case for the above code?

a) if(n ==0 && len == 0)
b) if(n == 0)
c) both of the mentioned
d) none of the mentioned

Answer: c

Explanation: Both of the above mentioned lines are the base cases for the above code.

8. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = -100,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

a) -1100100
b) 1100100
c) 2’s complement of 1100100
d) Garbage value

Answer: d

Explanation: The program doesn’t handle negative inputs and so produces a garbage value.

9. What is the time complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

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

Answer: d

Explanation: The time complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

10. What is the space complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

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

Answer: d

Explanation: The space complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

11. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = 111,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

a) 1110111
b) 1001111
c) 1101111
d) 1010111

Answer: c

Explanation: The program prints the binary equivalent of 111, which is 1101111.

12. How many times is the function recursive_dec_to_bin() called when the following code is executed?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
    int n = 111,i;
    recursive_dec_to_bin(n);
    for(i=len-1; i>=0; i--)
    printf("%d",arr[i]);
    return 0;
}

a) 7
b) 8
c) 9
d) 10

Answer: b

Explanation: The function recursive_dec_to_bin() is called 8 times when the above code is executed.