Trees & Graphs Quiz

Explore foundational concepts of trees and graphs in programming fundamentals, including traversal, properties, and algorithms. Sharpen your understanding of key characteristics and operations in modern data structures.

1. Maximum Nodes in Binary Tree

   What is the maximum number of nodes in a binary tree of height h?

   1. 2*h + 1
   2. 2^(h+1) – 1
   3. h^2 + 1
   4. 2^h – 1

   Explanation: The maximum number of nodes in a binary tree of height h is 2^(h+1) – 1. This represents a perfectly balanced (full) binary tree. '2*h + 1' and 'h^2 + 1' do not reflect the exponential growth of nodes. '2^h – 1' is the total for a tree of height h-1, not h.

2. Inorder Traversal of BST

   In a binary search tree (BST), an inorder traversal produces nodes in which order?

   1. Reverse order
   2. Sorted order
   3. Level order
   4. Random order

   Explanation: Inorder traversal of a BST visits nodes in left-root-right order, producing values in sorted ascending order. 'Random order' and 'reverse order' are incorrect; 'level order' is achieved using breadth-first traversal, not inorder.

3. Traversal for Expression Tree Evaluation

   Which tree traversal is typically used to evaluate arithmetic expression trees?

   1. Postorder
   2. Inorder
   3. Preorder
   4. Level order

   Explanation: Postorder traversal evaluates subtrees before the root, ideal for expression tree evaluation where operands must be processed before their operators. Preorder and inorder do not guarantee this evaluation order; level order is used for breadth-first operations, not evaluation.

4. Time Complexity of DFS

   What is the time complexity of Depth First Search (DFS) in a graph with V vertices and E edges?

   1. O(V^2)
   2. O(E^2)
   3. O(V + E)
   4. O(V*E)

   Explanation: DFS explores each vertex and edge once, giving O(V + E) time complexity. O(V^2), O(V*E), and O(E^2) are incorrect; these describe more resource-intensive operations uncommon in standard DFS.

5. Data Structure Used by BFS

   Which data structure is most commonly used to implement Breadth-First Search (BFS) in graphs or trees?

   1. Array
   2. Heap
   3. Queue
   4. Stack

   Explanation: BFS uses a queue to maintain the order of processing nodes level by level. Stack is associated with DFS, array can store nodes but doesn't maintain desired order, and heap is not related to BFS traversal control.

6. Height of Single Node Tree

   What is the height of a tree with only a single node?

   1. 1
   2. 2
   3. -1
   4. 0

   Explanation: A tree with one node (the root) has height 0, as height is the number of edges to the deepest leaf. Height 1 or 2 would require additional nodes; -1 is not a conventional tree height.

7. Complete Binary Tree

   In a complete binary tree, all levels except possibly the last are completely filled. True or False?

   1. False
   2. Sometimes True
   3. Cannot determine
   4. True

   Explanation: A complete binary tree fills every level except possibly the last, which is filled from left to right. 'False' contradicts the definition. The state is not contingent ('Sometimes True') nor undeterminable if the tree is described as complete.

8. Shortest Path Algorithm in Weighted Graph

   Which algorithm is commonly used to find the shortest path in a weighted graph?

   1. Bubble Sort
   2. DFS
   3. Prim's Algorithm
   4. Dijkstra's Algorithm

   Explanation: Dijkstra's Algorithm efficiently finds shortest paths in weighted (non-negative) graphs. Prim's is for minimum spanning trees, Bubble Sort is for arrays, and DFS doesn't guarantee shortest paths.

9. Topological Sorting Possibility

   Topological sorting is possible only in which type of graph?

   1. Directed Acyclic Graph (DAG)
   2. Undirected graph
   3. Graph with cycles
   4. Complete graph

   Explanation: Topological sorting orders nodes when dependencies exist, possible only in directed acyclic graphs (DAGs). Graphs with cycles or undirected/complete graphs do not support meaningful topological order.

10. Binary Search Tree Property

    Which property holds for a Binary Search Tree (BST)?

    1. Left = Right > Root
    2. Root < Left < Right
    3. Left < Root < Right
    4. All nodes have two children

    Explanation: BSTs require left subtree values to be less than the root, and right subtree values to be greater. 'Root < Left < Right' is incorrect order, 'Left = Right > Root' is not required, and not all nodes must have two children.