Hashing

Question 1

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

A
h(i) = i2 mod 10
B
h(i) = i3 mod 10
C
h(i) = (11 *i2) mod 10
D
h(i) = (12 * i) mod 10
       Data-Structures       Hashing       GATE 2015 [Set-2]
Question 1 Explanation: 
If we take first 10 elements, number of collisions taken by the hash function given by option (B) is less when compared to others.
Question 2

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.

A
80
B
70
C
60
D
50
       Data-Structures       Hashing       GATE 2015 [Set-3]
Question 2 Explanation: 
Load factor(α) = no. of elements/no. of slots = 2000/25 = 80
Question 3

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 the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

A
3, 0, and 1
B
3, 3, and 3
C
4, 0, and 1
D
3, 0, and 2
       Data-Structures       Hashing       GATE 2014 [Set-1]
Question 3 Explanation: 
Hash table has 9 slots.
h(k) = k mod 9
Collisions are resolved using chaining.
Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.

5%9 – 5
28%9 – 1
19%9 – 1
15%9 – 6
20%9 – 2
33%9 – 6
12%9 – 3
17%9 – 8
10%9 – 1
Maximum chain length is 3
Minimum chain length is 0
Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1
Question 4

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

A
(97×97×97)/1003
B
(99×98×97)/1003
C
(97×96×95)/1003
D
(97×96×95)/(3!×1003)
       Algorithms       Hashing       GATE 2014 [Set-3]
Question 4 Explanation: 
Given Hash table consists of 100 slots.
They are picked with equal probability of Hash function since it is uniform hashing.
So to avoid the first 3 slots to be unfilled
= 97/100*97/100*97/100 =((97*97*97))⁄1003
Question 5

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 table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

A
46, 42, 34, 52, 23, 33
B
34, 42, 23, 52, 33, 46
C
46, 34, 42, 23, 52, 33
D
42, 46, 33, 23, 34, 52
       Data-Structures       Hashing       GATE 2010
Question 5 Explanation: 
Hash Table consists of 10 slots, uses Open Addressing with hash function and linear probing.
After inserting 6 values, the table looks like

The possible order in which the keys are inserted are:
34, 42, 23, 46 are at their respective slots 4, 2, 3, 6.
52, 33 are at different positions.
― 52 has come after 42, 23, 34 because, it has the collision with 42, because of linear probing, it should have occupy the next empty slot. So 52 is after 42, 23, 34.
― 33 is after 46, because it has the clash with 23. So it got placed in next empty slot 7, which means 2, 3, 4, 5, 6 are filled.
42, 23, 34 may occur in any order but before 52 & 46 may come anywhere but before 33.

So option (C)
Question 6

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 table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

A
10
B
20
C
30
D
40
       Data-Structures       Hashing       GATE 2010
Question 6 Explanation: 
Total 6 insertions
― 33 must be inserted at last (only one possibility)
― 46 can be inserted in any of the 5 places remaining. So 5 ways.
― 52 must be inserted only after inserting 42, 23, 34. So only one choice for 52.
〈42,23,34〉 can be sequenced in 3! ways.
Hence, 5×3! = 30 ways
Question 7

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 mod 10 and linear probing. What is the resultant hash table?

A
B
C
D
       Data-Structures       Hashing       GATE 2009
Question 7 Explanation: 
Given keys: 12, 18, 13, 2, 3, 23, 5 & 15
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.

12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.
Question 8

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

A
8, _, _, _, _, _, 10
B
1, 8, 10, _, _, _, 3
C
1, _, _, _, _, _,3
D
1, 10, 8, _, _, _, 3
       Data-Structures       Hashing       GATE 2007
Question 8 Explanation: 
Consider a hash table of size 7
Starting index is zero i.e.,

⇾ Given hash function is = (3x+4) mod 3
⇾ Given sequence is = 1, 3, 8, 10
where x = 1 ⟹ (3(1)+4)mod 3 = 0
1 will occupy index 0.
where x = 3 ⟹ (3(3)+4) mod 7 = 6
3 will occupy index 6.
where x = 8 ⟹ (3(8)+4) mod 7 = 0
Index ‘0’ is already occupied then put value(8) at next space (1).
where x = 10 ⟹ (3(10)+4) mod 7 = 6
Index ‘6’ is already occupied then put value(10) at next space (2).
The resultant sequence is (1, 8, 10, __ , __ , __ , 3).
Question 9

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?

    i) 9679, 1989, 4199 hash to the same value
    ii) 1471, 6171 hash to the same value
    iii) All elements hash to the same value
    iv) Each element hashes to a different value
A
i only
B
ii only
C
i and ii only
D
iii or iv
       Data-Structures       Hashing       GATE 2004
Question 9 Explanation: 
Given Input = (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199)
Hash function = x mod 10
Hash values = (2, 4, 1, 9, 9, 1, 3, 9)
9679, 1989, 4199 have same hash values
&
1471, 6171 have same hash values.
Question 10

An advantage of chained hash table (external hashing) over the open addressing scheme is

A
Worst case complexity of search operations is less?
B
Space used is less
C
Deletion is easier
D
None of the above
       Data-Structures       Hashing       GATE 1996
Question 10 Explanation: 
In chained hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing can be postponed for longer time.
Question 11

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 that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is _______.

A
13
       Data-Structures       Hashing       GATE 2020
Question 11 Explanation: 
• Probe sequence is the list of locations which a method for open addressing produces as alternatives in case of a collision.
• K=90
• h1(k) = k mod 23 = 90 mod 23 = 21
• In case of collision, we need to use secondary hash function.
• h2(k) = 1 + (k mod19) = 1 + 90mod19 = 1+14 = 15
• Now (21+15) mod 23 = 36 mod 23 = 13
• So the address is 13.
Question 12

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

A
4
B
5
C
6
D
3
       Data-Structures       Hashing       GATE 1989
Question 12 Explanation: 
In this, maximum size of cluster = 4 (S6, S3, S7, S1)
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisons = 4 + 1 = 5
Question 13

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 with keys

 43 36 92 87 11 4 71 13 14
is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?
A
2
B
4
C
6
D
7
       Data-Structures       Hashing       GATE 2008-IT
Question 13 Explanation: 

Hence, correct option is (D).
Question 14
A hash table with 10 buckets with one slot per bucket is depicted here. The symbols, S1 to s7 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is
A
4
B
5
C
6
D
3
       Data-Structures       Hashing       ISRO-2018
Question 14 Explanation: 
In this, maximum size of cluster=4(S6, S3, S7, S1)
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum number of comparisons = 4 + 1 = 5
Question 15
A Hash Function f is defined as f(key) = key mod 7. With linear probing, while inserting the keys 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0, in which location the key 11 will be stored (Count table index 0 as 0th location)?
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       ISRO-2016
Question 15 Explanation: 
Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7
Question 16
Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order?
A
0
B
1
C
11
D
12
       Data-Structures       Hashing       ISRO CS 2014
Question 16 Explanation: 
The hash table size is 13 so the indexes are 0 to 12.So that the elements will store in to any of the 13 locations
661 mod 13 = 11
182 mod 13 = 0
24 mod 13 = 11, already filled, so after linear probing it will get index 12
103 mod 13 = 12, already filled, so after linear probing it will get index 1
Question 17

A hash function h defined h(key) = key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?

A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC-NET CS 2018 JUNE Paper-2
Question 17 Explanation: 
h(key) = key mod 7 is the given hash function and it is mentioned that linear probing is used.
h(44) = 44 mod 7 ⇒ 2
h(45) = 45 mod 7 ⇒ 3
h(79) = 79 mod 7 ⇒ 2 (collision occurred)
h(79) = (79+1) mod 7 ⇒ 3 (collision occurred)
h(79) = (79+2) mod 7 ⇒ 4
h(55) = 55 mod 7 ⇒ 6
h(91) = 91 mod 7 ⇒ 0
h(18) = 18 mod 7 ⇒ 4 (collision occurred)
h(79) = (18+1) mod 7 ⇒ 5
h(63) = 63 mod 7 ⇒ 0 (collision occurred)
h(63) = (63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations.
Question 18

Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ?

Here “__” denotes an empty location in the table.

 
A
3, 10, 1, 8, ___ , ___, ___.
B
1, 3, 8, 10, ___, ___, ___.
C
1, ___, 3, ___, 8, ___, 10
D
3, 10, ___, ___, 8, ___, ___.
       Data-Structures       Hashing       UGC-NET CS 2018 JUNE Paper-2
Question 18 Explanation: 
h(1) = ((7*1)+3) mod 4 = 2
h(3) = ((7*3)+3) mod 4 = 0
h(8) = ((7*8)+3) mod 4 = 3
h(10) = ((7*10)+3) mod 4 = 1
Question 19
The average search time of hashing, with linear probing will be less if the load factor
A
is far less than one
B
equals one
C
is far greater than one
D
none of these
       Data-Structures       Hashing       Nielit Scientist-C 2016 march
Question 19 Explanation: 
A critical statistic for a hash table is the load factor, defined as
Load factor= n / k
where
● n is the number of entries occupied in the hash table.
● k is the number of buckets.
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)
The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1
Question 20
A hash table with 10 buckets with one slot per bucket is depicted. The symbols, S1 to S7 are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is
A
6
B
5
C
4
D
3
E
None of the above
       Data-Structures       Hashing       Nielit Scientist-C 2016 march
Question 20 Explanation: 
Question and options are wrong. So, excluded for evaluation.
Question 21
A hash function f defined as f(key)=key mod 7, with linear probing, insert the keys 37,38,72,48,98,11,56 into a table indexed from 11 will be stored in the location
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       Nielit Scientist-B CS 2016 march
Question 21 Explanation: 
The hash starts from 0th index.
37%7=2
38%7=3
72%7=2. Here, collision happened because already index 2 is already filled by 37.
According to linear probing, increment index value by 1.
2+1=3 but index 3 also filled with 38 element. So, again increment by 1.
72%7=2( getting index position in hash table ​ 4 ​ )
48%7=6
98%7=0
11%7=4. Here, collision happened because already index 4 is already filled by 72.
According to linear probing, increment index value by 1.
11%7=4 (getting index position in hash table ​ 5 ​ )
56%7=0Here, collision happened because already index 0 is already filled by 98.
According to linear probing, increment index value by 1.
56%7=0 (getting index position in hash table ​ 1 ​ )
Question 22
A hash table has space for 100 records. then the probability of collision before the table is 10% full, is
A
0.45
B
0.5
C
0.3
D
0.37(approximately)
       Data-Structures       Hashing       Nielit Scientist-B CS 2016 march
Question 22 Explanation: 
Here, we can get the answer using 1-Probability of no collision for first 10 entries.
So, 1- (100*99*98*97*96*95*94*93*92*91)/100​ 10​ ⇒ 0.37(approximately)
Question 23
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing.The maximum number of comparisons needed in searching an item that is not present is

A
4
B
5
C
6
D
3
       Data-Structures       Hashing       ISRO CS 2015
Question 23 Explanation: 
In this, maximum size of cluster = 4 (S6, S3, S7, S1)
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisons = 4+1
= 5
Question 24
The average search time for hashing with linear probing will be less if the load factor
A
Is far less than one
B
Equals one
C
Is far greater than one
D
None of the above
       Data-Structures       Hashing       Nielit Scientific Assistance IT 15-10-2017
Question 24 Explanation: 
Load factor is the ratio of number of records that are currently present and the total number of records that can be present. If the load factor is less, free space will be more. This means probability of collision is less. So, the search time will be less.
Question 25
If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key x is less than _______.
A
1
B
1/n
C
1/m
D
n/m
       Data-Structures       Hashing       UGC NET CS 2017 Jan -paper-2
Question 25 Explanation: 
If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key x is less than 1. It is direct theorem from universal hashing.
Question 26
The hash function used in double hashing is of the form:
A
h (k, i) = (h​ 1​ (k) + h​ 2​ (k) + i) mod m
B
h (k, i) = (h​ 1​ (k) + h​ 2​ (k) - i) mod m
C
h (k, i) = (h​ 1​ (k) + i h​ 2​ (k)) mod m
D
h (k, i) = (h​ 1​ (k) - i h​ 2​ (k)) mod m
       Data-Structures       Hashing       UGC NET CS 2015 Dec- paper-2
Question 26 Explanation: 
Double Hashing with second hash function is​ ​ h(k,i) = (h​ 1​ (k) + i·h​ 2​ (k)) mod m 0≤ i ≤m-1
h​ 1​ → hash function
h​ 2​ → Step function
First try h(k,0) = h​ 1​ (k), if it is occupied, try h(k,1) etc..,
Advantage: less clusters, uses Θ(m*m) permutations of index addressing sequences.
Question 27
Suppose we are implementing quadratic probing with a Hash function, Hash(y)=X mod 100. If an element with key 4594 is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is :
A
2
B
3
C
9
D
97
       Data-Structures       Hashing       UGC NET CS 2004 Dec-Paper-2
Question 27 Explanation: 
Given quadratic probing with a Hash function,
-- Hash(y)=X mod 100
-- Key=4594
-- First 3 locations are already occupied.
-- Next cell=?
Step-1: Quadratic Probing function is​ ​ h(k,i) = (h'(k) +c​ 1​ i+c​ 2​ i​ 2​ )mod m 0≤ i ≤ m-1
where c1 and c2 constants ≠0
Step-2: First pass: 4594 % 100
= 94
Sep-3: Second pass: (4594 + 1​ 2​ ) % 100
= (94 + 1) % 100
= 95
Step-3: Third pass: (4594 + 2​ 2​ ) % 100
= (94 + 4) %100
= 98
Step-4: Fourth pass: (4594 + 1​ 2​ ) % 100
= (94 + 9) %100
= 103 % 100
= 3
Question 28
Which of the following is not collision resolution technique ?
A
Hash addressing
B
Chaining
C
Both (A) and (B)
D
Indexing
       Data-Structures       Hashing       UGC NET CS 2004 Dec-Paper-2
Question 28 Explanation: 
→ Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys.
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 29
A hash function ​ f ​ defined as ​ f ( ​ key)5 key mod 7, with linear probing it is used to insert the key 37,38,72,48,98,11,56 into a table index from 0 to 6. What will be the locations of 11 :
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC NET CS 2005 Dec-Paper-2
Question 29 Explanation: 
Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7
Question 30
Which of the following is not collision Resolution Technique :
A
Hash addressing
B
Chaining
C
Indexing
D
None of these
       Data-Structures       Hashing       UGC NET CS 2005 Dec-Paper-2
Question 30 Explanation: 
→ Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys.
→ Two keys mapping to the same location in the hash table is called “Collision”.
Collision Resolving techniques
1. Separate chaining
2. Open addressing
i. Linear Probing
ii. Quadratic Probing
iii. Double hashing
Question 31
Searching for an element in the hash table requires O(1) time for the _____ time, whereas for direct addressing it holds for the ________ time.
A
worst-case, average
B
worst-case, worst-case
C
average, worst-case
D
best, average
       Data-Structures       Hashing       UGC NET CS 2014 June-paper-2
Question 31 Explanation: 
→ Hash tables are a simple and effective method to implement dictionaries. Average time to search for an element is O(1), while worst-case time is O(n)
Question 32
A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18 ?
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC NET CS 2018 JUNE Paper-2
Question 32 Explanation: 
h(key)=key mod 7 is the given hash function and it is mentioned that linear probing is used.
h(44)=44 mod 7 ⇒ 2
h(45)=45 mod 7 ⇒ 3
h(79)=79 mod 7 ⇒ 2 (collision occurred)
h(79)=(79+1) mod 7 ⇒ 3 (collision occurred)
h(79)=(79+2) mod 7 ⇒ 4
h(55)=55 mod 7 ⇒ 6
h(91)=91 mod 7 ⇒ 0
h(18)=18 mod 7 ⇒ 4 (collision occurred)
h(79)=(18+1) mod 7 ⇒ 5
h(63)=63 mod 7 ⇒ 0 (collision occurred)
h(63)=(63+1) mod 7 ⇒ 1
Now the array contain keys 44, 45, 79, 55, 91, 18, 63 at locations
Question 33
A hash function f defined as f(key) = key mod 13, with linear probing is used to insert keys 55, 58, 68, 91, 27, 145. What will be the location of 79 ?
A
1
B
2
C
3
D
4
       Data-Structures       Hashing       UGC NET CS 2012 Dec-Paper-2
Question 33 Explanation: 

Question 34
Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ? Here “__ ” denotes an empty location in the table.
A
3, 10, 1, 8,___ ,___,___.
B
1, 3, 8, 10,___,___,___.
C
1,___,3,___, 8,___,10
D
3,10,___,___, 8,___,___.
       Data-Structures       Hashing       UGC NET CS 2018 JUNE Paper-2
Question 34 Explanation: 
h(1)= ((7*1)+3) mod 4 = 2
h(3)= ((7*3)+3) mod 4 = 0
h(8)= ((7*8)+3) mod 4 = 3
h(10)= ((7*10)+3) mod 4 = 1
Question 35
Consider a hash table of size m = 10000 and the hash function h(k) = ⌊m(kA mod 1)'⌋ for      A=(√5 – 1)/2 . The location to the key k=123456 is
A
46
B
47
C
41
D
43
       Data-Structures       Hashing       UGC NET CS 2011 June-Paper-2
Question 35 Explanation: 
Given data,
-- size m=10000
-- hash function h(k) = ⌊m(kA mod 1)'⌋
-- A=(√5 – 1)/2
-- key k=123456 location =?
Step-1: Find out h(123456) = ⌊(10000 * (123456 * (√5 − 1) / 2) mod 1)⌋
= ⌊(10000 * (76300.004115 mod 1)⌋
= ⌊(10000 * (.004115))⌋
= ⌊41.15⌋
= 41
Question 36
Given an open address hash table with load factor α < 1, the expected number of probes in a successful search is
A
At most (1/α) ln ((1–α)/α)
B
At most (1/α) ln (1/(1–α))
C
At least (1/α) ln (1/(1– α))
D
At least (1/α) ln (α/(1– α))
       Data-Structures       Hashing       UGC NET CS 2013 June-paper-2
Question 36 Explanation: 
Analysis of Open Addressing:
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
→ Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.
Question 37
Linear probing suffers from a problem known as
A
Secondary clustering
B
Primary clustering
C
Both (A) and (B)
D
None of these
       Data-Structures       Hashing       UGC NET CS 2010 Dec-Paper-2
Question 37 Explanation: 
→ Primary clustering means that if there is a cluster and the initial position of a new record would fall anywhere in the cluster the cluster size increases.
Example: Linear probing
→ Secondary clustering is less severe, two records do only have the same collision chain if their initial position is the same.
Example: Quadratic probing
Question 38
A chained hash table has an array size of 100. What is the maximum number of entries that can be placed in the table ?
A
100
B
200
C
10000
D
There is no upper limit
       Data-Structures       Hashing       UGC NET CS 2010 June-Paper-2
Question 38 Explanation: 
Here, two things we have to remember
1. They given chained hash. It is like linked list.
2. Maximum number of entries that can be placed in the table.
In chained hash, we adding new element when collisions are happened.
Question 39
A hash function f defined as f(key) = key mod 7, with linear probing used to resolve collisions. Insert the keys 37, 38, 72, 48, 98 and 11 into the table indexed from 0 to 6. What will be the location of 11 ?
A
3
B
4
C
5
D
6
       Data-Structures       Hashing       UGC NET CS 2009 Dec-Paper-2
Question 39 Explanation: 
Given data, insertion order is 37, 38, 72, 48, 98, 11
Hash function = f(key) = key mod 7

Question 40
Consider a hash table of size m = 10000, and the hash function h(K) = floor (m(KA mod1)) for A = ( √(5) – 1)/2. The key 123456 is mapped to location ______.
A
46
B
41
C
43
D
48
       Data-Structures       Hashing       UGC NET CS 2016 Aug- paper-3
Question 40 Explanation: 
Given data,
-- Hash table size(m)=10000
-- Hash function(h(K))= floor (m(KA mod1))
-- A=(√(5)-1)/2
-- key(K)=123456
-- location=?
Step-1: Hash function(h(K))= floor (m(KA mod1))
h(123456) = floor(10000 * (123456 * (√5 − 1) / 2) mod 1)
= floor(10000 * (76300.004115 mod 1)
= floor(10000 * (.004115))
= floor(41.15)
= 41
Question 41
Consider double hashing of the form
h(k,i)=(h​ 1​ (k)+ih​ 2​ (k)) mod m
Where h​ 1​ (k)=k mod m
h​ 2​ (k)=1+(k mod n)
Where n=m-1and m=701
for k=123456, what is the difference between first and second probes in terms of slots?
A
255
B
256
C
257
D
258
       Data-Structures       Hashing       UGC NET June-2019 CS Paper-2
Question 41 Explanation: 
Given h(k,i)=h1(k)+ih2(k)
where h1(k)=k mod m
h2(k)=1+k mod n
where n=m-1 and m=701. For k=123456
h1(k)=123456 mod 701
h1(k)=80
h2(k)=1+(123456 mod 700)
h2(k)=1+256=257
1st probe: i=1
h(k,i)=h1(k)+ih2(k)
h(k,1)=h1(k)+ih2(k)
h(k,1)=80+257=337
h(k,1)=337
2nd probe: i=2
h(k,2)=80+2257
h(k,2)=80+514
h(k,2)=594
∴ Difference h(k,2)-h(k,1)
594-337
257
Question 42
Consider a hash table of size m = 100 and the hash function h(k) = floor(m(kA mod 1)) for A = frac{(sqrt5 - 1) 2 = 0.618033 Compute the location to which the key k = 123456 is placed in hash table.
A
77
B
82
C
88
D
89
       Data-Structures       Hashing       UGC NET CS 2015 June Paper-3
Question 42 Explanation: 
h(k) = floor(100(123456* 0.618033 mod 1))
= floor(100(0.88204))
= floor(88.204)
= 88
Question 43
In linear hashing, if blocking factor bfr, loading factor l and file buckets N are known, the number of records will be
A
cr=l+bfr + N
B
r= l-bfr - N
C
r=l+bfr - N
D
r=l*bfr*N
       Data-Structures       Hashing       ISRO CS 2020
Question 43 Explanation: 
In linear hashing, if blocking factor bfr, loading factor l and file buckets N are known, the number of records will be r=l*bfr*N.
Question 44

In hashing, collision resolution is carried out by close addressing. Which of the following is close addressing technique-
I. Bucket (for contiguous storage)
II. Chains (for linked storage)

A
Only I
B
Only II
C
I and II
D
None
       Data-Structures       Hashing       CIL 2020
Question 44 Explanation: 
Linked list uses closed addressing, whereas array uses open addressing.
Hence Chains use close addressing whereas bucket uses open addressing.
Question 45

In hashing, collision results when ____

A
An attempt is made to delete a record at full primary bucket
B
An attempt is made to insert a record at full primary bucket
C
An attempt is made to insert a record anywhere in primary bucket
D
An attempt is made to insert a record at empty primary bucket
       Data-Structures       Hashing       CIL 2020
Question 45 Explanation: 
When the primary bucket is full then if a record is allowed to insert anywhere in the primary bucket then there will definitely be collision because no empty place is available in that bucket.
Question 46
A search procedure which associates an address with a key value and provides a mechanism for dealing with two or more values assigned to the same address is called
A
Linear search
B
Binary search
C
Hash coded search
D
Radix search
       Data-Structures       Hashing       TNPSC-2012-Polytechnic-CS
Question 46 Explanation: 
A search procedure which associates an address with a key value and provides a mechanism for dealing with two or more values assigned to the same address is called Hash coded search.
There are 46 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com
error: Content is protected !!