GATE Problem Solving Techniques & Application Skills 5

Question 1

A salesperson visits 5 cities. The number of distinct routes visiting each city exactly once and returning to the starting city is:

Accepted Answer

12

Answer

For n cities in TSP, the number of distinct tours (fixing start) is (n-1)!/2 = 4!/2 = 24/2 = 12.

Question 2

If log₂(x) = 5, what is the value of x?

Accepted Answer

32

Answer

log₂(x) = 5 means x = 2^5 = 32.

Question 3

A hash table uses chaining for collision resolution. In the worst case, the time complexity of a search operation is:

Accepted Answer

O(n)

Answer

In the worst case, all n keys hash to the same slot, creating a single chain of length n, making search O(n).

Question 4

A problem is in class NP if:

Accepted Answer

A proposed solution can be verified in polynomial time

Answer

NP (Nondeterministic Polynomial) contains problems for which a given solution (certificate) can be verified in polynomial time.

Question 5

In a circular arrangement of 6 distinct people, how many distinct arrangements are possible?

Accepted Answer

120

Answer

Circular permutations of n objects = (n-1)! = 5! = 120.

(GATE) Graduate Aptitude Test in Engineering Practice Test