Unit V · Viva Questions
Revise the concepts orally; open a study answer when you need more detail.
Explain tree terminology and common types of binary trees.
- Does every binary tree obey sorted-search order?
- No.
- What is the edge-based height of a leaf?
- Zero.
Explain conversion of a general rooted tree to left-child/right-sibling representation.
- Is the right link always an original child?
- No. It identifies the next sibling.
- What should the root’s next-sibling link be for one tree?
- NULL.
Explain preorder, inorder and postorder binary-tree traversals.
- Does inorder always output sorted values?
- Only when the tree has the appropriate BST ordering property.
- Which order naturally processes children before their parent?
- Postorder.
Define the BST ADT and explain searching.
- Is every BST automatically height-balanced?
- No.
- What result should an empty-root search return?
- Not found.
Explain BST insertion with an example.
- Why save the returned root in a recursive interface?
- Insertion into an empty subtree creates a new root pointer.
- Does a duplicate allocate another node in this example?
- No.
Explain all BST deletion cases with an algorithm.
- Why does the successor have no left child?
- It is the minimum in that subtree.
- Should the root return value be ignored after deletion?
- No. Deleting a root can change it.
Define graphs and explain common graph types.
- Does one directed edge imply its reverse?
- No.
- Why can graph traversal need a visited array?
- Cycles and multiple paths can revisit the same vertex.
Compare adjacency matrices and adjacency lists.
- Is every graph adjacency matrix symmetric?
- No. A directed graph need not be symmetric.
- Why are lists often useful for sparse graphs?
- They avoid storing every absent vertex pair.
Explain depth-first search with an algorithm and example.
- Can another neighbour order produce a different valid DFS sequence?
- Yes.
- Does a single DFS start necessarily cover a disconnected graph?
- No. Restart from other unvisited vertices to cover it.
Explain breadth-first search and its queue operations.
- Does BFS guarantee minimum total weight for arbitrary weighted edges?
- No.
- Why can a V-capacity queue suffice when each vertex is enqueued once?
- At most V distinct vertices enter during that traversal.
Compare DFS and BFS with the same graph.
- Can both traversals visit every vertex of a connected undirected graph?
- Yes, from any vertex with correct visited handling.
- Does BFS always use less memory than DFS?
- No. It depends on shape and pending work.
Explain a graph ADT and applications of graphs.
- Does a graph ADT require an adjacency matrix?
- No.
- Why define whether an edge is directed?
- It changes reachability, representation and neighbour semantics.
Represent the supplied five-city flight network as a directed graph, matrix and lists.
- What is city 5’s out-degree here?
- Four.
- Does city 1 have an outgoing flight to city 5 in this table?
- No. The supplied edge is 5→1.