Data structure MCQ Set-7

  1. 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. 2. The graph colouringalgorithm’s time can be bounded by _________
    • O(mnm)
    • O(nm)
    • O(nm. 2n)
    • O(nmn).
  3. 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. 4. Sorting is not possible by using which of the following methods?
    • Insertion
    • Selection
    • Deletion
    • Exchange
  5. 5. What is the type of the algorithm used in solving the 8 Queens problem?
    • Backtracking
    • Dynamic
    • Branch and Bound
    • D and C
  6. 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. 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. 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. 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. 10. Theasymptotic notation for defining the average time complexity is
    • Equivalence
    • Symmetric
    • Reflexive
    • Both (c) and (d) above.

Practice Now Data Structure Online Tests