Data Structres

Which of these best describes an array?

• A data structure that shows a hierarchical behavior

• Container of objects of similar types

• Arrays are immutable once initialised

• Array is not a data structure

Answer explanation

Array contains elements only of the same type.

What are the disadvantages of arrays?

• Data structure like queue or stack cannot be implemented

• There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size

• Index value of an array can be negative

• Elements are sequentially accessed

Answer explanation

Arrays are of fixed size. If we insert elements less than the allocated size, unoccupied positions can’t be used again. Wastage will occur in memory.

Elements in an array are accessed _____________

• randomly

• sequentially

• exponentially

• logarithmically

Answer explanation

Elements in an array are accessed randomly. In Linked lists, elements are accessed sequentially.

What is the time complexity of pop() operation when the stack is implemented using an array?

• O(1)

• O(n)

• O(log n)

• O(n log n)

Answer explanation

pop() accesses only one end of the structure, and hence constant time.

Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack > N)?

• S[N-1]

• S[N]

• S[N-2]

• S[N+1]

Answer explanation

Array indexing start from 0, hence N-1 is the last index.

In a stack, if a user tries to remove an element from an empty stack it is called _________

• Underflow

• Empty collection

• Overflow

• Garbage Collection

Answer explanation

Underflow occurs when the user performs a pop operation on an empty stack. Overflow occurs when the stack is full and the user performs a push operation. Garbage Collection is used to recover the memory occupied by objects that are no longer used.

What is the value of the postfix expression 6 3 2 4 + – *?

• 1

• 74

• 40

• -18

Answer explanation

Postfix Expression is (6*(3-(2+4))) which results -18 as output.

Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?

• 1

• 2

• 3

• 4

Answer explanation

When we perform the conversion from infix to postfix expression +, *, (, * symbols are placed inside the stack. A maximum of 4 symbols are identified during the entire conversion.

The postfix form of the expression (A+ B)*(C*D- E)*F / G is?

• AB+ CD*E – FG /**

• AB + CD* E – F **G /

• AB + CD* E – F G /

• AB + CDE – F *G /

Answer explanation

(((A+ B)*(C*D- E)*F) / G) is converted to postfix expression as(AB+(*(C*D- E)*F )/ G)(AB+CD*E-*F) / G(AB+CD*E-*F G/). Thus Postfix expression is AB+CDE-*F*G/

The data structure required to check whether an expression contains a balanced parenthesis is?

• Stack

• Queue

• Array

• Tree

Answer explanation

The stack is a simple data structure in which elements are added and removed based on the LIFO principle. Open parenthesis is pushed into the stack and a closed parenthesis pops out elements till the top element of the stack is its corresponding open parenthesis. If the stack is empty, parenthesis is balanced otherwise it is unbalanced.