Unit III · Viva Questions
Revise the concepts orally; open a study answer when you need more detail.
Explain an abstract data type and distinguish interface from implementation.
- Is an ADT identical to one memory layout?
- No.
- Can two different representations implement the same ADT?
- Yes, if their observable operations satisfy its contract.
Explain how to select a suitable data structure.
- Does O(1) relinking imply O(1) search-and-insert?
- No. Finding the position may dominate.
- Why consider how often each operation occurs?
- The overall workload depends on the frequency of each cost.
Define a linear list and explain its common operations.
- Does linear mean sorted ascending?
- No. It describes sequence organisation.
- What should deletion do on an empty list?
- Report failure or follow the defined empty-list contract safely.
Explain singly linked-list representation, creation and traversal.
- Can traversal access current->next after freeing current?
- No. Save the next pointer first.
- What makes a maintained-tail append efficient?
- It avoids searching from head for the last node.
Explain singly linked-list insertion and deletion with algorithms.
- Why track the predecessor when deleting in a singly linked list?
- Its next link must bypass the removed node.
- Does an unsuccessful deletion free any existing node?
- No.
Give an algorithm to delete the last occurrence of a key in a linked list.
- Why can this search not stop at the first match?
- A later duplicate may be the required occurrence.
- What extra update may a tail-based representation need?
- Update tail if the removed node was the last node.
Explain circular singly linked lists and their operations.
- Where is the first node when tail is used?
- At tail->next in a non-empty list.
- Why is a NULL-terminated traversal wrong here?
- The ordinary last link returns to the first node instead of NULL.
Explain doubly linked-list insertion, deletion and traversal.
- Does an extra previous link make key search O(1)?
- No.
- What must remain true after insertion?
- Forward and backward links must agree on neighbouring nodes.
Compare array lists, singly linked lists, circular lists and doubly linked lists.
- Does a tail pointer provide direct access to every middle node?
- No.
- Which representation naturally supports backward traversal?
- A doubly linked list with valid previous links.
Explain searching and counting nodes in a singly linked list.
- What count should an empty list produce?
- Zero.
- Can a returned node pointer be used after that node is deleted?
- No.