Hashing MCQ Quiz in मल्याळम - Objective Question with Answer for Hashing - സൗജന്യ PDF ഡൗൺലോഡ് ചെയ്യുക
Last updated on Mar 11, 2025
Latest Hashing MCQ Objective Questions
Top Hashing MCQ Objective Questions
Hashing Question 1:
A _______ is an ordered collection of finite, homogeneous data elements.
Answer (Detailed Solution Below)
Hashing Question 1 Detailed Solution
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 ).
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.
Hashing Question 2:
Consider a hash table of size m = 100 and a corresponding hash function h(k) = \(\lfloor{m(kA\text{ mod1})}\rfloor\) for A = \(\frac{\sqrt7}{2}\). Compute the location to which the key 55 is mapped.
Answer (Detailed Solution Below) 75
Hashing Question 2 Detailed Solution
\((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
Hashing Question 3:
Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search when the load factor is \(\frac{5}{6}\).
Answer (Detailed Solution Below) 6
Hashing Question 3 Detailed Solution
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})}\) = 6Hashing Question 4:
Consider the following elements:
15, 105, 37, 50, 63, 131, 8, 34, 205, 405, 5 and Hash table size = 13
How many collisions occur when these key’s are first folded by adding their digits together and then reducing to mod hash table size.
Answer (Detailed Solution Below)
Hashing Question 4 Detailed Solution
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.
Hashing Question 5:
Consider an empty Hash table of size 13 (0 -12). The keys inserted are 121, 142, 169, 30, 24, 78, 53, and 154. Hash Function is H(K) = K mod 13.Open addressing is the method used for collision resolution in a hash table with linear probing. Which is/are the CORRECT statement about index and their values?
Answer (Detailed Solution Below)
Hashing Question 5 Detailed Solution
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
Hashing Question 6:
In Hash table H, collision is resolved by using chaining. There are 29 slots in H. The average number of elements stored in a chain is 130. What is the total number of elements stored in H?
Answer (Detailed Solution Below) 3770
Hashing Question 6 Detailed Solution
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.
Hashing Question 7:
In hashing, collision results when _______.
Answer (Detailed Solution Below)
Hashing Question 7 Detailed Solution
Hashing Question 8:
A hash table of length (n) 5 uses hashing to insert a value (k) and linear probing to resolve the collision. After inserting 4, 25, 83, 77, 40 into an empty hash table, the table is as shown below.
Index |
Key |
0 |
4 |
1 |
25 |
2 |
40 |
3 |
77 |
4 |
83 |
Which one of the following hash function will distribute elements as shown in the above hash table?
Answer (Detailed Solution Below)
Hashing Question 8 Detailed Solution
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) = 2Hashing Question 9:
A hash table of length(m) 11 uses open addressing and linear probing. After inserting 9 values into an empty hash table, the table is as shown below.
0 |
|
1 |
10 |
2 |
41 |
3 |
22 |
4 |
80 |
5 |
63 |
6 |
25 |
7 |
|
8 |
17 |
9 |
8 |
10 |
18 |
Which one of the following hash function will distribute elements as shown in above hash table.
Answer (Detailed Solution Below)
Hashing Question 9 Detailed Solution
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 = 11
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)\)
Let's analyze option 2 why it is correct, let's consider the elements inserted into the hash table:
h ( k ) = ( k mod m ) / ( m − 1 ) " role="presentation" style=" position: relative;" tabindex="0">k = 10 goes to slot 1 since 1 + (10 mod (11-1)) = 1 + 0 = 1.- k = 41 goes to slot 2 since 1 + (41 mod (11-1)) = 1 + 1 = 2.
- k = 22 goes to slot 3 since 1 + (22 mod (11-1)) = 1 + 2 = 3.
- 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.
- 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.
Hashing Question 10:
Consider an open-address hash table with uniform hashing. What is the time complexity for successful search with n elements?
Answer (Detailed Solution Below)
Hashing Question 10 Detailed Solution
At worst, to search for an element, one has to search for the entire n elements if open-address hash table is used as collision resolution technique
T(n) = O (n)
Important Point:
O(n) is present in option and hence go for the worst case