Question

Q1.

A.

What is the complexity of partition process in quick sort?

O(1)

O(logN)

O(N)

O(NlogN)

B.

Evaluate the following postfix expression.

2 3 4 + *

C.

In an array representation of heap, what are the parent node of a node a[10]?

a[9]

a[11]

a[5]

a[20]

There is no easy way to access parent node in such representation.

D.

In an array representation of heap, what are the children nodes (if any) of a node a[10]?

a[11] and a[12]

a[9] and a[11]

a[5] and a[6]

a[20] and a[21]

There is no easy way to access children nodes in such representation.

Answer 1

A. O(1)

Explanation: partition is just the swapping process and getting the mid index which can be done in constant time.

B. 14  

Explanation:

The given expression is 2 3 4 + *, we can scan all elements one by one

1. Scan “2”, it’s a number so push it to the stack. Stack contains “2”.

2. Scan “3”, it’s a number so push it to the stack. Stack contains “2 3”.

3. Scan “4”, it’s a number so push it to the stack. Stack contains “2 3 4”.

4. Scan “+”, it’s an operator, so pop last two elements from stack, apply the + operator, we get 3+4=7, We push the “7” to the stack. Stack contains “2 7”,

5. Scan “*”, it’s an operator so pop last two elements from stack, apply the * operator, we get 2 * 7 = 14. We push 14 to the stack. Stack contains “14”.

6. There are no more elements to scan, we return the top element from stack

C. A[5]

Explanation:

Parent node in array representation can be found using A[ceil(i - 1 / 2)], so in this case

i = 10

i - 1 / 2 = (10 - 1 / 2) = ceil(4.5) = 5

So A[5]

D. Answer will be A[21] and A[22]

Explanation:

Left child can be found using A[ ( 2 * i) + 1] = A[ 2*10 + 1] = A[21]

Right child can found using A[ (2 * i) + 2] = A[ 2*10 + 2] = A[22]