Time Left - 10:00 mins

GATE 2020 : Algorithms Quiz 8 (App update required to attempt this test)

Attempt now to get your rank among 617 students!

Question 1

Let πA be a problem that belongs to the class NP. Then which one of the following is TRUE?

Question 2

A hash table has space for 100 records. Then the probability of collision before the table is 10% full is

Question 3

Load the keys 23, 13, 21, 14, 7, 8, and 15 in this order, in a hash table of size 7 using quadratic probing with the hash function h(key) = key % 7.
[Note: The required probe sequences are given by:

How many collisions can occur in the hash table?

Question 4

Consider the following keys that are hashed into the hash table in the order given using the hash function mod 11.
12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5.
Assume hash table has locations from 0 to 10. If hash table uses chaining to handle the collisions, how many locations are left without hashing any element into it?

Question 5

Consider the following keys that are hashed into the hash table in the order given using the hash function mod 11.
12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5.
Assume hash table has locations from 0 to 10. If hash table uses chaining to handle the collisions, how many locations are left without hashing any element into it?

Question 6

A hash table of length 10 is taken for insertion of the keys with hash function h(key)= key mod 10. If Collision occurs, it is resolved with quadratic probing. The following sequence of keys are inserted:
46, 36, 34, 24, 52, 57, 56
Which of the following cannot be inserted to the table due to quadratic probing?
  • 617 attempts
  • 1 upvote
  • 6 comments
Jul 4GATE & PSU CS