Register

GATE Overflow | Algorithms | Test 1 | Question: 17

1,209 views
2 2 votes
While inserting keys 12,44,13,88,23,94,11,39,20,16 and 5 in a 11 item hash table using the hash function  $h(i) =  (2i+5) \mod 11$, total number of collisions that occur is _________ (On collision no insertion takes place)

1 Answer

4 4 votes
Hashvalues will be

12 - 29 mod 11 = 7
44 - 93 mod 11 = 5
13 - 31 mod 11 = 9
88 - 181 mod 11 = 5 - collission
23 - 51 mod 11 = 7 - collision
94 - 193 mod 11 = 6
11 - 27 mod 11 = 5 - collision
39 - 83 mod 11 = 6 - collision
20 - 45 mod 11 = 1
16 - 37 mod 11 = 4
5 - 15 mod 11 = 4 - collision

So, 5 collisions.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE Overflow | Algo...Next → · GATE Overflow | Algo...
← Previous in category · GATE Overflow | Algo...Next in category → · GATE Overflow | Algo...
Position:
Show:

Related questions

2 2 votes
3 answers 3 answers
782
782 views
Bikram asked Oct 4, 2016
782 views
GATE Overflow | Algorithms | Test 1 | Question: 29
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___
1 1 vote
2 answers 2 answers
1.6k
1.6k views
Bikram asked Oct 4, 2016
1,565 views
GATE Overflow | Algorithms | Test 1 | Question: 27
Consider a hash table of size $m = 10$ and a corresponding hash function $h(k) = k A \mod m$ for $A = 5$ where collisions are resolved by quadratic probing. The location...
2 2 votes
2 answers 2 answers
1.2k
1.2k views
Bikram asked Oct 4, 2016
1,184 views
GATE Overflow | Algorithms | Test 1 | Question: 10
Consider the following recurrence relation.$$T(n) = \begin{cases}1 & \quad if \: n = 1 \\ T(n-1) + 2^n \quad & otherwise \end{cases}$$What will be the value of $T(10)$?
7 7 votes
2 answers 2 answers
4.0k
4.0k views
Bikram asked Oct 3, 2016
4,016 views
GATE Overflow | Algorithms | Test 1 | Question: 4
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1...n]$ having $n$ values : Sequentially choose $i$ from 1 to n if A[i] = x ...