Data Structure MCQ - Hashing
Q1. What is direct addressing?
- Distinct array position for every possible key
- Fewer array positions than keys
- Fewer keys than array positions
- Same array position for all keys
Answer:- (A).
Explanations :Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.
Explanations :Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.
- A function has allocated memory to keys
- A function that computes the location of the key in the array
- A function that creates an array
- A function that computes the location of the values in the array
Answer:- (B).
Explanations :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.
Explanations :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.
- Every element has equal probability of hashing into any of the slots
- A weighted probabilistic method is used to hash elements into the slots
- Elements has Random probability of hashing into array slots
- Elements are hashed based on priority
Answer:- (A).
Explanations :In simple uniform hashing, any given element is equally likely to hash into any of the slots available in the array.
Explanations :In simple uniform hashing, any given element is equally likely to hash into any of the slots available in the array.
- Singly linked list
- Doubly linked list
- Circular linked list
- Binary trees
Answer:- (B).
Explanations :Deletion becomes easier with doubly linked list, hence it is appropriate.
Explanations :Deletion becomes easier with doubly linked list, hence it is appropriate.
- O(n)
- O(logn)
- O(nlogn)
- O(1)
Answer:- (D).
Explanations :Since every key has a unique array position, searching takes a constant time.
Explanations :Since every key has a unique array position, searching takes a constant time.
- A function has allocated memory to keys
- A function that computes the location of the key in the array
- A function that creates an array
- None of the mentioned
Answer:- (B).
Explanations : 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.
Explanations : 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.
- Every element has equal probability of hashing into any of the slots
- A weighted probabilistic method is used to hash elements into the slots
- Elements has Random probability of hashing into array slots
- Elements are hashed based on priority
Answer:- (A).
Explanations :In simple uniform hashing, any given element is equally likely to hash into any of the slots available in the array.
Explanations :In simple uniform hashing, any given element is equally likely to hash into any of the slots available in the array.
- O(n)
- O(logn)
- O(nlogn)
- O(1)
Answer:- (d).
Explanations :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.
Explanations :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.
- faster access of data
- easy to implement
- very efficient for less number of entries
- exhibit good locality of reference
Answer:- (A).
Explanations : Clarification: Hash table is a data structure that has an advantage that it allows fast access of elements. But linked list is easier to implement as compared to the hash table.
Explanations : Clarification: Hash table is a data structure that has an advantage that it allows fast access of elements. But linked list is easier to implement as compared to the hash table.
- it should cause less collisions
- it should cause more collisions
- it should occupy less space
- it should be easy to implement
Answer:- (a).
Explanations : Clarification: Hash function calculates and returns the index for corresponding data. So the most important trait of a hash function is that it should cause a minimum number of collisions.
Explanations : Clarification: Hash function calculates and returns the index for corresponding data. So the most important trait of a hash function is that it should cause a minimum number of collisions.
Copyright © 2022 Shineskill Software Pvt. Ltd., All rights reserved.