Home › Quizzes › Trees and Forests

Trees and Forests

This quiz covers various concepts related to trees and forests in graph theory.

15 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

Which of the following statements is true about a tree?

  1. It is a connected graph.
  2. It has no cycles.
  3. It has a unique path between any two vertices.
  4. All of the above.
Question 2 Multiple Choice (Single Answer)

What is the maximum number of edges in a tree with n vertices?

  1. n-1
  2. n
  3. n+1
  4. 2n-1
Question 3 Multiple Choice (Single Answer)

Which of the following is a forest?

  1. A graph with no cycles.
  2. A graph with no isolated vertices.
  3. A graph in which every connected component is a tree.
  4. All of the above.
Question 4 Multiple Choice (Single Answer)

What is the minimum number of edges in a forest with n vertices?

  1. 0
  2. 1
  3. n-1
  4. n
Question 5 Multiple Choice (Single Answer)

Which of the following algorithms can be used to find a minimum spanning tree of a weighted graph?

  1. Kruskal's algorithm
  2. Prim's algorithm
  3. Dijkstra's algorithm
  4. Floyd-Warshall algorithm
Question 6 Multiple Choice (Single Answer)

What is the time complexity of Kruskal's algorithm for finding a minimum spanning tree?

  1. O(E log E)
  2. O(E log V)
  3. O(V log V)
  4. O(V^2)
Question 7 Multiple Choice (Single Answer)

Which of the following is a property of a binary tree?

  1. It has at most two children for each node.
  2. It has a unique path from the root to each node.
  3. It is a complete tree.
  4. All of the above.
Question 8 Multiple Choice (Single Answer)

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

  1. 2^h
  2. 2^(h+1) - 1
  3. 2^(h+1)
  4. 2^(h+2) - 1
Question 9 Multiple Choice (Single Answer)

Which of the following is a traversal method for a binary tree?

  1. Inorder traversal
  2. Preorder traversal
  3. Postorder traversal
  4. All of the above.
Question 10 Multiple Choice (Single Answer)

What is the time complexity of inorder traversal of a binary tree?

  1. O(log V)
  2. O(V)
  3. O(V log V)
  4. O(V^2)
Question 11 Multiple Choice (Single Answer)

Which of the following is a type of tree data structure?

  1. Binary search tree
  2. Red-black tree
  3. AVL tree
  4. All of the above.
Question 12 Multiple Choice (Single Answer)

What is the property of a binary search tree?

  1. The left child of a node is always smaller than the node.
  2. The right child of a node is always larger than the node.
  3. Both of the above.
  4. None of the above.
Question 13 Multiple Choice (Single Answer)

Which of the following is a type of forest data structure?

  1. Trie
  2. Suffix tree
  3. Patricia tree
  4. All of the above.
Question 14 Multiple Choice (Single Answer)

What is the property of a trie?

  1. It is a tree-like data structure.
  2. It is used for storing strings.
  3. It allows for efficient searching and retrieval of strings.
  4. All of the above.
Question 15 Multiple Choice (Single Answer)

Which of the following is a type of tree decomposition?

  1. Nice tree decomposition
  2. Path decomposition
  3. Treewidth decomposition
  4. All of the above.
← Back to Quizzes