# Hash Table in Data Structure and Algorithms MCQs

Q1. What is the search complexity in direct addressing?.

A. O(n).

B. O(logn).

C. O(nlogn).

D. O(1).

Q2. 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.

Answer= A function that computes the location of the key in the array

Q3. 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.

Q4. What is the load factor?.

A. Average array size.

B. Average key size.

C. Average chain length.

D. None of the mentioned.

Q5. 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.

Answer= Every element has equal probability of hashing into any of the slots

Q6. In simple uniform hashing, what is the search complexity?.

A. O(n).

B. O(logn).

C. O(nlogn).

D. O(1).

Q7. In simple chaining, what data structure is appropriate?.

D. Binary trees.

Q8. The case in which a key other than the desired one is kept at the identified location is called?.

A. Hashing.

B. Collision.

C. Chaining.

Q9. What data organization method is used in hash tables?.

A. Stack.

B. Array.

D. Queue

Q10. The task of generating alternative indices for a node is called?.

A. Collision handling.

B. Collision detection.

C. Collision recovery.

D. Closed hashing.

Q11. Which of the following is not a collision resolution technique?.

A. Separate chaining.

B. Linear probing.

D. Hashing.

Q12. Hashing is the problem of finding an appropriate mapping of keys into addresses..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q13. In a hash table of size 10, where is element 7 placed?.

A. 6.

B. 7.

C. 17.

D. 16.

Q14. What should be the load factor for separate chaining hashing?.

A. 0.5.

B. 1.

C. 1.5.

D. 2.

Q15. Which of the following operations are done in a hash table?.

A. Insert only.

B. Search only.

C. Insert and search.

D. Replace.

Q16. Which of the following is identical to that of a separate chaining hash node?.

B. Array.

C. Stack.

D. Queue

Q17. Which of the following is the hashing function for separate chaining?.

A. H(x)=(hash(x)+f(i)) mod table size.

B. H(x)=hash(x)+i2  mod table size.

C. H(x)=x mod table size.

D. H(x)=x mod (table size * 2).

Q18. Which of the following is a disadvantage of using separate chaining using linked lists?.

A. It requires many pointers.

C. It uses array.

D. It does not resolve collision.

Q19. What is the worst case search time of a hashing using separate chaining algorithm?.

A. O(N log N).

B. O(N).

C. O(N2).

D. O(N3).

Q20. How many properties will an equivalent relationship satisfy?.

A. 1.

B. 2.

C. 3.

D. 4.

Q21. Which of the following is used in hash tables to determine the index of any input record?.

A. hash function.

C. hash tree.

D. hash chaining.

Q22. What is the advantage of a hash table as a data structure?.

A. faster access of data.

B. easy to implement.

C. very efficient for less number of entries.

D. exhibit good locality of reference.

Q23. What is the use of a hash function?.

A. to calculate and return the index of corresponding data.

B. to store data.

C. to erase data.

D. to change data.

Answer= to calculate and return the index of corresponding data

Q24. What is the time complexity of insert function in a hash table using a doubly linked list?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q25. What is the time complexity of search function in a hash table using a doubly linked list?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q26. What is the time complexity of delete function in the hash table using a doubly linked list?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q27. Hashing can be used to encrypt and decrypt digital signatures..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q28. What is the advantage of using a doubly linked list for chaining over singly linked list?.

A. it takes less memory.

B. it is easy to implement.

C. it makes the process of insertion and deletion faster.

D. it causes less collisions.

Answer= it makes the process of insertion and deletion faster

Q29. Which of the following technique stores data in the hash table itself in case of a collision?.

C. Chaining using doubly linked list.

D. Chaining using binary tree.

Q30. Which of the following technique stores data in a separate entity in case of a collision?.

B. Chaining using doubly linked list.

C. Linear probing.

D. Double hashing.

Q31. Which of the following variant of a hash table has the best cache performance?.

A. hash table using a linked list for separate chaining.

B. hash table using binary search tree for separate chaining.

C. hash table using open addressing.

D. hash table using a doubly linked list for separate chaining.

Q32. What is the advantage of hashing with chaining?.

A. cache performance is good.

B. uses less space.

C. less sensitive to hash function.

D. has a time complexity of O(n) in the worst case.

Answer= less sensitive to hash function

Q33. What is the disadvantage of hashing with chaining?.

A. not easy to implement.

B. takes more space.

C. quite sensitive to hash function.

D. table gets filled up easily.

Q34. What is the time complexity of insert function in a hash table using a binary tree?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q35. What is the time complexity of the search function in a hash table using a binary tree?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q36. What is the time complexity of the delete function in the hash table using a binary tree?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q37. What is the advantage of a hash table over BST?.

A. hash table has a better average time complexity for performing insert, delete and search operations.

B. hash table requires less space.

C. range query is easy with hash table.

D. easier to implement.

Answer= hash table has a better average time complexity for performing insert, delete and search operations

Q38. What is the advantage of BST over the hash table?.

A. BST is easier to implement.

B. BST can get the keys sorted by just performing inorder traversal.

C. BST can perform range query easily.

D. All of the mentioned.

Q39. Which of the following technique stores data separately in case of a collision?.

B. Double hashing.

D. Chaining using a binary tree.

Answer= Chaining using a binary tree

Q40. Separate chaining is easier to implement as compared to open addressing..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q41. In open addressing the hash table can never become full..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q42. Which of the following helps keys to be mapped into addresses?.

A. hash function.

B. separate chaining.

D. chaining using a linked list.

Q43. What is the advantage of the hash table over a linked list?.

A. faster access of data.

B. easy to implement.

C. very efficient for less number of entries.

D. exhibit good locality of reference.

Q44. Which of the following trait of a hash function is most desirable?.

A. it should cause less collisions.

B. it should cause more collisions.

C. it should occupy less space.

D. it should be easy to implement.

Answer= it should cause less collisions

Q45. What is the time complexity of insert function in a hash table using list head?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q46. What is the time complexity of search function in a hash table using list head?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q47. What is the time complexity of delete function in the hash table using list head?.

A. O(1).

B. O(n).

C. O(log n).

D. O(n log n).

Q48. A hash table may become full in the case when we use open addressing..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

A. it takes less memory.

B. it causes more collisions.

C. it makes the process of insertion and deletion faster.

D. it causes less collisions.

Q50. What is the worst case time complexity of insert function in the hash table when the list head is used for chaining?.

A. O(1).

B. O(n log n).

C. O(log n).

D. O(n).

Q51. Which of the following technique is used for handling collisions in a hash table?.

B. Hashing.

C. Searching.

D. Hash function.

Q52. By implementing separate chaining using list head we can reduce the number of collisions drastically..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q53. Which of the following is an advantage of open addressing over separate chaining?.

A. it is simpler to implement.

B. table never gets full.

C. it is less sensitive to hash function.

D. it has better cache performance.

Answer= it is simpler to implement

Q54. Which of the following problems occur due to linear probing?.

A. Primary collision.

B. Secondary collision.

C. Separate chaining.

D. Extendible hashing.

Q55. How many probes are required on average for insertion and successful search?.

A. 4 and 10.

B. 2 and 6.

C. 2.5 and 1.5.

D. 3.5 and 1.5.

A. 1.

B. 0.5.

C. 1.5.

D. 0.

Q57. Which of the following is not a collision resolution strategy for open addressing?.

A. Linear probing.

C. Double hashing.

D. Rehashing.

Q58. In linear probing, the cost of an unsuccessful search can be used to compute the average cost of a successful search..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned  .

Q59. Which of the following is the correct function definition for linear probing?.

A. F(i)= 1.

B. F(i)=i.

C. F(i)=i2.

D. F(i)=i+1.

Q60. ___________  is not a theoretical problem but actually occurs in real implementations of probing..

A. Hashing.

B. Clustering.

C. Rehashing.

D. Collision.

Q61. What is the hash function used in linear probing?.

A. H(x)= key mod table size.

B. H(x)= (key+ F(i2)) mod table size.

C. H(x)= (key+ F(i)) mod table size.

D. H(x)= X mod 17.

Answer= H(x)= (key+ F(i)) mod table size

Q62. Hashing can be used in online spelling checkers..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q63. Which of the following schemes does quadratic probing come under?.

A. rehashing.

B. extended hashing.

C. separate chaining.

Q64. Quadratic probing overcomes primary collision..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q65. What kind of deletion is implemented by hashing using open addressing?.

A. active deletion.

B. standard deletion.

C. lazy deletion.

D. no deletion.

Q66. In quadratic probing, if the table size is prime, a new element cannot be inserted if the table is half full..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q67. Which of the following is the correct function definition for quadratic probing?.

A. F(i)=i2.

B. F(i)=i.

C. F(i)=i+1.

D. F(i)=i2+1.

Q68. How many constraints are to be met to successfully implement quadratic probing?.

A. 1.

B. 2.

C. 3.

D. 4.

Q69.  Which among the following is the best technique to handle collision?.

B. Linear probing.

C. Double hashing.

D. Separate chaining.

Q70. Which of the following techniques offer better cache performance?.

B. Linear probing.

C. Double hashing.

D. Rehashing.

Q71. What is the formula used in quadratic probing?.

A. Hash key = key mod table size.

B. Hash key=(hash(x)+F(i)) mod table size.

C. Hash key=(hash(x)+F(i2)) mod table size.

D. H(x) = x mod 17.

Answer= Hash key=(hash(x)+F(i2)) mod table size

Q72. Which scheme uses a randomization approach?.

A. hashing by division.

B. hashing by multiplication.

C. universal hashing.

Q73. Which hash function satisfies the condition of simple uniform hashing?.

A. h(k) = lowerbound(km).

B. h(k)= upperbound(mk).

C. h(k)= lowerbound(k).

D. h(k)= upperbound(k).

Q74. A good hash approach is to derive the hash value that is expected to be dependent of any patterns that might exist in the data..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q75. Interpret the given character string as an integer expressed in suitable radix notation.  Character string = pt.

A. 14963.

B. 14392.

C. 12784.

D. 14452.

Q76. What is the hash function used in the division method?.

A. h(k) = k/m.

B. h(k) = k mod m.

C. h(k) = m/k.

D. h(k) = m  mod k.

Answer= h(k) = k mod m

Q77. What can be the value of m in the division method?.

A. Any prime number.

B. Any even number.

C. 2p - 1.

D. 2p.

Q78. Which scheme provides good performance?.

B. universal hashing.

C. hashing by division.

D. hashing by multiplication.

Q79. Using division method, in a given hash table of size 157, the key of value 172 be placed at position ____.

A. 19.

B. 72.

C. 15.

D. 17.

Q80. How many steps are involved in creating a hash function using a multiplication method?.

A. 1.

B. 4.

C. 3.

D. 2.

Q81. What is the hash function used in multiplication method?.

A. h(k) = floor( m(kA mod 1)).

B. h(k) = ceil( m(kA mod 1)).

C. h(k) = floor(kA mod m).

D. h(k) = ceil( kA mod m).

Answer= h(k) = floor( m(kA mod 1))

Q82. What is the advantage of the multiplication method?.

A. only 2 steps are involved.

B. using constant.

C. value of m not critical.

D. simple multiplication.

Answer= value of m not critical

Q83. What is the table size when the value of p is 7 in multiplication method of creating hash functions?.

A. 14.

B. 128.

C. 49.

D. 127.

Q84. What is the value of h(k) for the key 123456?.

A. Given: p=14, s=2654435769, w=32.

B. 123.

C. 456.

D. 70.

Q85. What is the average retrieval time when n keys hash to the same slot?.

A. Theta(n).

B. Theta(n2).

C. Theta(nlog n).

D. Big-Oh(n2).

Q86. Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored..

A. TRUE.

B. FALSE.

C.  Nothing can be said.

D.  None of the mentioned.

Q87. Double hashing is one of the best methods available for open addressing..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q88. What is the hash function used in Double Hashing?.

A. (h1(k) - i*h2(k))mod m.

B. h1(k) + h2(k).

C. (h1(k) + i*h2(k))mod m.

D. (h1(k) + h2(k))mod m.

Q89. On what value does the probe sequence depend on?.

A. c1.

B. k.

C. c2.

D. m.

Q90. The value of h2(k) can be composite relatively to the hash table size m..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q91. What is the running time of double hashing?.

A. Theta(m).

B. Theta(m2).

C. Theta(m log k).

D. Theta(m3).

Q92. Which technique has the greatest number of probe sequences?.

A. Linear probing.

C. Double hashing.

D. Closed hashing.

Q93. What is the value of m' if the value of m is 19?.

A. 11.

B. 18.

C. 17.

D. 15.

Q94. Hash tree is generalization of ______.

A. Heap.

B. Hash list.

C. BST.

D. B - tree.

Q95. Hash tree is used in effective data verification in distributed systems..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q96. Which of the following is a widely used form of the hash tree?.

A. B+ - tree.

B. T tree.

C. Tiger tree hash.

D. Htree .

Q97. Which of the following is true for a Hash tree?.

A. Hashing is used for sequential access.

B. Indexing is used for direct access.

C. Hash tree allows only sequential access.

D. Hashing is used for direct access.

Answer= Hashing is used for direct access

Q98. Hash tree is also known as _____.

A. Merkle tree.

B. T -tree.

C. Hash table.

D. Bx-tree.

Q99. What will be the height of the hash tree with branching factor 2 and with 8 records?.

A. 3.

B. 5.

C. 4.

D. 6.

Q100. Where is the hash tree used?.

A. in digital currency.

B. in sorting of large data.

C. for indexing in databases.

D. in encryption of data.

Q101. What is the worst case time complexity of the insertion in the hash tree?.

A. O(logk(n)).

B. O(n2).

C. O(nlogk(n)).

D. O(kn).

Q102. Sequential access in a Hash tree is faster than in B-trees..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q103. Hash tree is used in data synchronisation. In the worst case the data synchronisation takes ______ time..

A. O(logn).

B. O(n2).

C. O(nlogn).

D. O(n).

Q104. Which technique is used for finding similarity between two sets?.

A. MinHash.

B. Stack.

C. Priority Queue

D. PAT Tree.

Q105. Who invented the MinHash technique?.

A. Weiner.

B. Samuel F. B. Morse.

C. Friedrich Clemens Gerke.

D. Andrei Broder.

Q106. Which technique was firstly used to remove duplicate web pages from search results in AltaVista search engine?.

A. MinHash.

B. Stack.

C. Priority Queue

D. PAT Tree.

Q107. Which technique was firstly used clustering documents using the similarity of two words or strings?.

A. MinHash.

B. Stack.

C. Priority Queue

D. PAT Tree.

Q108. Which indicator is used for similarity between two sets?.

A. Rope Tree.

B. Jaccard Coefficient.

C. Tango Tree.

D. MinHash Coefficient.

Q109. Which of the following is defined as the ratio of total elements of intersection and union of two sets?.

A. Rope Tree.

B. Jaccard Coefficient Index.

C. Tango Tree.

D. MinHash Coefficient.

Q110. When are the members of two sets more common relatively?.

A. Jaccard Index is Closer to 1.

B. Jaccard Index is Closer to 0.

C. Jaccard Index is Closer to -1.

D. Jaccard Index is Farther to 1.

Answer= Jaccard Index is Closer to 1

Q111. How many hashes will be needed for calculating Jaccard index with an expected error less than or equal to 0.05?.

A. 100.

B. 200.

C. 300.

D. 400.

Q112. What is the time required for single variant hashing to maintain the minimum hash queue?.

A. O (log n!).

B. O (n!).

C. O (n2).

D. O (n).

Q113. Is MinHash used as a tool for association rule learning..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

Q114. Did Google conduct a large evaluation for comparing the performance by two technique MinHash and SimHash..

A. TRUE.

B. FALSE.

C.  Nothing Can be said.

D.  None of the mentioned.

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.

Answer= Distinct array position for every possible key

Q116. When is it appropriate to use direct addressing?.

A. When the array is comparatively large.

B. When the universe U of keys is reasonably small.

C. When the universe U of keys is reasonably large.

D. When the array is comparatively small.

Answer= When the universe U of keys is reasonably small

Q117. What is the search complexity in direct addressing?.

A. O(n).

B. O(logn).

C. O(nlogn).

D. O(1).

Q118. What is the time complexity to insert an element into the direct address table?.

A. O(n).

B. O(logn).

C. O(nlogn).

D. O(1).

Q119. 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.

Q120. What is the time complexity to delete an element from the direct address table?.

A. O(n).

B. O(logn).

C. O(nlogn).

D. O(1).

Q121. How is a bit vector better compared to a normal array for implementing the hash table?.

A. It saves time.

B. It saves space.

C. It saves both time and space.

D. None of the mentioned.

Q122. Which of the following statements for a simple graph is correct?.

A. Every path is a trail.

B. Every trail is a path.

C. Every trail is a path as well as every path is a trail.

D. None of the mentioned .

Answer= Every path is a trail

Q123.  What is the number of edges present in a complete graph having n vertices?.

A. (n*(n+1))/2.

B. (n*(n-1))/2.

C. n.

D. Information given is insufficient.