Register

GO Classes DPP | PYTHON & DSA |HASHING

190 views
0 0 votes

Consider a hash table with $M=11$ slots, using Linear Probing with the hash function $h(k, i)=(k+i) \bmod 11$, where $i \in\{0,1, \ldots, 10\}$ is the probe number. The following keys are inserted in the order: $\mathbf{2 5 , 3 6 , 1 4 , 4 7}$

Calculate the Average Number of Probes required for a Successful Search of these four keys. (Note: Round your answer to two decimal places).

1 Answer

0 0 votes
0
1
2
3
4
5
6
7
8
9
10

 

The keys inserted are : 25, 36, 14, 47

25 mod 11 = 3 so it goes to 4th row containing 3 --> No. of probes = 1

36 mod 11 = 3 goes to 4th row again and then it finds 25 there and shifts to 5th row containg 4.  --> No. of probes = 2

14 mod 11 = 3 again goes to 4th row then to 5th and settles at 6th row.  --> No. of probes = 3

47 mod 11 = 3 again goes to 4th row, skips, goes to 5th row, skips, goes to 6th row, skips and settles at 7th row.  --> No. of probes = 4

The average no of probes = (1+2+3+4)/4

= 10/4 = 2.5

• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | PYT...Next → · GO Classes DPP | PYT...
← Previous in category · GO Classes DPP | PYT...Next in category → · GO Classes DPP | PYT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
243
243 views
GO Classes asked Feb 6
243 views
GO Classes DPP | PYTHON & DSA |ASYMPTOTIC ANALYSIS
Consider the following pseudocode for a function $\verb|process(n)| :$def process(n): count = 0 i = n while i 1: j = 1 while j < n: ...
0 0 votes
1 1 answer
236
236 views
GO Classes asked Feb 6
236 views
GO Classes DPP | PYTHON & DSA |SORTING
Which of the following statement(s) is/are TRUE regarding searching and sorting?IF AN INPUT ARRAY IS ALREADY SORTED, BINARY SEARCH TAKES $O(\log n)$ TIME, BUT SEARCHING F...
0 0 votes
1 1 answer
225
225 views
GO Classes asked Feb 6
225 views
GO Classes DPP | PYTHON & DSA |PYTHON
In Python, the $\verb|list|$ and $\verb|tuple|$ types handle memory allocation differently. Given the following operations:import sys L = [1, 2, 3] T = (1, 2, 3) L.append...
1 1 vote
1 1 answer
179
179 views
GO Classes asked Feb 6
179 views
GO Classes DPP | PYTHON & DSA |PYTHON
def create_multipliers(): return [lambda x: i * x for i in range(4)] multipliers = create_multipliers() result = [m(2) for m in multipliers] print(result)What is ...