Hashing MCQ Quiz in தமிழ் - Objective Question with Answer for Hashing - இலவச PDF ஐப் பதிவிறக்கவும்

The correct option is 

EXPLANATION:

Keys: 15, 2, 1, 5, 20, 31, 12, 21, 17, 34.

Hash function ℎ(k) = k mod 10

Insert 15:

ℎ(15) = 15 mod 10 = 5

15

   0    1     2     3     4         5        6     7     8     9

Insert 2:

ℎ(2) = 2 mod 10 = 2

2

15

   0    1      2     3     4         5        6     7     8     9

Insert 1:

ℎ(1) = 1 mod 10 = 1

1

2

15

   0    1      2     3     4         5        6     7     8     9

Insert 5:

ℎ(5) = 5 mod 10 = 5

That will result in a collision at index 5 as it already contains an element. 

So according to linear probing ℎ(k) = k mod 10 + i, where i is the collision number

Now ℎ(5) = 5 mod 10 + 1 = 5 + 1 = 6  

1

2

15

5

   0    1      2     3     4         5       6     7     8     9

Insert 20:

ℎ(20) = 20 mod 10 = 0

20

1

2

15

   0         1     2    3     4       5        6     7    8     9

Insert 31:

ℎ(31) = 31 mod 10 = 1

That will result in a collision at index 1 as it already contains an element. 

So according to linear probing ℎ(k) = k mod 10 + i, where i is the collision number

Now ℎ(31) = 31 mod 10 + 1 = 1 + 1 = 2 which also results into collision.

Now ℎ(31) = 31 mod 10 + 2 = 1 + 2 = 3  

20

1

2

31

15

5

   0        1     2     3       4       5      6     7     8    9

Insert 12:

ℎ(12) = 12 mod 10 = 2

That will result in a collision at index 2 as it already contains an element. 

So according to linear probing ℎ(k) = k mod 10 + i, where i is the collision number

Now ℎ(12) = 12 mod 10 + 1 = 2 + 1 = 3 which also results into collision.

Now ℎ(12) = 12 mod 10 + 2 = 2 + 2 = 4  

20

1

2

31

12

15

5

   0      1    2      3       4       5       6     7     8     9

Insert 21:

ℎ(21) = 21 mod 10 = 1

That will result in a collision at index 1 as it already contains an element. 

So according to linear probing ℎ(k) = k mod 10 + i, where i is the collision number

Now ℎ(21) = 21 mod 10 + 1 = 1 + 1 = 2 which also results into collision.

Now ℎ(21) = 21 mod 10 + 2 = 1 + 2 = 3 which also results into collision.

Now ℎ(21) = 21 mod 10 + 2 = 1 + 3 = 4 which also results into collision.

Now ℎ(21) = 21 mod 10 + 2 = 1 + 4 = 5 which also results into collision.

Now ℎ(21) = 21 mod 10 + 2 = 1 + 5 = 6 which also results into collision.

Now ℎ(21) = 21 mod 10 + 2 = 1 + 6 = 7  

20

1

2

31

12

15

5

21

   0     1    2     3      4       5     6       7      8     9 

Insert 17:

ℎ(17) = 17 mod 10 = 7

That will result in a collision at index 7 as it already contains an element. 

So according to linear probing ℎ(k) = k mod 10 + i, where i is the collision number

Now ℎ(17) = 17 mod 10 + 1 = 7 + 1 = 8  

 

20

1

2

31

12

15

5

21

17

   0     1    2     3      4       5     6       7      8     9 

Insert 34:

ℎ(34) = 34 mod 10 = 4

That will result in a collision at index 4 as it already contains an element. 

So according to linear probing ℎ(k) = k mod 10 + i, where i is the collision number

Now ℎ(34) = 34 mod 10 + 1 = 4 + 1 = 5 which also results into collision.

Now ℎ(34) = 34 mod 10 + 2 = 4 + 2 = 6 which also results into collision.

Now ℎ(34) = 34 mod 10 + 2 = 4 + 3 = 7 which also results into collision.

Now ℎ(34) = 34 mod 10 + 2 = 4 + 4 = 8 which also results into collision.

Now ℎ(34) = 34 mod 10 + 2 = 4 + 5 = 9  

 

20

1

2

31

12

15

5

21

17

34

   0     1     2    3       4       5    6     7        8      9

Concept:

Homogeneous data structure (HDS):

• HDS that contains only similar type of data like only integers or only float values.
• Basic example of Homogeneous data structure is Array.

Explanation

In question we required ordered finite HDS which is nothing but Array but Array is not present in the

Options so we have to choose best option among them Let’s take option wise.

Option 1:  Linked list

Linked list is HDS but not finite because linked list size is decided on Run time.

Option 2: Graph

Graph is HDS but not finite because Graph size is decided on Run time.

Option 3:  Tree

Tree is HDS but not finite because Tree size is decided on Run time.

Option 4:  Hash Table

Hash table is ordered and finite data structure (Size is decided on Compile time ).

Option 5 : Structure

Structure allows to combine data of different types together. It is finite set of values

Hence option 4 is the Best option to choose for the answer.

\((kA\text{ mod1})\) means fractional part of \(kA\). i.e. \(kA - \lfloor{kA}\rfloor\)

Here, k = 55, A = \(\frac{\sqrt7}{2}\)

h(k) = \(m\times(kA - \lfloor{kA}\rfloor)\) = 100 \(\times\) (72.75 – 72) = 100 \(\times\) 0.75 = 75

Given an open-address hash table with load factor, \(\alpha =\frac{n}{m}\) < 1, the expected number of probes in an unsuccessful search is at most \(\frac{1}{(1-\alpha)}\), assuming uniform hashing.

Where m = Number of slots in the hash table and n = Number of keys to be inserted in the hash table.

Therefore, expected number of probes in an unsuccessful search = \(\frac{1}{(1-\alpha)}\) = \(\frac{1}{(1-\frac{5}{6})}\) = 6

Answer: Option 1

Explanation:

Key	After Folding	Location	Collision
15	6	6
105	6	6	Yes
37	10	10
50	5	5
63	9	9
131	5	5	Yes
8	8	8
34	7	7
205	7	7	Yes
405	9	9	Yes
5	5	5	Yes

 

Therefore, the number of collisions is 5.

Key Points

Concept:

Division Method:

This is the easiest method to create a hash function. The hash function can be described as

 h(k) = k mod n

Here, h(k) is the hash value obtained by dividing the key-value k by the size of hash table n using the remainder. It is best that n is a prime number as that makes sure the keys are distributed with more uniformity. So here mod operation gives a reminder of k and m.

Explanation:

57 × 1 = 57

57 × 2 = 114

57 × 3 = 171

So both are close to 171,

171 + 6 = 177

171 + 26 = 197

 h(177) = 177 mod 57 = 6

 h(197) = 197 mod 57 = 26

positions are 6, 26 of 177 and 197 respectivly.

Hence the correct answer is 6, 26.

Keys: 121, 142, 169, 30, 24, 78, 53, 154

Hash Function: K mod 13

Hash Table:

Index	Values
0	169
1	78
2	53
3	154
4	121
5	30
6
7
8
9
10
11	24
12	142

Therefore 1, 2, and 3 options correct statement

The index of the key 53 is 2

Therefore option 4 is incorrect

Data: 

Total slots = total chain = 29

Average no. of elements stored in a chain = load factor = 175

Formula:

 \(load\; factor = \frac{Total\;elements}{number \;of \;slots}\)

Calculation:

\(130 = \frac{Total \;elements}{29}\)

Total number of elements = 130 × 29 = 3770.

Collision occurs when two items hash to the same slot. Ideally, a perfect hash function is the one in which no collision occurs. But this is not possible in real world applications. Hence when an attempt is made to insert a record at a slot which is full or at a primary bucket which is full, collision occurs.

No. of slots (n) = 5

For option 1:

h(4) = k mod (n - 1) = 4 mod 4 = 0

h(25) = k mod (n - 1) = 25 mod 4 = 1

h(40) = k mod (n - 1) = 40 mod 4 = 0 (2 by linear probing)

h(83) = k mod (n - 1) = 83 mod 4 = 3

h(77) = k mod (n - 1) = 77 mod 4 = 1 ( 4 by linear probing)

Two collisions and hence option 4 is more suitable  Hence option 1 is incorrect.

For option 2:

h(4) = (k - 1) mod n = 3 mod 5 = 3

but h(4) = 0. Hence option 2 is incorrect.

For option 3:

h(4) = k mod (n+1) = 4 mod 6 = 4

but h(4) = 0. Hence option 2 is incorrect.

For option 4:

h(4) = (k+1) mod n = 5 mod 5 = 0

h(25) = (k+1) mod n = 26 mod 5 = 1

h(83) = (k+1) mod n = 84 mod 5 = 4

h(77) = (k+1) mod n = 78 mod 5 = 3

h(40) = (k+1) mod n = 41 mod 5 = 1 (2)→ Here, collision occurs.

By linear probing, insert 40 at the next free slot.

h(40) = 2