OR 507

The Breadth First Search traversal of a graph will result into?. Linked List. Tree. Tree with back edges. Arrays.

A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?. a) Depth First Search. b) Breadth First Search. c) Dijkstra Algorithm. d) None of the above.

3. Which of the following is not an application of Breadth First Search?. a) Finding shortest path between two nodes. c) Finding bipartiteness of a graph. b) GPS navigation system. d) Path Finding.

4. In Breadth First Search, how many times a node is visited?. a) Once. b) Twice. c) Equivalent to number of indegree of the node. d) None of the above.

5. Cycle is a path with 2 or more nodes, except that the first node is the last node and no node is repeated with directions are important. a) True. b) False.

6. In a directed path, nodes are no repeated and directions are important. a) True. b) False.

7. Walks are paths that can repeat nodes and arcs. a) True. b) False.

8. A closed walk is a cycle except that it can repeat nodes and arcs. a) True. b) False.

9. A walk is closed if its first and last nodes are not the same. a) True. b) False.

10. The degree of a node in an undirected graph is the number of incident arcs. a) True. b) False.

11. The necessity conditions for Euler’s theorem are any eulerian cycle “visits” each node an even number of times and the network is connected. a) True. b) False.

12. Which node is the predecessor for node 5?. a) Node 1. b) Node 2. c) Node 3. d) Node 4.

13. What is the adjacency list for node 2?. a) Nodes 3, 5. b) Nodes 3, 5, 4. c) Nodes 2, 4. e) None of the above.

14. Is the predecessor for node 4 is node 2?. a) True. b) False.

15. Is the outdegree for node 5 is zero?. a) True. b) False.

16. What is the successor for node 2?. a) Nodes 3, 5. b) Nodes 3, 5, 4. c) Nodes 2, 4. d) None of the above.

17. Adjacency matrix is efficient storage if matrix is very “dense”, but adjacency lists efficient storage if matrix is “sparse.”. a) True. b) False.

18. A tree is a connected acyclic graph. a) True. b) False.

19. If a tree has n nodes, it has n-1 arcs?. a) True. b) False.

21. Which of the following is an application of Depth First Search?. a) For generating topological sort of a graph. b) For generating Strongly Connected Components of a directed graph. c) Detecting cycles in the graph. d) All the above.

22. In Depth First Search, how many times a node is visited?. a) Once. b) Twice. c) Equivalent to number of indegree of the node. d) None of the above.

29. Topological sort can be applied to which of the following graphs. a) Undirected Cyclic Graphs. b) Directed Cyclic Graphs. c) Undirected Acyclic Graphs. d) Directed Acyclic Graphs.

30. In most of the cases, topological sort starts from a node which has ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐. a) Maximum Degree. b) Zero Degree. c) Minimum Degree. d) Any degree.

31. Every Directed Acyclic Graph has at least one sink vertex. a) True. b) False.

32. If there are more than 1 topological sorting of a directed acyclic graph is possible, which of the following is true. a) Many Hamiltonian paths are possible. b) No Hamiltonian path is possible. c) Exactly 1 Hamiltonian path is possible. d) None of the above.

33. Which of the following is an application of topological sorting?. a) Finding prerequisite of a task. b) Finding Deadlock in an Operating System. c) Finding Cycle in a graph. d) All the above.