Which one of the following data structure can have search efficiency in O(1) tim

Question

Which one of the following data structure can have search efficiency in O(1) time? a) Linked-List b) Heap tree c) Hash Table d) B + tree The keys 2, 3, 5, 12, 13, 15, 18, 23 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k (mod 10) and linear probing. What is the resultant hash table? a) a b) b c) c d) d In a max-heap, a) maximum values are stored in order b) parent nodes have large value than child nodes c) minimum value is contained by the root node d) none of the above What is the worst-case runtime complexity of finding the largest item in a max-heap of n nodes? a)O(n) b)O(n log n) c) O(log n) d) O(1)

Explanation / Answer

14.

To get the idea of open addressing concept, you can go through below lines from Wikipedia
.
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:

linear probing in which the interval between probes is fixed--often at 1.
quadratic probing in which the interval between probes increases linearly (hence, the indices are described by a quadratic function).
double hashing in which the interval between probes is fixed for each record but is computed by another hash function.

Thus, C is the correct option ..directly from the definition of linear probing. In linear probing, when a hashed location is already filled, locations are linearly probed until a free one is found.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.