GATE CSE
Data Structures
Hashing
Previous Years Questions

## Marks 1

Suppose we are given n keys, m has table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the od...
Consider a double hashing scheme in which the primary hash function is h1(k)=k mod 23, and the secondary hash function is h2(k)=1+(k mod 19). Assume t...
Given a hash table $$𝑇$$ with $$25$$ slots that stores $$2000$$ elements, the load factor $$\alpha$$ for $$𝑇$$ is ____________ .
Consider the following two statements: i. A hash function (these are often used for computing digital signatures) is an injective function. ii. encr...
A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If...
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?...
An advantage of chained hash table (external hashing) over the open addressing scheme is

## Marks 2

Consider a dynamic hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is use...
Which one of the following hash functions on integers will distribute keys most uniformly over $$10$$ buckets numbered $$0$$ to $$9$$ for $$𝑖$$ rangi...
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first ...
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in...
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table...
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table...
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k...
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records w...
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of ...
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new ...
EXAM MAP
Joint Entrance Examination