Data structure MCQ Set-7

1. 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:
  • x[k]  (x[k] + 1) mod n
  • x[k]  (x[k]) mod (n)
  • x[k]  (x[k] + 1) mod (n+1)
  • x[k]  x[k+1] mod n
2. The graph colouringalgorithm’s time can be bounded by _________
  • O(mnm)
  • O(nm)
  • O(nm. 2n)
  • O(nmn).
3. For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for memory table, and ______time to determine the optimal load, for N objects and W as the capacity of KNAPSACK.
  • O(N+W), O(NW)
  •  O(NW),O(N+W)
  • O(N),O(NW)
  • O(NW),O(N)
4. Sorting is not possible by using which of the following methods?
  • Insertion
  • Selection
  • Deletion
  • Exchange
5. What is the type of the algorithm used in solving the 8 Queens problem?
  • Backtracking
  • Dynamic
  • Branch and Bound
  • D and C
6. The following are the statements regarding the NP problems. Chose the right option from the following options: I. All NP-complete problems are not NP-hard. II. SomeNP-hard problems are not known to be NP-complete.
  •  Both (I) and (II) are true
  • Both (I) and (II) are false
  • Only (I) is true
  • Only (II) is true
7. Let G be a graph with ‘n’ nodes and let ‘m’ be the chromatic number of the graph. Then the time taken by the backtracking algorithm to color it is
  • O(nm)
  • O(n+m)
  • O(mnm)
  • O(nmn).
8. The time complexity of the shortest path algorithm can be bounded by
  • O(n2)
  • O(n4)
  • O(n3)
  • O(n)
  • O(n log n ).
9. 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).
  •  (I) is false but (II) is true
  • (I) is true but (II) is false
  • Both (I) and (II) are true
  • (I) is true and (II) is not true always
  • Both (I) and (II) are false.
10. Theasymptotic notation for defining the average time complexity is
  • Equivalence
  • Symmetric
  • Reflexive
  • Both (c) and (d) above.