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

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

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)

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

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)

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

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)

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