# Shortest Path in Data Structure and Algorithms MCQs

Q1. What is the time complexity of Dijikstra’s algorithm?.

A.  O(N).

B.  O(N3).

C.  O(N^2).

D.  O(logN).

Q2. 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.

Answer=  Graphs having negative weight function

Q3. How many priority queue operations are involved in Dijkstra’s Algorithm?.

A. 1.

B. 3.

C. 2.

D. 4.

Q4. How many times the insert and extract min operations are invoked per vertex?.

A. 1.

B. 2.

C. 3.

D. 0.

Q5. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to ___________.

A.  Total number of vertices.

B.  Total number of edges.

C.  Number of vertices – 1.

D.  Number of edges – 1.

Q6. What is running time of Dijkstra’s algorithm using Binary min- heap method?.

A.  O(V).

B.  O(VlogV).

C.  O(E).

D.  O(ElogV).

Q7. Dijkstra’s Algorithm is the prime example for ___________.

A.  Greedy algorithm.

B.  Branch and bound.

C.  Back tracking.

D.  Dynamic programming.

Q8. The Bellmann Ford algorithm returns _______ value..

A.  Boolean.

B.  Integer.

C.  String.

D.  Double.

Q9. Bellmann ford algorithm provides solution for ____________ problems..

A.  All pair shortest path.

B.  Sorting.

C.  Network flow.

D.  Single source shortest path.

Q10. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q11. What is the running time of Bellmann Ford Algorithm?.

A.  O(V).

B.  O(V2).

C.  O(ElogV).

D.  O(VE).

Q12. How many times the for loop in the Bellmann Ford Algorithm gets executed?.

A.  V times.

B.  V-1.

C.  E.

D.  E-1.

Q13. What is the basic principle behind Bellmann Ford Algorithm?.

A.  Interpolation.

B.  Extrapolation.

C.  Regression.

D.  Relaxation.

Q14. Bellmann Ford Algorithm can be applied for _____________.

A.  Undirected and weighted graphs.

B.  Undirected and unweighted graphs.

C.  Directed and weighted graphs.

D.  All directed graphs.

Q15. Bellmann Ford algorithm was first proposed by ________.

A.  Richard Bellmann.

B.  Alfonso Shimbe.

C.  Lester Ford Jr.

D.  Edward F. Moore.

Q16. Bellmann Ford Algorithm is an example for ____________.

A.  Dynamic Programming.

B.  Greedy Algorithms.

C.  Linear Programming.

D.  Branch and Bound.

Q17. A graph is said to have a negative weight cycle when?.

A.  The graph has 1 negative weighted edge.

B.  The graph has a cycle.

C.  The total weight of the graph is negative.

D.  The graph has 1 or more negative weighted edges.

Answer=  The total weight of the graph is negative

Q18. Floyd Warshall’s Algorithm is used for solving ____________.

A.  All pair shortest path problems.

B.  Single Source shortest path problems.

C.  Network flow problems.

D.  Sorting problems.

Answer=  All pair shortest path problems

Q19. Floyd Warshall’s Algorithm can be applied on __________.

A.  Undirected and unweighted graphs.

B.  Undirected graphs.

C.  Directed graphs.

D.  Acyclic graphs.

Q20. What is the running time of the Floyd Warshall Algorithm?.

A.  Big-oh(V).

B.  Theta(V2).

C.  Big-Oh(VE).

D.  Theta(V3).

Q21. What approach is being followed in Floyd Warshall Algorithm?.

A.  Greedy technique.

B.  Dynamic Programming.

C.  Linear Programming.

D.  Backtracking.

Q22. Floyd Warshall Algorithm can be used for finding _____________.

A.  Single source shortest path.

B.  Topological sort.

C.  Minimum spanning tree.

D.  Transitive closure.

Q23. What procedure is being followed in Floyd Warshall Algorithm?.

A.  Top down.

B.  Bottom up.

C.  Big bang.

D.  Sandwich.

Q24. Floyd- Warshall algorithm was proposed by ____________.

A.  Robert Floyd and Stephen Warshall.

B.  Stephen Floyd and Robert Warshall.

C.  Bernad Floyd and Robert Warshall.

D.  Robert Floyd and Bernad Warshall.

Answer=  Robert Floyd and Stephen Warshall

Q25. Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?.

A.  Robert Floyd.

B.  Stephen Warshall.

C.  Bernard Roy.

D.  Peter Ingerman.

Q26. What happens when the value of k is 0 in the Floyd Warshall Algorithm?.

A.  1 intermediate vertex.

B.  0 intermediate vertex.

C.  N intermediate vertices.

D.  N-1 intermediate vertices.

Q27. What is the formula to compute the transitive closure of a graph?.

A.  tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1)).

B.  tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1)).

C.  tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1)).

D.  tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1)).

Answer=  tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))

Q28. What does Maximum flow problem involve?.

A.  finding a flow between source and sink that is maximum.

B.  finding a flow between source and sink that is minimum.

C.  finding the shortest path between source and sink.

D.  computing a minimum spanning tree.

Answer=  finding a flow between source and sink that is maximum

Q29. How many 2*2 matrices are used in this problem?.

A. 1.

B. 2.

C. 3.

D. 4.

Q30. What happens when a free man approaches a married woman?.

A.  She simply rejects him.

B.  She simply replaces her mate with him.

C.  She goes through her preference list and accordingly, she replaces her current mate with him.

D.  She accepts his proposal.

Answer=  She goes through her preference list and accordingly, she replaces her current mate with him

Q31. In case of stability, how many symmetric possibilities of trouble can occur?.

A. 1.

B. 2.

C. 4.

D. 3.

Q32. Who formulated a straight forward backtracking scheme for stable marriage problem?.

A.  McVitie and Wilson.

B.  Gale.

C.  Ford and Fulkerson.

D.  Dinitz.

Q33. What is the prime task of the stable marriage problem?.

A.  To provide man optimal solution.

B.  To provide woman optimal solution.

C.  To determine stability of marriage.

D.  To use backtracking approach.

Answer=  To determine stability of marriage

Q34. Which of the following problems is related to stable marriage problem?.

A.  Choice of school by students.

B.  N-queen problem.

C.  Arranging data in a database.

D.  Knapsack problem.

Answer=  Choice of school by students

Q35. What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?.

A.  O(N).

B.  O(N log N).

C.  O(N^2).

D.  O(log N).

Q36. _____________ is a matching with the largest number of edges..

A.  Maximum bipartite matching.

B.  Non-bipartite matching.

C.  Stable marriage.

D.  Simplex.

Q37. Maximum matching is also called as maximum cardinality matching..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q38. How many colours are used in a bipartite graph?.

A. 1.

B. 2.

C. 3.

D. 4.

Q39. What is the simplest method to prove that a graph is bipartite?.

A.  It has a cycle of an odd length.

B.  It does not have cycles.

C.  It does not have a cycle of an odd length.

D.  Both odd and even cycles are formed.

Answer=  It does not have a cycle of an odd length

Q40. A matching that matches all the vertices of a graph is called?.

A.  Perfect matching.

B.  Cardinality matching.

C.  Good matching.

D.  Simplex matching.

Q41. What is the length of an augmenting path?.

A.  Even.

B.  Odd.

C.  Depends on graph.

D. 1.

Q42. In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?.

A.  Bipartite matching.

B.  Cardinality matching.

C.  Augmenting.

D.  Weight matching.

Q43. A matching M is maximal if and only if there exists no augmenting path with respect to M..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q44. Which one of the following is an application for matching?.

A.  Proposal of marriage.

B.  Pairing boys and girls for a dance.

C.  Arranging elements in a set.

D.  Finding the shortest traversal path.

Answer=  Pairing boys and girls for a dance

Q45. Which is the correct technique for finding a maximum matching in a graph?.

A.  DFS traversal.

B.  BFS traversal.

C.  Shortest path traversal.

D.  Heap order traversal.

Q46. The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?.

A.  Maximum- mass matching.

B.  Maximum bipartite matching.

C.  Maximum weight matching.

D.  Maximum node matching.

Q47. What is the total number of iterations used in a maximum- matching algorithm?.

A.  [n/2].

B.  [n/3].

C.  [n/2]+n.

D.  [n/2]+1.

Q48. What is the efficiency of algorithm designed by Hopcroft and Karp?.

A.  O(n+m).

B.  O(n(n+m).

C.  O(?n(n+m)).

D.  O(n+2).

Q49. Who was the first person to solve the maximum matching problem?.

A.  Jack Edmonds.

B.  Hopcroft.

C.  Karp.

D.  Claude Berge.

Q50. Which algorithm is used to solve a minimum cut algorithm?.

A.  Gale-Shapley algorithm.

B.  Ford-Fulkerson algorithm.

C.  Stoer-Wagner algorithm.

D.  Prim’s algorithm.

Q51. ___________ is a partition of the vertices of a graph in two disjoint subsets that are joined by atleast one edge..

A.  Minimum cut.

B.  Maximum flow.

C.  Maximum cut.

D.  Graph cut.

Q52. ______________ separates a particular pair of vertices in a graph..

A.  line.

B.  arc.

C.  cut.

D.  flow.

Q53. What is the minimum number of cuts that a graph with ‘n’ vertices can have?.

A.  n+1.

B.  n(n-1).

C.  n(n+1)/2.

D.  n(n-1)/2.

Q54. What is the running time of Karger’s algorithm to find the minimum cut in a graph?.

A.  O(E).

B.  O(.

C. V.

D. 2).

Q55. _____________ is a family of combinatorial optimization problems in which a graph is partitioned into two or more parts with constraints..

A.  numerical problems.

B.  graph partition.

C.  network problems.

D.  combinatorial problems.

Q56. The weight of the cut is not equal to the maximum flow in a network..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q57. __________ is a data structure used to collect a system of cuts for solving min-cut problem..

A.  Gomory-Hu tree.

B.  Gomory-Hu graph.

C.  Dancing tree.

D.  AA tree.

Q58. In how many ways can a Gomory-Hu tree be implemented?.

A. 1.

B. 2.

C. 3.

D. 4.

Q59. The running time of implementing naïve solution to min-cut problem is?.

A.  O(N).

B.  O(N log N).

C.  O(log N).

D.  O(N^2).

Q60. What is the running time of implementing a min-cut algorithm using bidirected edges in a graph?.

A.  O(N).

B.  O(N log N).

C.  O(N4).

D.  O(N^2).

Q61. Which one of the following is not an application of max-flow min-cut algorithm?.

A.  network reliability.

B.  closest pair.

C.  network connectivity.

D.  bipartite matching.

Q62. Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?.

A.  Number of vertices in U = Number of vertices in V.

B.  Sum of degrees of vertices in U = Sum of degrees of vertices in V.

C.  Number of vertices in U > Number of vertices in V.

D.  Nothing can be said.

Answer=  Sum of degrees of vertices in U = Sum of degrees of vertices in V

Q63. A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?.

A.  Number of vertices in U=Number of vertices in V.

B.  Number of vertices in U not equal to number of vertices in V.

C.  Number of vertices in U always greater than the number of vertices in V.

D.  Nothing can be said.

Answer=  Number of vertices in U=Number of vertices in V