Q1. What is the time complexity of Dijikstra’s algorithm?.
A. O(N).
B. O(N3).
C. O(N^2).
D. O(logN).
Answer= O(N^2)
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.
Answer= 3
Q4. How many times the insert and extract min operations are invoked per vertex?.
A. 1.
B. 2.
C. 3.
D. 0.
Answer= 1
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.
Answer= Total number of edges
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).
Answer= O(ElogV)
Q7. Dijkstra’s Algorithm is the prime example for ___________.
A. Greedy algorithm.
B. Branch and bound.
C. Back tracking.
D. Dynamic programming.
Answer= Greedy algorithm
Q8. The Bellmann Ford algorithm returns _______ value..
A. Boolean.
B. Integer.
C. String.
D. Double.
Answer= Boolean
Q9. Bellmann ford algorithm provides solution for ____________ problems..
A. All pair shortest path.
B. Sorting.
C. Network flow.
D. Single source shortest path.
Answer= 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.
Answer= TRUE
Q11. What is the running time of Bellmann Ford Algorithm?.
A. O(V).
B. O(V2).
C. O(ElogV).
D. O(VE).
Answer= 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.
Answer= V-1
Q13. What is the basic principle behind Bellmann Ford Algorithm?.
A. Interpolation.
B. Extrapolation.
C. Regression.
D. Relaxation.
Answer= 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.
Answer= Directed and weighted graphs
Q15. Bellmann Ford algorithm was first proposed by ________.
A. Richard Bellmann.
B. Alfonso Shimbe.
C. Lester Ford Jr.
D. Edward F. Moore.
Answer= Alfonso Shimbe
Q16. Bellmann Ford Algorithm is an example for ____________.
A. Dynamic Programming.
B. Greedy Algorithms.
C. Linear Programming.
D. Branch and Bound.
Answer= Dynamic Programming
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.
Answer= Directed 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).
Answer= Theta(V3)
Q21. What approach is being followed in Floyd Warshall Algorithm?.
A. Greedy technique.
B. Dynamic Programming.
C. Linear Programming.
D. Backtracking.
Answer= Dynamic Programming
Q22. Floyd Warshall Algorithm can be used for finding _____________.
A. Single source shortest path.
B. Topological sort.
C. Minimum spanning tree.
D. Transitive closure.
Answer= Transitive closure
Q23. What procedure is being followed in Floyd Warshall Algorithm?.
A. Top down.
B. Bottom up.
C. Big bang.
D. Sandwich.
Answer= Bottom up
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.
Answer= 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.
Answer= 0 intermediate vertex
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.
Answer= 2
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.
Answer= 2
Q32. Who formulated a straight forward backtracking scheme for stable marriage problem?.
A. McVitie and Wilson.
B. Gale.
C. Ford and Fulkerson.
D. Dinitz.
Answer= McVitie and Wilson
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).
Answer= O(N^2)
Q36. _____________ is a matching with the largest number of edges..
A. Maximum bipartite matching.
B. Non-bipartite matching.
C. Stable marriage.
D. Simplex.
Answer= Maximum bipartite matching
Q37. Maximum matching is also called as maximum cardinality matching..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= TRUE
Q38. How many colours are used in a bipartite graph?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
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.
Answer= Perfect matching
Q41. What is the length of an augmenting path?.
A. Even.
B. Odd.
C. Depends on graph.
D. 1.
Answer= Odd
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.
Answer= Augmenting
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.
Answer= TRUE
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.
Answer= BFS 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.
Answer= Maximum weight 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.
Answer= [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).
Answer= O(?n(n+m))
Q49. Who was the first person to solve the maximum matching problem?.
A. Jack Edmonds.
B. Hopcroft.
C. Karp.
D. Claude Berge.
Answer= Jack Edmonds
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.
Answer= Stoer-Wagner 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.
Answer= Minimum cut
Q52. ______________ separates a particular pair of vertices in a graph..
A. line.
B. arc.
C. cut.
D. flow.
Answer= cut
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.
Answer= 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).
Answer= O(V)
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.
Answer= graph partition
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.
Answer= false
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.
Answer= Gomory-Hu tree
Q58. In how many ways can a Gomory-Hu tree be implemented?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
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).
Answer= 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).
Answer= O(N4)
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.
Answer= closest pair
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