Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Decimal to Binary using Stacks

1 - Question

Express -15 as a 6-bit signed binary number.
a) 001111
b) 101111
c) 101110
d) 001110
View Answer

Answer: b
Explanation: The first 4 1s from the right represent the number 15, 2 more bits are padded to make it 6 digits and the leftmost bit is a 1 to represent that it is -15.


2 - Question

Which of the following code snippet is used to convert decimal to binary numbers?
a)

public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[index++] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

b)

public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
       bin[++index] = num%2;
       num = num/2;
     }
     for(int i = index-1;i >= 0;i--)
     {
       System.out.print(bin[i]);
     }
}

c)

public void convertBinary(int num)
{
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[index++] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
}

d)

public void convertBinary(int num)
 {
     int bin[] = new int[50];
     int index = 0;
     while(num > 0)
     {
         bin[++index] = num/2;
         num = num%2;
     }
     for(int i = index-1;i >= 0;i--)
     {
         System.out.print(bin[i]);
     }
  }
View Answer

Answer: a
Explanation: Take the modulus by 2 of the number and store in an array while halving the number during each iteration and then display the contents of the array.


3 - Question

Which is the predefined method available in Java to convert decimal to binary numbers?
a) toBinaryInteger(int)
b) toBinaryValue(int)
c) toBinaryNumber(int)
d) toBinaryString(int)
View Answer

Answer: d
Explanation: The method toBinaryString() takes an integer argument and is defined in java.lang package. Usage is java.lang.Integer.toBinaryString(int) this returns the string representation of the unsigned integer value.


4 - Question

Using stacks, how to obtain the binary representation of the number?
a)

public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num / 2;
        stack.push(digit);
        num = num % 2;
    }
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

b)

public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit);
    }
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

c)

public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit);
        num = num / 2;
    }
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }

d)

public void convertBinary(int num)
{
    Stack<Integer> stack = new Stack<Integer>();
    while (num != 0)
    {
        int digit = num % 2;
        stack.push(digit%2);
        num = num / 2;
    }
    System.out.print("\nBinary representation is:");
    while (!(stack.isEmpty() ))
    {
        System.out.print(stack.pop());
    }
 }
View Answer

Answer: c
Explanation: Here instead of adding the digits to an array, you push it into a stack and while printing, pop it from the stack.


5 - Question

What is the time complexity for converting decimal to binary numbers?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
View Answer

Answer: c
Explanation: Since each time you are halving the number, it can be related to that of a binary search algorithm, hence the complexity is O(logn).


6 - Question

Write a piece of code which returns true if the string contains balanced parenthesis, false otherwise.
a)

public boolean isBalanced(String exp)
{
int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
        {
char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
if(stk.peek() == null)
                        {
return false;
}
			stk.pop();
}
}
return true;
}

b)

public boolean isBalanced(String exp)
{
int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
            {
char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
if(stk.peek() != null)
                        {
return true;
}
			stk.pop();
}
}
return false;
  }

c)

public boolean isBalanced(String exp)
{
int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
        {
	       char ch = exp.charAt(i);
               if (ch == ')')
               stk.push(i);
               else if (ch == '(')
               {
if(stk.peek() == null)
                        {
return false;
}
			stk.pop();
}
}
return true;
}

d)

public boolean isBalanced(String exp)
{
int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
        {
char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
if(stk.peek() != null)
                        {
return false;
}
			stk.pop();
}
}
return true;
  }

 
View Answer

Answer: a
Explanation: Whenever a ‘(‘ is encountered, push it into the stack, and when a ‘)’ is encountered check the top of the stack to see if there is a matching ‘(‘, if not return false, continue this till the entire string is processed and then return true.


7 - Question

What is the time complexity of the following code?

 

public boolean isBalanced(String exp)
{
int len = exp.length();
	Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
        {
char ch = exp.charAt(i);
                if (ch == '(')
                stk.push(i);
                else if (ch == ')')
                {
if(stk.peek() == null)
                        {
return false;
}
			stk.pop();
}
}
return true;
}

a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)
View Answer

Answer: b
Explanation: All the characters in the string have to be processed, hence the complexity is O(n).


8 - Question

Which of the following program prints the index of every matching parenthesis?
a)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
          try
          {
            int p = stk.pop() + 1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

b)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {
        char ch = exp.charAt(i);
        if (ch == '(')
        stk.push(i);
        else if (ch == ')')
        {
           try
           {
             int p = stk.pop() + 1;
             System.out.println("')' at index "+(i)+" matched with ')' at index "+p);
           }
           catch(Exception e)
           {
              System.out.println("')' at index "+(i)+" is unmatched");
           }
        }
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

c)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop() +1;
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
             System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}

d)

public void dispIndex(String exp)
{
    Stack<Integer> stk = new Stack<Integer>();
    for (int i = 0; i < len; i++)
    {
        char ch = exp.charAt(i);
        if (ch == ')')
        stk.push(i);
        else if (ch == '(')
        {
          try
          {
            int p = stk.pop();
            System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
          }
          catch(Exception e)
          {
            System.out.println("')' at index "+(i+1)+" is unmatched");
          }
        }
    }
    while (!stk.isEmpty() )
    System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}
View Answer

Answer: a
Explanation: Whenever a ‘(‘ is encountered, push the index of that character into the stack, so that whenever a corresponding ‘)’ is encountered, you can pop and print it.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners