# 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