Graphs
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