Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQs – Decimal to Binary using Stacks

1 - Question

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 - Question

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

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 - Question

4. Using stacks, how to obtain the binary representation of the number? a) public void convertBinary(int num) { Stack stack = new Stack(); 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 stack = new Stack(); 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 stack = new Stack(); 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 stack = new Stack(); 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

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 - Question

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 stk = new Stack(); 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 stk = new Stack(); 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 stk = new Stack(); 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 stk = new Stack(); 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

7. What is the time complexity of the following code? public boolean isBalanced(String exp) { int len = exp.length(); Stack stk = new Stack(); 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

8. Which of the following program prints the index of every matching parenthesis? a) public void dispIndex(String exp) { Stack stk = new Stack(); 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 stk = new Stack(); 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 stk = new Stack(); 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 stk = new Stack(); 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