Graphs
1. Breadth first search __________
A.  Scans each incident node along with its children. B.  Scans all incident edges before moving to other node. C.  Issame as backtracking D.  Scans all the nodes in random order.
2. Which method of traversal does not use stack to hold nodes that are waiting to be processed?
A.  Dept First B.  D-search C.  Breadth first D.  Back-tracking
3. The Hamiltonian cycles problem uses the following line of code to generate a next vertex, provided x[ ] is a global array and kth vertex is under consideration:
A.  

x[k] ← (x[k] + 1) mod n

 B.  

x[k] ← (x[k]) mod (n)

 C.  

x[k] ← (x[k] + 1) mod (n+1)

 D.  

x[k] ← x[k+1] mod n
4.

The graph colouring algorithm’s time can be bounded by _________
A.  O(mnm) B.  O(nm) C.  O(nm. 2n) D.  O(nmn).
5.

Read the following statements carefully and pick the correct option:

 I. The worst time complexity of the Floyd’s algorithm is O(n3).

 II. The worst time complexity of the Warshall’s algorithm is O(n3).
A.  (I) is false but (II) is true B.  (I) is true but (II) is false C.  Both (I) and (II) are true D.  (I) is true and (II) is not true always E.  Both (I) and (II) are false.
6.

How many edges are there in a Hamiltonian cycle if the edge cost is ‘c’ and the

cost of cycle is ‘cn’
A.  c B.  cn C.  n D.  2c
7. Breadth first search
A.  Scans all incident edges before moving to other vertex B.  Scans adjacentunvisited vertex as soon as possible C.  Is same as backtracking D.  Computes a path between two vertices of graph or equivalently
8. . Breadth first search uses __________ as an auxiliary structure to hold nodes for future processing.
A.  Stack B.  Linked list C.  Graph D.  Queue
9.

Prims algorithm is based on _____________ method
A.  Divide and conquer method B.  Dynamic programming C.  Greedy method D.  Branch and bound
10. kruskal algorithm is based on ___________method
A.  Divide and conquer method B.  Greedy method C.  Dynamic programming D.  Branch and bound