Graphs Interview Questions Part 7

62. Given the graph ,the resulting breadth-first traversal will be



a. ABCDEFGH
b. ACDGBFEH
c. ACDBEFGH
d. ACDGBEFH
Ans. b
Refer pg-565 fig.b of Data Structures Using C and C++ by Tanenbaum

63. Using adjacency matrix representation,the efficiency of breadth-first search is
a. O(n+n²) or O(n²)
b. O(e)
c. O(n)
d. O(n+e)
Where n is the number of graph nodes and e is the number of edges in the graph
Ans. a

64. Using adjacency list representation,the efficiency of breadth-first traversal is
a. O(n+n²)
b. O(e)
c. O(n)
d. O(n+e)
Ans. d
Traversing all successors of all nodes is O(e) and assuming that the graph nodes are organized as an array or a linked list ,visiting all n nodes is O(n).hence,efficiency is O(n+e).



65. The adjacency matrix representation size is equal to the number of nodes available in the graph.(T/F)
Ans:True

66.A weighted graph has a weight/cost of construction for
a.no edge
b.1 edge
c.2 edges
d.each edge
Ans:d

67.The adjacency matrix representation mat[i][j] has a value ____ when there is an edge from ith to jth node
a.0
b.1
c.2
d.can be any value
Ans:b

68. The adjacency matrix representation mat[i][j] has a value ____ when there is no edge from ith to jth node
a.0
b.1
c.2
d.can be any value
Ans:a

69. If there is a solution breadth-first search will find it regardless of the kind of graph. However, if the graph is infinite and there is no solution breadth-first search will diverge.What does this property mean?
a. BFS is complete
b. BFS is incomplete
c. BFS is optimal
d. BFS implements queue
Ans. a
Breadth-first search is complete. This means that if there is a solution breadth-first search will find it regardless of the kind of graph. However, if the graph is infinite and there is no solution breadth-first search will diverge.
70. Breadth-first search is _______ since it always returns the result with the fewest edges between the start node and the goal node.
a. optimal
b. not optimal
c. complete
d. incomplete
Ans. b
In general breadth-first search is not optimal since it always returns the result with the fewest edges between the start node and the goal node. If the graph is a weighted graph and therefore has costs associated with each step a goal next to the start does not have to be the cheapest goal available.
71. _________ is a good technique for graph when there are many possible solutions, and you only want one.
a. Breadth first search
b. Depth first search
c. Postorder
d. Inorder
Ans. b
Depth first search is good when there are many possible solutions, and you only want one (and you don't care which one). It may be less appropriate when there is only one solution, or if you want the shortest one.