Related InterviewSolutions

• Traversal of a graph is different from tree because(A) There can be a loop in graph so we must maintain a visited flag for every vertex(B) DFS of a graph uses stack, but inorrder traversal of a tree is recursive(C) BFS of a graph uses queue, but a time efficient BFS of a tree is recursive.(D) All of the above
• What are the appropriate data structures for following algorithms?1) Breadth First Search 2) Depth First Search 3) Prim's Minimum Spanning Tree 4) Kruskal' Minimum Spanning Tree (A)1) Stack2) Queue3) Priority Queue4) Union Find(B)1) Queue2) Stack3) Priority Queue4) Union Find(C)1) Stack2) Queue3) Union Find4) Priority Queue (D)1) Priority Queue2) Queue3) Stack4) Union Find
• If the DFS finishing time f[u] > f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree. (Source http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2007-sol.pdf)(A) True(B) False
• Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?(A) Depth First Search(B) Breadth First Search(C) Prim’s Minimum Spanning Tree Algorithm(D) Kruskal’ Minimum Spanning Tree Algorithm
• 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(A) MNOPQR(B) NQMPOR(C) QMNPRO(D) QMNPOR