Design And Analysis Of Algorithms Set 7

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 7

Q1 | Which of the following is false in the case of a spanning tree of a graph G?
  • it is tree that spans g
  • it is a subgraph of the g
  • it includes every vertex of the g
  • it can be either cyclic or acyclic
Answer: it can be either cyclic or acyclic
Explaination:
a graph can have many spanning trees. each spanning tree of a graph g is a subgraph of the graph g, and spanning trees include every vertex of the gram.
Q2 | Every graph has only one minimum spanning tree.
  • true
  • false
Answer: false
Explaination:
minimum spanning tree is a spanning tree with the lowest cost among all the spacing trees. sum of all of the edges in the spanning tree is the cost of the spanning tree. there can be many minimum spanning trees for a given graph.
Q3 | Consider a complete graph G with 4 vertices. The graph G has          spanning trees.
  • 15
  • 8
  • 16
  • 13
Answer: 16
Explaination:
a graph can have many spanning trees. and a complete graph with n vertices has n(n-2) spanning trees. so, the complete graph with 4 vertices has 4(4-2) = 16 spanning trees.
Q4 | The travelling salesman problem can be solved using                    
  • a spanning tree
  • a minimum spanning tree
  • bellman – ford algorithm
  • dfs traversal
Answer: a minimum spanning tree
Explaination:
in the travelling salesman problem we have to find the shortest possible route that visits every city exactly once and returns to the starting point for the given a set of cities. so, travelling salesman problem can be solved by contracting the minimum spanning tree.
Q5 | Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?
  • graph m has no minimum spanning tree
  • graph m has a unique minimum spanning trees of cost 2
  • graph m has 3 distinct minimum spanning trees, each of cost 2
  • graph m has 3 spanning trees of different costs
Answer: graph m has 3 distinct minimum spanning trees, each of cost 2
Explaination:
here all non-diagonal elements in the adjacency matrix are 1. so, every vertex is connected every other vertex of the graph. and, so graph m has 3 distinct minimum spanning trees.
Q6 | Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
  • every minimum spanning tree of g must contain cd
  • if ab is in a minimum spanning tree, then its removal must disconnect g
  • no minimum spanning tree contains ab
  • g has a unique minimum spanning tree
Answer: no minimum spanning tree contains ab
Explaination:
every mst will contain cd as it is smallest edge. so, every minimum spanning tree of g must contain cd is true. and g has a unique minimum spanning tree is also true because the graph has edges with distinct weights. so, no minimum spanning tree contains ab is false.
Q7 | If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.
  • true
  • false
Answer: true
Explaination:
a subgraph is a graph formed from a subset of the vertices and edges of the original graph. and the subset of vertices includes all endpoints of the subset of the edges. so, we can say mst of a graph is a subgraph when all weights in the original graph are positive.
Q8 | Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
  • (a-c)(c-d)(d-b)(d-b)
  • (c-a)(a-d)(d-b)(d-e)
  • (a-d)(d-c)(d-b)(d-e)
  • (c-a)(a-d)(d-c)(d-b)(d-e)
Answer: (a-d)(d-c)(d-b)(d-e)
Explaination:
the minimum spanning tree of the given graph is shown below. it has cost
Q9 | Which of the following is not the algorithm to find the minimum spanning tree of the given graph?
  • boruvka’s algorithm
  • prim’s algorithm
  • kruskal’s algorithm
  • bellman–ford algorithm
Answer: bellman–ford algorithm
Explaination:
the boruvka’s algorithm, prim’s algorithm and kruskal’s algorithm are the algorithms that can be used to find the minimum spanning tree of the given graph. the bellman-ford algorithm is used to find the shortest path from the single source to all other vertices.
Q10 | Which of the following is false?
  • the spanning trees do not have any cycles
  • mst have n – 1 edges if the graph has n edges
  • edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph
  • removing one edge from the spanning tree will not make the graph disconnected
Answer: removing one edge from the spanning tree will not make the graph disconnected
Explaination:
every spanning tree has n – 1 edges if the graph has n edges and has no cycles. the mst follows the cut property, edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph.
Q11 | Kruskal’s algorithm is used to              
  • find minimum spanning tree
  • find single source shortest path
  • find all pair shortest path algorithm
  • traverse the graph
Answer: find minimum spanning tree
Explaination:
the kruskal’s algorithm is used to find the minimum spanning tree of the connected graph. it construct the mst by finding the edge having the least possible weight that connects two trees in the forest.
Q12 | Kruskal’s algorithm is a              
  • divide and conquer algorithm
  • dynamic programming algorithm
  • greedy algorithm
  • approximation algorithm
Answer: greedy algorithm
Explaination:
kruskal’s algorithm uses a greedy algorithm approach to find the mst of the connected weighted graph. in the greedy method, we attempt to find an optimal solution in stages.
Q13 | What is the time complexity of Kruskal’s algorithm?
  • o(log v)
  • o(e log v)
  • o(e2)
  • o(v log e)
Answer: o(e log v)
Explaination:
kruskal’s algorithm involves sorting of the edges, which takes o(e loge) time, where e is a number of edges in graph and v is the number of vertices. after sorting, all edges are iterated and union-find algorithm is applied. union-find algorithm requires o(logv) time. so, overall kruskal’s algorithm requires o(e log v) time.
Q14 | Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?
  • gf
  • de
  • be
  • bg
Answer: be
Explaination:
in krsuskal’s algorithm the edges are selected and added to the spanning tree in increasing order of their weights.
Q15 | Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?
  • (b-e)(g-e)(e-f)(d-f)
  • (b-e)(g-e)(e-f)(b-g)(d-f)
  • (b-e)(g-e)(e-f)(d-e)
  • (b-e)(g-e)(e-f)(d-f)(d-g)
Answer: (b-e)(g-e)(e-f)(d-f)
Explaination:
using krushkal’s algorithm on the given graph, the generated minimum spanning tree is shown below.
Q16 | Which of the following is false about the Kruskal’s algorithm?
  • it is a greedy algorithm
  • it constructs mst by selecting edges in increasing order of their weights
  • it can accept cycles in the mst
  • it uses union-find data structure
Answer: it can accept cycles in the mst
Explaination:
kruskal’s algorithm is a greedy algorithm to construct the mst of the given graph. it constructs the mst by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. so, using kruskal’s algorithm is never formed.
Q17 | Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
  • true
  • false
Answer: false
Explaination:
prim’s algorithm outperforms the kruskal’s algorithm in case of the dense graphs. it is significantly faster if graph has more edges than the kruskal’s algorithm.
Q18 | Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
  • s1 is true but s2 is false
  • both s1 and s2 are false
  • both s1 and s2 are true
  • s2 is true but s1 is false
Answer: s2 is true but s1 is false
Explaination:
in kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components containing a vertex and adds the new edges. and kruskal’s algorithm always finds the mst for the connected graph.
Q19 | Which of the following is true?
  • prim’s algorithm initialises with a vertex
  • prim’s algorithm initialises with a edge
  • prim’s algorithm initialises with a vertex which has smallest edge
  • prim’s algorithm initialises with a forest
Answer: prim’s algorithm initialises with a vertex
Explaination:
steps in prim’s algorithm: (i) select any vertex of given graph and add it to mst (ii) add the edge of minimum weight from a vertex not in mst to the vertex in mst; (iii) it mst is complete the stop, otherwise go to step (ii).
Q20 | Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
  • o(log v)
  • o(v2)
  • o(e2)
  • o(v log e)
Answer: o(v2)
Explaination:
use of adjacency matrix provides the simple implementation of the prim’s algorithm. in prim’s algorithm, we need to search for the edge with a minimum for that vertex. so, worst case time complexity will be o(v2), where v is the number of vertices.
Q21 | Prim’s algorithm is a              
  • divide and conquer algorithm
  • greedy algorithm
  • dynamic programming
  • approximation algorithm
Answer: greedy algorithm
Explaination:
prim’s algorithm uses a greedy algorithm approach to find the mst of the connected weighted graph. in greedy method, we attempt to find an optimal solution in stages.
Q22 | Prim’s algorithm resembles Dijkstra’s algorithm.
  • true
  • false
Answer: true
Explaination:
in prim’s algorithm, the mst is constructed starting from a single vertex and adding in new edges to the mst that link the partial tree to a new vertex outside of the mst. and dijkstra’s algorithm also rely on the similar approach of finding the next closest vertex. so, prim’s algorithm
Q23 | Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
  • true
  • false
Answer: true
Explaination:
prim’s algorithm and kruskal’s algorithm perform equally in case of the sparse graphs. but kruskal’s algorithm is simpler and easy to work with. so, it is best suited for sparse graphs.
Q24 | Prim’s algorithm can be efficiently implemented using            for graphs with greater density.
  • d-ary heap
  • linear search
  • fibonacci heap
  • binary search
Answer: d-ary heap
Explaination:
in prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. this searching can be efficiently implemented using binary heap for dense graphs. and for graphs with greater density, prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap).
Q25 | Which of the following is false about Prim’s algorithm?
  • it is a greedy algorithm
  • it constructs mst by selecting edges in increasing order of their weights
  • it never accepts cycles in the mst
  • it can be implemented using the fibonacci heap
Answer: it constructs mst by selecting edges in increasing order of their weights
Explaination:
prim’s algorithm can be implemented using fibonacci heap and it never accepts cycles. and prim’s algorithm follows greedy approach. prim’s algorithms
Previous Next