Data Structure MCQ - Hashing Function
This section focuses on the "Hashing Function" of the Data Structure. These Multiple Choice Questions (mcq) should be practiced to improve the Data Structure skills required for various interviews (campus interview, walk-in interview, company interview), placement, entrance exam and other competitive examinations.
1. What is a hash table?
A. A structure that maps values to keys
B. A structure that maps keys to values
C. A structure used for storage
D. A structure used to implement stack and queue
View Answer
Ans : B
Explanation: A hash table is used to implement associative arrays which has a key-value pair, so the has table maps keys to values.
2. How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
A. 10
B. 20
C. 30
D. 40
View Answer
Ans : C
Explanation: In a valid insertion sequence, the elements 42, 23 and 34 must appear before 52 and 33, and 46 must appear before 33.
Total number of different sequences = 3! x 5 = 30
In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.
3. If ' h ' is a hashing function and it is used to hash ' n ' keys into a table of size ' m ' where n <= m . What is the expected number of collisions involving a particular key ' x ' ?
A. less than 1.
B. less than n.
C. less than m.
D. less than n / 2.
View Answer
Ans : A
Explanation: No Explanation
4.Hashing technique which allocates fixed number of buckets is classified as
A. dynamic hashing
B. static hashing
C. external hashing
D. internal hashing
View Answer
Ans : C
Explanation:Hashing technique which allocates fixed number of buckets is classified as external hashing.
5.If several elements are competing for the same bucket in the hash table, what is it called?
A. Diffusion
B. Replication
C. Collision
D. None of the mentioned
View Answer
Ans : C
Explanation:If several elements are competing for the same bucket in the hash table, is it called Collision.
6. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
A. 8, _, _, _, _, _, 10
B. 1, 8, 10, _, _, _, 3
C. 1, _, _, _, _, _,3
D. 1, 10, 8, _, _, _, 3
View Answer
Ans : B
Explanation: hashing and probing. Let us put values 1, 3, 8, 10 in the hash of size 7. Initially, hash table is empty
- - - - - - -
0 1 2 3 4 5 6
The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0
1 - - - - - -
0 1 2 3 4 5 6
The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6
1 - - - - - 3
0 1 2 3 4 5 6
The value of function (3x + 4)mod 7 for 8 is 0, but 0 is already occupied, let us put the value(8) at next available space(1)
1 8 - - - - 3
0 1 2 3 4 5 6
The value of function (3x + 4)mod 7 for 10 is 6, but 6 is already occupied, let us put the value(10) at next available space(2)
1 8 10 - - - 3
0 1 2 3 4 5 6
7. What is the advantage of using a dynamic set in direct addressing?
A. It saves time
B. It saves space
C. It saves both time and space
D. None of the mentioned
View Answer
Ans : B
Explanation: Using a dynamic set, the size of the array is restricted to the number of keys, hence saves space.
8. In linear hashing, formula used to calculate number of records if blocking factor, loading factor and file buckets are known is as
A. r =l + bfr + N
B. r =l - bfr - N
C. r =l + bfr - N
D. r =l * bfr * N
View Answer
Ans : D
Explanation: No Explanation
9. What is the load factor?
A. Average array size
B. Average key size
C. Average chain length
D. None of the mentioned
View Answer
Ans : C
Explanation:In simple chaining, load factor is the average number of elements stored in a chain, and is given by the ratio of number of elements stored to the number of slots in the array.
.
10. Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is __________
A. 80
B. 0.0125
C. 8000
D. 1.25
View Answer
Ans : A
Explanation:load factor = (no. of elements) / (no. of table slots) = 2000/25 = 80.
11. What is direct addressing?
A. Distinct array position for every possible key
B. Fewer array positions than keys
C. Fewer keys than array positions
D. None of the mentioned
View Answer
Ans : A
Explanation: Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.
12. What is the search complexity in direct addressing?
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(1)
View Answer
Ans : D
Explanation: Since every key has a unique array position, searching takes a constant time.
13. What is a hash function?
A. A function has allocated memory to keys
B. A function that computes the location of the key in the array
C. A function that creates an array
D. None of the mentioned
View Answer
Ans : B
Explanation: In a hash table, there are fewer array positions than the keys, so the position of the key in the array has to be computed, this is done using the hash function.
14. What can be the techniques to avoid collision?
A. Make the hash function appear random
B. Use the chaining method
C. Use uniform hashing
D. All of the mentioned
View Answer
Ans : D
Explanation: Making the hash function random is not really a good choice, although it is considered one of the techniques to avoid collisions along with chaining and simple uniform hashing.
15. What is simple uniform hashing?
A. Every element has equal probability of hashing into any of the slots
B. A weighted probabilistic method is used to hash elements into the slots
C. All of the mentioned
D. None of the mentioned
View Answer
Ans : A
Explanation: In simple uniform hashing, any given element is equally likely to hash into any of the slots available in the array.
16. In simple uniform hashing, what is the search complexity?
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(1)
View Answer
Ans : D
Explanation: There are two cases, once when the search is successful and when it is unsuccessful, but in both the cases, the complexity is O(1+alpha) where 1 is to compute the hash function and alpha is the load factor.
17. In simple chaining, what data structure is appropriate?
A. Singly linked list
B. Doubly linked list
C. Circular linked list
D. Binary trees
View Answer
Ans : B
Explanation: Deletion becomes easier with doubly linked list, hence it is appropriate.
18.Which of these are core interfaces in the collection framework. Select the one correct answer.
A. Tree
B. Stack
C. Queue
D. Map
E. LinkedList
View Answer
19. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i. 9679, 1989, 4199 hash to the same value
ii. 1471, 6171 hash to the same value
iii. All elements hash to the same value
iv. Each element hashes to a different value
A. i only
B. ii only
C. i and ii only
D. iii or iv
View Answer
Ans : C
Hash function given is mod(10).
9679, 1989 and 4199 all these give same hash value i.e 9
1471 and 6171 give hash value 1
Also Check :
Discussion