Trees and Graphs MCQs, Set 1 of 1
Q1 / 14
Q1. What is the maximum number of children a node can have in a binary tree?
- A.1
- B.2(correct answer)
- C.3
- D.Unlimited
Binary means each node has at most two children: left and right.
Q2. Which traversal of a binary search tree visits the keys in sorted order?
- A.Preorder
- B.Inorder(correct answer)
- C.Postorder
- D.Level order
Inorder visits left subtree, node, then right subtree, which gives ascending order in a BST.
Q3. What is the height of a balanced binary search tree with n nodes?
- A.O(1)
- B.O(log n)(correct answer)
- C.O(n)
- D.O(n²)
Each level doubles the number of nodes, so height grows logarithmically.
Q4. A tree with n nodes has exactly how many edges?
- A.n
- B.n - 1(correct answer)
- C.n + 1
- D.2n
Every node except the root has exactly one edge to its parent.
Q5. What is the worst-case search time in an unbalanced binary search tree?
- A.O(1)
- B.O(log n)
- C.O(n)(correct answer)
- D.O(n log n)
If keys are inserted in sorted order the tree becomes a chain, like a linked list.
Q6. Which of these is a self-balancing binary search tree?
- A.Max heap
- B.AVL tree(correct answer)
- C.Trie
- D.Huffman tree
An AVL tree uses rotations to keep subtree heights within 1 of each other.
Q7. In a max-heap, the largest element is always at the:
- A.Leftmost leaf
- B.Root(correct answer)
- C.Rightmost leaf
- D.Last level
Every parent is greater than or equal to its children, so the maximum is at the root.
Q8. Depth-first search (DFS) is usually implemented with a:
- A.Queue
- B.Stack or recursion(correct answer)
- C.Heap
- D.Hash table
DFS goes as deep as possible first, which a stack (or the call stack) naturally does.
Q9. A connected undirected graph with no cycles is called a:
- A.Tree(correct answer)
- B.Complete graph
- C.Bipartite graph
- D.Directed acyclic graph
This is the definition of a tree in graph theory.
Q10. Which representation is most space-efficient for a sparse graph?
- A.Adjacency matrix
- B.Adjacency list(correct answer)
- C.Incidence matrix
- D.Distance matrix
An adjacency list uses O(V + E) space; a matrix always uses O(V²).
Q11. What is the maximum number of edges in a simple undirected graph with n vertices?
- A.n - 1
- B.n
- C.n(n - 1)/2(correct answer)
- D.n²
Every pair of distinct vertices can have at most one edge: n choose 2.
Q12. Dijkstra’s algorithm finds:
- A.A minimum spanning tree
- B.Shortest paths from one source when weights are non-negative(correct answer)
- C.All cycles in a graph
- D.A topological order
It greedily settles the closest unvisited vertex; negative weights break it.
Q13. Which algorithm finds a minimum spanning tree?
- A.Kruskal’s algorithm(correct answer)
- B.Dijkstra’s algorithm
- C.Floyd-Warshall algorithm
- D.Binary search
Kruskal’s (and Prim’s) build a minimum spanning tree; the others solve shortest paths or searching.
Q14. A topological sort is possible only for a:
- A.Complete graph
- B.Directed acyclic graph (DAG)(correct answer)
- C.Undirected tree
- D.Weighted graph
A cycle would mean some vertex must come before itself.