CS Free MCQ Bank

[ Option D ]

Hashing is a technique used to store data in a table using a hash function, which converts a key into an index. Sometimes, two keys may map to the same index, which is called a Collision. 
To handle collisions, different collision resolution techniques are used:

• Linear Probing: Check next slots sequentially until an empty slot is found.
• Quadratic Probing: Use quadratic jumps to find the next position.
• Double Hashing: Use a second hash function to decide the step size.
• Chaining: Store multiple elements at the same index using a linked list.

In this question, linear probing is used, meaning if a slot is occupied, we move step-by-step to the next free slot.
The given hash function is, h(x)=(ord(x)-ord(′B′)+1) mod 10. Since ord('B')=66, the formula becomes:

• h(x) = (ord(x)-66+1) mod 10 = (ord(x)-65) mod 10

Now Apply Linear Probing:

• K : 0
• R : 7
• P : 5
• C : 2
• S : 8
• T : 9
• J : 9 (Collision at 9) = 0 (Full) : 1 (Free)
• M : 2 (Collision at 2) = 3 (Free)
• N : 3 (Collision at 3) = 4 (Free)
• Y : 4 (Collision at 4) = 5 (Full) : 6 (Free)

Final Hash Table:

Therefore, Final Sequence : K J C M N P Y R S T

[ Option C ]

Different data structures have different time complexities for searching. A Hash Table provides O(1) (Constant Time) search in the best and average case because it uses a hash function to directly compute the index where the data is stored, avoiding traversal.

[ Option B ]

In hashing, the Load Factor (α) represents how full a hash table is. It is defined as the ratio of the number of elements stored in the table to the total number of slots available. A higher load factor means more elements are stored per slot.
Load Factor = Number of Elements / Number of Slots
Here, number of elements = 2400 and number of slots = 25. So, Load Factor = 2400/25 = 96

[ Option B ]

A hash table is typically implemented using an array. The hash function converts a key into an array index, and the value is stored at that index in the array.
Arrays are used because they provide fast random access, which allows insertion, deletion, and searching operations in O(1) average time.

[ Option C ]

A Hash Table provides very fast searching, insertion, and deletion, generally in O(1) time on average, because it uses a hash function to compute the index of the element.
Hash Table stores data in an associative manner using a hash function to compute an index where the value is stored.

[ Option C ]

In a chained hash table (external hashing), each slot in the hash table holds a linked list of all elements that hash to the same index. This makes deletion easier because elements can be removed from the linked list without affecting other entries in the main hash table array.
Unlike in open addressing, stores all elements directly in the array itself, which makes deletion more complex.
Another advantage of external hashing is it handles collisions efficiently, multiple elements can exist at the same slot without affecting other slots.

[ Option A ]

A Hash Function is used to convert input data (message) into a fixed-size value called a hash code. It is widely used in data structures and security applications.
Statement-1 is true because a hash function can produce the same hash value for different inputs, which is called a collision. Since the output size is fixed but input size can vary, collisions are possible.
Statement-2 is also true because a hash function takes input of arbitrary length and produces a fixed-length output i.e., 128-bit, 256-bit hash.

[ Option A ]

The given hash function is h(i)=i² mod8. To find the value of h(8), we substitute i=8 into the function. 
First, calculate 8²=64. Then apply the modulus operation: 64 mod 8, which means finding the remainder when 64 is divided by 8. 
Since 64 is exactly divisible by 8, the remainder is 0. Therefore, the value of the hash function is 0.

[ Option A ]

In a hash table with 100 slots, when 10 records are inserted (i.e., 10% full), the probability of no collision is calculated by multiplying the probabilities that each new record goes into a unique slot. This gives approximately 0.55. 
Therefore, the probability of at least one collision is obtained by subtracting this from 1, i.e., 1-0.55 = 0.45. Hence, the probability of collision before the table is 10% full is 0.45.

[ Option A ]

The load factor (α) of a hash table is defined as the ratio of the number of stored elements (n) to the number of slots (m), that is
Load Factor (α) = Number of Elements (n) / Number of Slots (m)
Here, the load factor is 300 and the number of elements stored is 10800.
Therefore, Load Factor = 10800/300 = 36

[ Option D ]

Given:

• Hash Function: H(K) = K mod 10
• Keys (in-order insertion): [40, 27, 19, 48, 7]
• Collision Resolution: Linear Probing
• Memory addresses available: 0 to 9 (single digit)

Step-by-step Insertion with Linear Probing:
Insert 40:

• H(40) = 40 % 10 = 0
• Store at address 0

Insert 27:

• H(27) = 27 % 10 = 7
• Store at address 7

Insert 19:

• H(19) = 19 % 10 = 9
• Store at address 9

Insert 48:

• H(48) = 48 % 10 = 8
• Store at address 8

Insert 7:

• H(7) = 7 % 10 = 7
• Address 7 is already occupied (by 27)

Use linear probing (check next available slot)
Try address 8 →  Already taken (by 48)
Try address 9 →  Already taken (by 19)
Try address 0 →  Already taken (by 40)
Try address 1 →  Free
So, 7 is stored at address 1