Time Left - 15:00 mins

GATE 2022: Algorithms QUIZ - 8

Attempt now to get your rank among 374 students!

Question 1

Consider a hash table of size m = 7 and a corresponding hash function h(k) = k mod 7, where a value of k is computed using a folding method. In folding method key is divided into some segment of length 3. Compute the location to which the key 749287198 is mapped. An Index of the hash table starts from 0 .

Question 2

Given the set of values {2341, 4234, 2839, 430, 22, 397, 3920} in a hash table of size 7, and hash function

mod 7. Find the total number of first time collisions when linear probing is used.

Question 3

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?

Question 4

Consider a hash table with ‘m’ slots that uses chaining for collision resolution. The table is initially empty. What is the probability that after 4 keys are inserted that exactly a chain of size 4 is created? (Assume simple uniform hashing is used)

Question 5

Consider the hashing table with ‘m’ slots and ‘n’ keys. If the expected number of probes in unsuccessful search is 3 then value of load factor is ____.(upto 3 decimal places)

Question 6

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?

374 attempts
1 upvote
1 comment

Tags :

GATE & PSU CS Algorithms

Aug 12GATE & PSU CS