Spanning Trees MCQ

Test your knowledge with important Spanning Trees MCQ and their applications. These MCQs are beneficial for competitive exams too. Explore 30 + more Spanning Trees MCQs at Bissoy

• Prim’s algorithm can be implemented using _______
  ক

  a stack data structure

  খ

  radix sort

  গ

  priority queue data structure

  ঘ

  bubble sort
• In a maximum spanning tree the weighted graph is of _______
  ক

  maximum number of edges

  খ

  maximum number of cyclic trees

  গ

  minimum number of vertices

  ঘ

  maximum weight
• The spanning tree will be maximally acyclic if ____________
  ক

  one additional edge makes a cycle in the tree

  খ

  two additional edges makes a cycle in the tree

  গ

  removing one edge makes the tree cycle free

  ঘ

  removing two edges make the tree cycle free
• A complete undirected graph of n nodes can have maximum ______ spanning trees.
  ক

  nn+1

  খ

  nn-2

  গ

  \(\frac{n(n+1)}{2}\)

  ঘ

  n
• If minimum cost edge of a graph is unique, then that edge will be added to any MST. Choose the correct option.
  ক

  false

  খ

  maximum cost edge is added

  গ

  true

  ঘ

  minimum cost edge need not be unique
• An immediate application of minimum spanning tree ______
  ক

  gesture analysis

  খ

  handwriting recognition

  গ

  fingerprint detection

  ঘ

  soft computing
• Time complexity of Prim’s algorithm is _________
  ক

  O((V+E)logV)

  খ

  O(E+V)

  গ

  O(E)

  ঘ

  O(V+1)
• For every spanning tree with n vertices and n edges what is the least number of different Spanning trees can be formed?
  ক

  2

  খ

  5

  গ

  3

  ঘ

  4
• If the weight of an edge e of cycle C in a graph is larger than the individual weights of all other edges of C, then that edge ________
  ক

  belongs to an minimum spanning tree

  খ

  cannot belong to an minimum spanning tree

  গ

  belongs to all MSTs of the graph

  ঘ

  can not belong to the graph
• Spanning trees have a special class of depth-first search trees named _________
  ক

  Euclidean minimum spanning trees

  খ

  Tremaux trees

  গ

  Complete bipartite graphs

  ঘ

  Decision trees