This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Hamiltonian Path Problem”.
1. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
a) branch and bound
b) iterative improvement
c) divide and conquer
d) greedy algorithm
View Answer
Explanation: The Hamiltonian path problem can be solved efficiently using branch and bound approach. It can also be solved using a backtracking approach.
2. The problem of finding a path in a graph that visits every vertex exactly once is called?
a) Hamiltonian path problem
b) Hamiltonian cycle problem
c) Subset sum problem
d) Turnpike reconstruction problem
View Answer
Explanation: Hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas Hamiltonian cycle problem is finding a cycle in a graph.
3. Hamiltonian path problem is _________
a) NP problem
b) N class problem
c) P class problem
d) NP complete problem
View Answer
Explanation: Hamiltonian path problem is found to be NP complete. Hamiltonian cycle problem is also an NP- complete problem.
4. There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
a) true
b) false
View Answer
Explanation: There is a relationship between Hamiltonian path problem and Hamiltonian circuit problem. The Hamiltonian path in graph G is equal to Hamiltonian cycle in graph H under certain conditions.
5. Which of the following problems is similar to that of a Hamiltonian path problem?
a) knapsack problem
b) closest pair problem
c) travelling salesman problem
d) assignment problem
View Answer
Explanation: Hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once.
6. Who formulated the first ever algorithm for solving the Hamiltonian path problem?
a) Martello
b) Monte Carlo
c) Leonard
d) Bellman
View Answer
Explanation: The first ever problem to solve the Hamiltonian path was the enumerative algorithm formulated by Martello.
7. In what time can the Hamiltonian path problem can be solved using dynamic programming?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(N2 2N)
View Answer
Explanation: Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N2 2N).
8. In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.
a) true
b) false
View Answer
Explanation: According to a handshaking lemma, in graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.
9. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
a) Karp
b) Leonard Adleman
c) Andreas Bjorklund
d) Martello
View Answer
Explanation: Andreas Bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of Hamiltonian cycles.
10. For a graph of degree three, in what time can a Hamiltonian path be found?
a) O(0.251n)
b) O(0.401n)
c) O(0.167n)
d) O(0.151n)
View Answer
Explanation: For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251n).
11. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
a) O(N!)
b) O(N! * N)
c) O(log N)
d) O(N)
View Answer
Explanation: For a graph having N vertices traverse the permutations in N! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes N iterations (i.e.) O(N! * N).
12. How many Hamiltonian paths does the following graph have?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The above graph has only one Hamiltonian path that is from a-b-c-d-e.
13. How many Hamiltonian paths does the following graph have?
a) 1
b) 2
c) 0
d) 3
View Answer
Explanation: The above graph has no Hamiltonian paths. That is, we cannot traverse the graph with meeting vertices exactly once.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Programming Books
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
