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.

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

For linear probing with open addressing, the hash function plays a crucial role in determining the sequence of slots to check when a collision occurs.

EXPLANATION:

Given hash table:

0
1	10
2	41
3	22
4	80
5	63
6	25
7
8	17
9	8
10	18

The hash table is of length m = 11m=11" id="MathJax-Element-33-Frame" role="presentation" style=" position: relative;" tabindex="0">m=11" id="MathJax-Element-84-Frame" role="presentation" style=" position: relative;" tabindex="0">m=11m=11" id="MathJax-Element-112-Frame" role="presentation" style=" position: relative;" tabindex="0">m=11�=11" id="MathJax-Element-162-Frame" role="presentation" style="position: relative;" tabindex="0">�=11�=11 �=11  , and open addressing with linear probing is used. In linear probing, when a collision occurs, you linearly search for the next available slot.

Now, let's evaluate the given hash functions:

1) \(h(k) = (k + 1) \mod m) + 1\)
2) \(h(k) = 1 + (k \mod (m - 1))\)
3) \(h(k) = 1 + (k \mod m)\)" id="MathJax-Element-34-Frame" role="presentation" style=" position: relative;" tabindex="0">" id="MathJax-Element-85-Frame" role="presentation" style=" position: relative;" tabindex="0">" id="MathJax-Element-113-Frame" role="presentation" style=" position: relative;" tabindex="0">" id="MathJax-Element-163-Frame" role="presentation" style="position: relative;" tabindex="0">
4) \(h(k) = (k \mod m)/(m - 1)\)h(k)=(kmodm)/(m−1)" id="MathJax-Element-35-Frame" role="presentation" style=" position: relative;" tabindex="0">

Let's analyze option 2 why it is correct, let's consider the elements inserted into the hash table:

1. h(k)=(kmodm)/(m−1)" role="presentation" style=" position: relative;" tabindex="0">k = 10 goes to slot 1 since 1 + (10 mod (11-1)) = 1 + 0  = 1.
2. k = 41 goes to slot 2 since 1 + (41 mod (11-1)) = 1 + 1 = 2.
3. k = 22 goes to slot 3 since 1 + (22 mod (11-1)) = 1 + 2 = 3.
4. k = 80 goes to slot 4 since 1 + (80 mod (11-1)) = 1 + 0 = 1. Slot 1 is Full so we put next blank hash.
5. And so on.

Option 2 produces a distribution that aligns with the given hash table. It effectively uses the modulo operation with m = 11 to ensure that the resulting index stays within the bounds of the hash table. This is suitable for linear probing in an open-addressing scheme, providing a sequence of indices to check when resolving collisions.