Q1. What is the search complexity in direct addressing?.
A. O(n).
B. O(logn).
C. O(nlogn).
D. O(1).
Answer= 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.
Answer= 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.
Answer= Average chain length
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).
Answer= O(1)
Q7. In simple chaining, what data structure is appropriate?.
A. Singly linked list.
B. Doubly linked list.
C. Circular linked list.
D. Binary trees.
Answer= Doubly linked list
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.
D. Open addressing.
Answer= Collision
Q9. What data organization method is used in hash tables?.
A. Stack.
B. Array.
C. Linked list.
D. Queue
Answer= Linked list
Q10. The task of generating alternative indices for a node is called?.
A. Collision handling.
B. Collision detection.
C. Collision recovery.
D. Closed hashing.
Answer= Collision handling
Q11. Which of the following is not a collision resolution technique?.
A. Separate chaining.
B. Linear probing.
C. Quadratic probing.
D. Hashing.
Answer= 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.
Answer= TRUE
Q13. In a hash table of size 10, where is element 7 placed?.
A. 6.
B. 7.
C. 17.
D. 16.
Answer= 7
Q14. What should be the load factor for separate chaining hashing?.
A. 0.5.
B. 1.
C. 1.5.
D. 2.
Answer= 1
Q15. Which of the following operations are done in a hash table?.
A. Insert only.
B. Search only.
C. Insert and search.
D. Replace.
Answer= Insert and search
Q16. Which of the following is identical to that of a separate chaining hash node?.
A. Linked list.
B. Array.
C. Stack.
D. Queue
Answer= Linked list
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).
Answer= H(x)=x mod table size
Q18. Which of the following is a disadvantage of using separate chaining using linked lists?.
A. It requires many pointers.
B. It requires linked lists.
C. It uses array.
D. It does not resolve collision.
Answer= It requires many pointers
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).
Answer= O(N)
Q20. How many properties will an equivalent relationship satisfy?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 3
Q21. Which of the following is used in hash tables to determine the index of any input record?.
A. hash function.
B. hash linked list.
C. hash tree.
D. hash chaining.
Answer= hash function
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.
Answer= faster access of data
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).
Answer= O(1)
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).
Answer= O(1)
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).
Answer= O(1)
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.
Answer= TRUE
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?.
A. Open addressing.
B. Chaining using linked list.
C. Chaining using doubly linked list.
D. Chaining using binary tree.
Answer= Open addressing
Q30. Which of the following technique stores data in a separate entity in case of a collision?.
A. Open addressing.
B. Chaining using doubly linked list.
C. Linear probing.
D. Double hashing.
Answer= Chaining using doubly linked list
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.
Answer= hash table using open addressing
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.
Answer= takes more space
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).
Answer= O(1)
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).
Answer= O(1)
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).
Answer= O(1)
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.
Answer= All of the mentioned
Q39. Which of the following technique stores data separately in case of a collision?.
A. Open addressing.
B. Double hashing.
C. Quadratic probing.
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.
Answer= TRUE
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.
Answer= FALSE
Q42. Which of the following helps keys to be mapped into addresses?.
A. hash function.
B. separate chaining.
C. open addressing.
D. chaining using a linked list.
Answer= hash function
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.
Answer= faster access of data
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).
Answer= O(1)
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).
Answer= O(1)
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).
Answer= O(1)
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.
Answer= TRUE
Q49. What is the advantage of using linked list over the doubly linked list for chaining?.
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.
Answer= it takes less memory
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).
Answer= O(n)
Q51. Which of the following technique is used for handling collisions in a hash table?.
A. Open addressing.
B. Hashing.
C. Searching.
D. Hash function.
Answer= Open addressing
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.
Answer= FALSE
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.
Answer= Primary collision
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.
Answer= 2.5 and 1.5
Q56. What is the load factor for an open addressing technique?.
A. 1.
B. 0.5.
C. 1.5.
D. 0.
Answer= 0.5
Q57. Which of the following is not a collision resolution strategy for open addressing?.
A. Linear probing.
B. Quadratic probing.
C. Double hashing.
D. Rehashing.
Answer= 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 .
Answer= TRUE
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.
Answer= F(i)=i
Q60. ___________ is not a theoretical problem but actually occurs in real implementations of probing..
A. Hashing.
B. Clustering.
C. Rehashing.
D. Collision.
Answer= Clustering
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.
Answer= TRUE
Q63. Which of the following schemes does quadratic probing come under?.
A. rehashing.
B. extended hashing.
C. separate chaining.
D. open addressing.
Answer= open addressing
Q64. Quadratic probing overcomes primary collision..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= TRUE
Q65. What kind of deletion is implemented by hashing using open addressing?.
A. active deletion.
B. standard deletion.
C. lazy deletion.
D. no deletion.
Answer= lazy 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.
Answer= FALSE
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.
Answer= F(i)=i2
Q68. How many constraints are to be met to successfully implement quadratic probing?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
Q69. Which among the following is the best technique to handle collision?.
A. Quadratic probing.
B. Linear probing.
C. Double hashing.
D. Separate chaining.
Answer= Quadratic probing
Q70. Which of the following techniques offer better cache performance?.
A. Quadratic probing.
B. Linear probing.
C. Double hashing.
D. Rehashing.
Answer= Linear probing
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.
D. open addressing.
Answer= 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).
Answer= h(k) = lowerbound(km)
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.
Answer= FALSE
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.
Answer= 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.
Answer= Any prime number
Q78. Which scheme provides good performance?.
A. open addressing.
B. universal hashing.
C. hashing by division.
D. hashing by multiplication.
Answer= universal hashing
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.
Answer= 15
Q80. How many steps are involved in creating a hash function using a multiplication method?.
A. 1.
B. 4.
C. 3.
D. 2.
Answer= 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.
Answer= 128
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.
Answer= 67
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).
Answer= Theta(n)
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.
Answer= TRUE
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.
Answer= TRUE
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.
Answer= (h1(k) + i*h2(k))mod m
Q89. On what value does the probe sequence depend on?.
A. c1.
B. k.
C. c2.
D. m.
Answer= k
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.
Answer= FALSE
Q91. What is the running time of double hashing?.
A. Theta(m).
B. Theta(m2).
C. Theta(m log k).
D. Theta(m3).
Answer= Theta(m)
Q92. Which technique has the greatest number of probe sequences?.
A. Linear probing.
B. Quadratic probing.
C. Double hashing.
D. Closed hashing.
Answer= Double hashing
Q93. What is the value of m' if the value of m is 19?.
A. 11.
B. 18.
C. 17.
D. 15.
Answer= 17
Q94. Hash tree is generalization of ______.
A. Heap.
B. Hash list.
C. BST.
D. B - tree.
Answer= Hash list
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.
Answer= TRUE
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 .
Answer= Tiger tree hash
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.
Answer= Merkle 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.
Answer= 4
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.
Answer= in digital currency
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).
Answer= O(logk(n))
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.
Answer= TRUE
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).
Answer= O(n)
Q104. Which technique is used for finding similarity between two sets?.
A. MinHash.
B. Stack.
C. Priority Queue
D. PAT Tree.
Answer= MinHash
Q105. Who invented the MinHash technique?.
A. Weiner.
B. Samuel F. B. Morse.
C. Friedrich Clemens Gerke.
D. Andrei Broder.
Answer= 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.
Answer= MinHash
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.
Answer= MinHash
Q108. Which indicator is used for similarity between two sets?.
A. Rope Tree.
B. Jaccard Coefficient.
C. Tango Tree.
D. MinHash Coefficient.
Answer= Jaccard 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.
Answer= Rope Tree
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.
Answer= 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).
Answer= 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.
Answer= TRUE
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.
Answer= TRUE
Q115. 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.
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).
Answer= 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).
Answer= 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.
Answer= It saves space
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).
Answer= 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.
Answer= It saves space
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.
Answer= (n*(n-1))/2
Q124. The given Graph is regular..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE