Unit IV · Viva Questions
Revise the concepts orally; open a study answer when you need more detail.
Explain the stack ADT and array-based push, pop and peek.
- Does peek remove the top item?
- No.
- Is an empty top index the same as the first valid stored index?
- No. -1 marks empty and 0 is the first stored position.
Explain a stack implemented using a singly linked list.
- Can a linked stack overflow in practice?
- Yes. Allocation or resource limits can prevent a push.
- Why not use the tail as top in a singly linked stack?
- Removing the last node would normally require a predecessor search.
Trace the supplied sequence of stack operations and find the final peek.
- Did the maximum count exceed capacity 10?
- No. The maximum count in this trace is 7.
- Does final peek change the final count?
- No.
Explain infix-to-postfix conversion using a stack with worked expressions.
- Is C’s ^ operator exponentiation?
- No. It is bitwise XOR; this example uses $ as exercise notation.
- Why do equal $ operators not pop on arrival?
- The exercise treats exponentiation as right-associative.
Explain postfix evaluation using a stack with the supplied numerical expression.
- What final stack size indicates a complete valid expression?
- Exactly one value.
- Why must division check the right operand?
- It is the divisor and must not be zero.
Explain balancing parentheses, brackets and braces using a stack.
- Why is ([)] invalid despite equal counts?
- The nesting types close in the wrong order.
- What does a non-empty final stack mean?
- Some opening symbols were never closed.
Explain expression trees, construction from postfix and traversals.
- Why pop right before left when constructing a binary operator node?
- The postfix stack’s top is the completed right operand subtree.
- Does plain inorder always preserve arithmetic grouping?
- No. Parentheses may be necessary.
Explain the queue ADT, operations, overflow, underflow and applications.
- Is a queue automatically a priority queue?
- No.
- Can -1 be a valid stored item when failure is reported separately?
- Yes.
Explain a circular array queue with full and empty conditions.
- Is physical array order always queue order after wraparound?
- No. Traverse logically from front for count elements.
- Does this implementation reserve an unused slot?
- No. The separate count distinguishes full and empty.
Explain a queue implemented using a singly linked list.
- What happens to rear after the last node is removed?
- It becomes NULL.
- Does allocation failure require removing an existing item?
- No. Failed enqueue leaves the queue unchanged.
Compare stacks and queues and explain a queue implemented using two stacks.
- Must a queue implemented with two stacks transfer on every dequeue?
- No. Transfer only when the output stack is empty.
- Is amortised O(1) the same as worst-case O(1) for each dequeue?
- No.