Stack Polish Notation Questions

 

What is the result of the given postfix expression? abc*+ where a=1, b=2, c=3.
a) 4
b) 5
c) 6
d) 7

What is the result of the following postfix expression?
ab*cd*+ where a=2,b=2,c=3,d=4.
a) 16
b) 12
c) 14
d) 10

Evaluate the postfix expression ab + cd/- where a=5, b=4, c=9, d=3.

a) 23
b) 15
c) 6
d) 10

Evaluate and write the result for the following postfix expression
abc*+de*f+g*+ where a=1, b=2, c=3, d=4, e=5, f=6, g=2.

a) 61
b) 59
c) 60
d) 55

For the given expression tree, write the correct postfix expression.

a) abc*+
b) abc+*
c) ab+c*
d) a+bc*

What would be the Prefix notation for the given equation?

A+(B*C)

a) +A*CB
b) *B+AC
c) +A*BC
d) *A+CB

What would be the Prefix notation for the given equation?

(A*B)+(C*D)

a) +*AB*CD
b) *+AB*CD
c) **AB+CD
d) +*BA*CD

What would be the Prefix notation for the given equation?

A+B*C^D

a) +A*B^CD
b) +A^B*CD
c) *A+B^CD
d) ^A*B+CD

What would be the Prefix notation for the given equation?

A^B^C^D

a) ^^^ABCD
b) ^A^B^CD
c) ABCD^^^
d) AB^C^D

What would be the Prefix notation for the given equation?

a+b-c/d&e|f

a) |&-+ab/cdef
b) &|-+ab/cdef
c) |&-ab+/cdef
d) |&-+/abcdef

What would be the Prefix notation for the given equation?

(a+(b/c)*(d^e)-f)

a) -+a*/^bcdef
b) -+a*/bc^def
c) -+a*b/c^def
d) -a+*/bc^def

What would be the Prefix notation and Postfix notation for the given equation?

A+B+C

a) ++ABC and AB+C+
b) AB+C+ and ++ABC
c) ABC++ and AB+C+
d) ABC+ and ABC+

What would be the Prefix notation for the given equation?

a|b&c

a) a|&bc
b) &|abc
c) |a&bc
d) ab&|c

What is the postfix expression for the corresponding infix expression?

a+b*c+(d*e)

a) abc*+de*+
b) abc+*de*+
c) a+bc*de+*
d) abc*+(de)*+

What is the postfix expression for the infix expression?

a-b-c

a) -ab-c
b) ab – c –
c) – -abc
d) -ab-c

What is the postfix expression for the following infix expression?

a/b^c-d

a) abc^/d-
b) ab/cd^-
c) ab/^cd-
d) abcd^/-

What is the corresponding postfix expression for the given infix expression?

a*(b+c)/d

a) ab*+cd/
b) ab+*cd/
c) abc*+/d
d) abc+*d/

What is the corresponding postfix expression for the given infix expression?

a+(b*c(d/e^f)*g)*h)

a) ab*cdef/^*g-h+
b) abcdef^/*g*h*+
c) abcd*^ed/g*-h*+
d) abc*de^fg/*-*h+

What is the correct postfix expression for the following expression?

a+b*(c^d-e)^(f+g*h)-i

a) abc^de-fg+*^*+i-
b) abcde^-fg*+*^h*+i-
c) abcd^e-fgh*+^*+i-
d) ab^-dc*+ef^gh*+i-

From the given Expression tree, identify the correct postfix expression from the list of options.

a) ab*cd*+
b) ab*cd-+
c) abcd-*+
d) ab*+cd-

What would be the solution to the given prefix notation?

- + 5 / 10 5 5

a) 2
b) 5
c) 10
d) 7

What would be the solution to the given prefix notation?

/ / / / 16 4 2 1

a) 1
b) 4
c) 2
d) 8

What would be the solution to the given prefix notation?

+ 9 * 3 / 8 4

a) 14
b) 15
c) 18
d) 12

What would be the solution to the given prefix notation?

- + 1 2 * 3 / 6 2

a) 6
b) -6
c) 3
d) -3

What would be the solution to the given prefix notation?

- * 1 5 / * / 6 3 6 2

a) 1
b) 0
c) -1
d) -2

What would be the solution to the given prefix notation?

* / + 1 2 / 4 2 + 3 5

a) 12
b) 7.5
c) 9
d) 13.5

The postfix expression abc+de/*- is equivalent to which of the following infix expression?
a) abc+-de*/
b) (a+b)-d/e*c
c) a-(b+c)*(d/e)
d) abc+*-(d/e)

The equivalent infix expression and value for the postfix form 1 2 + 3 * 4 5 * – will be ___________
a) 1 + 2 * 3 – 4 * 5 and -13
b) (2 + 1) * (3 – 4) * 5 and 13
c) 1 + 2 * (3 – 4) * 5 and -11
d) (1 + 2) * 3 – (4 * 5) and -11

What is the value of the postfix expression 2 3 + 4 5 6 – – *
a) 19
b) 21
c) -4
d) 25

The prefix expression of the postfix expression AB+CD-* is __________
a) (A+B)*(C-D)
b) +AB*-CD
c) A+*BCD-
d) *+AB-CD

Consider the postfix expression 4 5 6 a b 7 8 a c, where a, b, c are operators. Operator a has higher precedence over operators b and c. Operators b and c are right associative. Then, equivalent infix expression is
a) 4 a 5 6 b 7 8 a c
b) 4 a 5 c 6 b 7 a 8
c) 4 b 5 a 6 c 7 a 8
d) 4 a 5 b 6 c 7 a 8

The result of the postfix expression 5 3 * 9 + 6 / 8 4 / + is _____________
a) 8
b) 6
c) 10
d) 9

Stack Operations

 Stack Operations

push() − Pushing (storing) an element on the stack.

pop() − Removing (accessing) an element from the stack.

peek() or Top() − get the top data element of the stack, without removing it.

PEEP() To find nth element from stack.

PEEP(Stack_s1, TOP, i) 

 //Check for Stack Underflow 

If(TOP-i+1 < 0) then 

 Write (‘Stack Underflow For PEEP’) 

 Return 

  //Return ith element from top of stack 

Return Stack_s1 [Top – i + 1] 

isFull() − check if stack is full.

isEmpty() − check if stack is empty.

push(), pop(), isEmpty() and peek() etc. all take O(1) time. We do not run any loop in any of these operations.

Array Address Calculation Questions

 

1. 

An array X [-15……….10, 15……………40] requires one byte of storage. If beginning location is 1500 determine the location of X [15][20].

2.

A matrix B[10][20] is stored in the memory with each element requiring 2 bytes of storage. If the base address at B[2][1] is 2140, find the address of B[5][4] when the matrix is stored in Column Major Wise.

3.

Each element of an array arr[15][20] requires ‘W’ bytes of storage. If the address of arr[6][8] is 4440 and the base address at arr[1][1] is 4000, find the width ‘W’ of each cell in the array arr[][] when the array is stored as Column Major Wise.

4.

A matrix ARR[-4…6, 3…8] is stored in the memory with each element requiring 4 bytes of storage. If the base address is 1430, find the address of ARR[3][6] when the matrix is stored in Row Major Wise.

5. 

A matrix A[m][m] is stored in the memory with each element requiring 4 bytes of storage. If the base address at A[1][1] is 1500 and the address of A[4][5] is 1608, determine the order of the matrix when it is stored in Column Major Wise.

6. 

A matrix P[15][10] is stored with each element requiring 8 bytes of storage. If the base address at P[0][0] is 1400, determine the address at P[10][7] when the matrix is stored in Row Major Wise.

7. 

 A matrix A[m][n] is stored with each element requiring 4 bytes of storage. If the base address at A[1][1] is 1500 and the address at A[4][5] is 1608, determine the number of rows of the matrix when the matrix is stored in Column Major Wise.

8. 

The array D[-2…10][3…8] contains double type elements. If the base address is 4110, find the address of D[4][5], when the array is stored in Column Major Wise.

9.

An array AR[-4 … 6, -2 … 12], stores elements in Row Major Wise, with the address AR[2][3] as 4142. If each element requires 2 bytes of storage, find the Base address.

10. 

A square matrix M[][] of size 10 is stored in the memory with each element requiring 4 bytes of storage. If the base address at M[0][0] is 1840, determine the address at M[4][8] when the matrix is stored in Row Major Wise.

11.

A matrix B[10][7] is stored in the memory with each element requiring 2 bytes of storage. If the base address at B[x][1] is 1012 and the address at B[7][3] is 1060, determine the value ‘x’ where the matrix is stored in Column Major Wise

12. 

A square matrix A [m × m] is stored in the memory with each element requiring 2 bytes of storage. If the base address at A[1][1] is 1098 and the address at A[4][5] is 1144, determine the order of the matrix A[m × m] when the matrix is stored in Column Major Wise

13. 

A character array B[7][6] has a base address 1046 at 0, 0. Calculate the address at B[2][3] if the array is stored in Column Major Wise. Each character requires 2 bytes of storage.

14.

Each element of an array A[20][10] requires 2 bytes of storage. If the address of A[6][8] is 4000, find the base address at A[0][0] when the array is stored in Row Major Wise.

15.

A two-dimensional array defined as X[3…6, -2…2] requires 2 bytes of storage space for each element. If the array is stored in Row Major Wise order, determine the address of X[5][1], given the base address as 1200.

Ans:

1    1660, 2285

2    2206

3    4

4    1610

5    6

6    2256

7    6

8     4366

9    3952

10    2032

11    3

12    5

13    1092

14    3864

15.    1226

MCQ Questions on Sorting

What is the best time complexity of bubble sort?

A N^2

B NlogN

C N

D N(logN)^2

Assume that we use Bubble Sort to sort n distinct elements in ascending order. When does the best case of Bubble Sort occur?

A When elements are sorted in ascending order

B When elements are sorted in descending order

C When elements are not sorted by any order

D There is no best case for Bubble Sort. It always takes O(n*n) time

The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order, using bubble sort is

A 11

B 12

C 13

D 10

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

A O(n^2 Logn)

B O(n^2)

C O(n Logn Logn)

D O(nLogn)

Which of the following is not a stable sorting algorithm in its typical implementation.

A Insertion Sort

B Merge Sort

C Quick Sort

D Bubble Sort

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

A Quick Sort

B Heap Sort

C Merge Sort

D Insertion Sort

Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

A Heap Sort

B Selection Sort

C Insertion Sort

D Merge Sort

Which of the following is not true about comparison based sorting algorithms?

A The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array

B Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared

C Counting Sort is not a comparison based sorting algortihm

D Heap Sort is not a comparison based sorting algorithm.

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2  5  1  7  9  12  11  10 

Which statement is correct?

A The pivot could be either the 7 or the 9.

B The pivot could be the 7, but it is not the 9

C The pivot is not the 7, but it could be the 9

D Neither the 7 nor the 9 is the pivot

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

A Heap sort

B Merge sort

C Quick sort

D Insertion sort

Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.

A Insertion Sort

B Heap Sort

C Merge Sort

D Selection Sort

Which of the following sorting algorithms has the lowest worst-case complexity?

A Merge Sort

B Bubble Sort

C Quick Sort

D Selection Sort

Which sorting algorithms is most efficient to sort string consisting of ASCII characters?

A Quick sort

B Heap sort

C Merge sort

D Counting sort

Which of the following is true about merge sort?

A Merge Sort works better than quick sort if data is accessed from slow sequential memory.

B Merge Sort is stable sort by nature

C Merge sort outperforms heap sort in most of the practical situations.

D     All of the above.

Given an array where numbers are in range from 1 to n^6, which sorting algorithm can be used to sort these number in linear time?

A Not possible to sort in linear time

B Radix Sort

C Counting Sort

D Quick Sort