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?
h(i) = i2 mod 10 | |
h(i) = i3 mod 10 | |
h(i) = (11 *i2) mod 10 | |
h(i) = (12 * i) mod 10 |
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 ___________.
80 | |
70 | |
60 | |
50 |
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
3, 0, and 1 | |
3, 3, and 3 | |
4, 0, and 1 | |
3, 0, and 2 |
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
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?
(97×97×97)/1003 | |
(99×98×97)/1003 | |
(97×96×95)/1003 | |
(97×96×95)/(3!×1003) |
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
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?
46, 42, 34, 52, 23, 33 | |
34, 42, 23, 52, 33, 46
| |
46, 34, 42, 23, 52, 33 | |
42, 46, 33, 23, 34, 52
|
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)
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?
10 | |
20 | |
30 | |
40 |
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
― 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?
 | |
 | |
 | |
 |
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.
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.
8, _, _, _, _, _, 10 | |
1, 8, 10, _, _, _, 3 | |
1, _, _, _, _, _,3 | |
1, 10, 8, _, _, _, 3 |
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).
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
i only | |
ii only | |
i and ii only | |
iii or iv |
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.
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
Worst case complexity of search operations is less? | |
Space used is less | |
Deletion is easier | |
None of the above |
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 _______.
13 |
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.
• 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
4 | |
5 | |
6 | |
3 |
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
→ 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 14is 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?
2 | |
4 | |
6 | |
7 |
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
4 | |
5 | |
6 | |
3 |
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
→ 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)?
3 | |
4 | |
5 | |
6 |
Question 15 Explanation:
Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7
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?
0 | |
1 | |
11 | |
12 |
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
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 ?
3 | |
4 | |
5 | |
6 |
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.
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.
3, 10, 1, 8, ___ , ___, ___.
| |
1, 3, 8, 10, ___, ___, ___.
| |
1, ___, 3, ___, 8, ___, 10
| |
3, 10, ___, ___, 8, ___, ___. |
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
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
is far less than one | |
equals one | |
is far greater than one | |
none of these |
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
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
6 | |
5 | |
4 | |
3 | |
None of the above |
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
3 | |
4 | |
5 | |
6 |
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 )
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
0.45 | |
0.5 | |
0.3 | |
0.37(approximately) |
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)
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
4 | |
5 | |
6 | |
3 |
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
→ 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
Is far less than one | |
Equals one | |
Is far greater than one | |
None of the above |
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 _______.
1 | |
1/n | |
1/m | |
n/m |
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:
h (k, i) = (h 1 (k) + h 2 (k) + i) mod m | |
h (k, i) = (h 1 (k) + h 2 (k) - i) mod m | |
h (k, i) = (h 1 (k) + i h 2 (k)) mod m | |
h (k, i) = (h 1 (k) - i h 2 (k)) mod m |
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.
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 :
2 | |
3 | |
9 | |
97 |
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
-- 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 ?
Hash addressing | |
Chaining | |
Both (A) and (B) | |
Indexing |
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
→ 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 :
3 | |
4 | |
5 | |
6 |
Question 29 Explanation:
Given data, insertion order is 37, 38, 72, 48, 98, 11, 56
Hash function = f(key) = key mod 7
Hash function = f(key) = key mod 7
Question 30 |
Which of the following is not collision Resolution Technique :
Hash addressing | |
Chaining | |
Indexing | |
None of these |
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
→ 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.
worst-case, average | |
worst-case, worst-case | |
average, worst-case | |
best, average |
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 ?
3 | |
4 | |
5 | |
6 |
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
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 ?
1 | |
2 | |
3 | |
4 |
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.
3, 10, 1, 8,___ ,___,___. | |
1, 3, 8, 10,___,___,___. | |
1,___,3,___, 8,___,10 | |
3,10,___,___, 8,___,___. |
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
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
46 | |
47 | |
41 | |
43 |
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
-- 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
At most (1/α) ln ((1–α)/α) | |
At most (1/α) ln (1/(1–α)) | |
At least (1/α) ln (1/(1– α)) | |
At least (1/α) ln (α/(1– α)) |
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.
→ 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
Secondary clustering | |
Primary clustering | |
Both (A) and (B) | |
None of these |
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
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 ?
100 | |
200 | |
10000 | |
There is no upper limit |
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.
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 ?
3 | |
4 | |
5 | |
6 |
Question 39 Explanation:
Given data, insertion order is 37, 38, 72, 48, 98, 11
Hash function = f(key) = key mod 7
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 ______.
46 | |
41 | |
43 | |
48 |
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
-- 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?
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?
255 | |
256 | |
257 | |
258 |
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
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.
77 | |
82 | |
88 | |
89 |
Question 42 Explanation:
h(k) = floor(100(123456* 0.618033 mod 1))
= floor(100(0.88204))
= floor(88.204)
= 88
= 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
cr=l+bfr + N | |
r= l-bfr - N | |
r=l+bfr - N | |
r=l*bfr*N |
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)
Only I | |
Only II
| |
I and II
| |
None |
Question 44 Explanation:
Linked list uses closed addressing, whereas array uses open addressing.
Hence Chains use close addressing whereas bucket uses open addressing.
Hence Chains use close addressing whereas bucket uses open addressing.
Question 45 |
In hashing, collision results when ____
An attempt is made to delete a record at full primary bucket | |
An attempt is made to insert a record at full primary bucket
| |
An attempt is made to insert a record anywhere in primary bucket
| |
An attempt is made to insert a record at empty primary bucket
|
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
Linear search | |
Binary search | |
Hash coded search | |
Radix search |
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.