Data Structure Questions and Answers - Decimal to Binary using Stacks

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Decimal to Binary using Stacks”.

1. 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. 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]);
     }
}

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]);
     }
}

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]);
     }
}

Note: Join free Sanfoundry classes at Telegram or Youtube

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. 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. 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());
    }
 }

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());
    }
 }

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());
    }
 }

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. 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. 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;
}

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;
  }

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;
}

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. 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. 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");
}

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");
}

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");
}

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.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

« Prev - Data Structure Questions and Answers – Stack using Queues

» Next - Data Structure Questions and Answers – Evaluation of an Infix Expression (Not Parenthesized)

Related Posts:

Check Data Structure Books
Apply for Computer Science Internship
Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ
Check Programming Books

Recommended Articles: