In the spanning tree shown, what will be the minimum cost?
Question 2
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph if Q is starting node.
Question 3
Consider a weighted complete graph Gon the vertex set {v1,v2,...vn} such that the weight of the edge (vi, vj) is 2|i-j|. The weight of a minimum spanning tree of G is:
Question 4
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
Question 5
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
Question 6
In the graph shown, which options shows sum as 4
Question 7
Let G = (V,E) be a directed graph with n vertices. A path from vi to vj in G is a sequence of vertices (vi, vi+1, ... ,vj) such that (vk, vk+1) ∈E for all k in i through j - 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follows. Consider the following algorithm. fori = 1 to n for j = 1 to n for k = 1 to n A[j,k] = max(A[j,k], A[j,i] + A[i,k]); Which of the following statements is necessarily true for all j and k after termination of the above algorithm?
Question 8
A binary search tree contains the numbers 1,2,3,4,5,6,7,8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5,3,1,2,4,6,8,7.. If the tree is traversed in post-order, the sequence obtained would be.
Question 9
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
Question 10
Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?
