DAA QUIZ-II

Dijkstra’s Algorithm is the prime example for ___________

• Dynamic Programming

• Backtracking

• Branch & Bound

• Greedy Algorithm

Fractional knapsack problem is solved most efficiently by which of the following algorithm?

• Backtracking

• Greedy algorithm

• Dynamic programming

• Divide and conquer

Which of the following is false about the Kruskal’s algorithm?

• It constructs MST by selecting edges in increasing order of their weights

• It is a greedy algorithm

• It uses union-find data structure

• It can accept cycles in the MST

Consider the given graph.
What is the weight of the minimum spanning tree using the Kruskal’s algorithm?

• 24

• 23

• 15

• 19

What is the time complexity of Kruskal’s algorithm?

• O(log V)
  

• O(E log V)
  

• O(E²)
  

• O(V log E)

Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?

• GF

• DE

• BE

• BG

Every graph has only one minimum spanning tree.

• TRUE

• FALSE

Dijkstra’s Algorithm is used to solve _____________ problems.

• All pair shortest path
  

• Single source shortest path
  

• Network flow
  

• Sorting

What is the time complexity of Dijikstra’s algorithm?

• O(N)

• O(N^2)

• O(N^3)

• O(Log N)

Dijkstra’s Algorithm cannot be applied on ______________

• a) Directed and weighted graphs
  

• b) Graphs having negative weight function
  

• c) Unweighted graphs
  

• d) Undirected and unweighted graphs