Graphs Interview Questions Part 1

1.Any search algorithm that considers outgoing edges of a vertex before any neighbors of the vertex, that is, outgoing edges of the vertex's predecessor in the search, where extremes are searched first is called
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:a

2. Depth first search can be implemented with recursion.(T/F)
Ans:True

3. A search algorithm that considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex, where extremes are searched last is called
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b

4. Depth first search can be implemented with
a.stack
b.queue
c.tree
d.priority queue
Ans:a

5. Breadth first search can be implemented with
a.stack
b.queue
c.tree
d.forest
Ans:b

6. For tree search, depth first search tends to require_____ memory, as compared to breadth first search.
a.less
b.more
c.same
d.cannot say
Ans:a

For tree search at least, depth first search tends to require less memory, as you only need to record nodes on the `current' path. If there are lots of solutions, but all at a comparable `depth' in the tree, then you may hit on a solution having only explored a very small part of the tree.

7. __________ may use more memory, but will not get stuck in blind alleys, and will always find the shortest path first (or at least, the path that involves the least number of steps).
a.Depth first search
b.Breadth first seach
c.Prim’s algorithm
d.Kruskal’s algorithm
Ans:b

Breadth first search may use more memory, but will not get stuck in blind alleys, and will always find the shortest path first (or at least, the path that involves the least number of steps). It may be more appropriate when exploring very large search spaces where there is an expected solution which takes a relatively small number of steps, or when you are interested in all the solutions (perhaps up to some depth limit).

8.What is the output of pre-order traversal using DFS for the given graph


a. 1 2 3 4 8 7 5 6 b. 1 2 3 4 7 8 6 5 c.1 2 3 4 8 7 6 5 d. 1 2 3 4 8 6 7 5
Ans:c

http://www.cs.duke.edu/csed/jawaa/DFSanim.html


9. What is the output of post-order traversal using DFS for the given graph


a. 2 7 8 5 6 4 1 3 b.2 7 8 5 6 4 3 1 c. 2 7 8 5 4 6 3 1 d. 2 7 5 8 6 4 3 1
Ans:b

http://www.cs.duke.edu/csed/jawaa/DFSanim.html