Sample Data Structures Questions Chapter 12 Searching 9. Suppose that an open-ad

Question

Sample Data Structures Questions
Chapter 12
Searching

9. Suppose that an open-address hash table has a capacity of 811 and it contains 81 elements. What is the table's load factor? (An appoximation is fine.) 10. I plan to put 1000 items in a hash table, and I want the average number of accesses in a successful search to be about 2.0. Short Answers Section 12.4 Time Analysis of Hashing A. About how big should the array be if I use open addressing with linear probing? NOTE: For a load factor of A, the average number of accesses is generally (1-i/(1-0 B. About how big should the array be if I use chained hashing? NOTE: For a load factor of A, the average number of accesses is generally (1+A/2).

Explanation / Answer

The answer to Question 9. load factor= (number of elements present)/(capacity of array)= 81/811= 0.0998~0.1

The answer to Question10. A. ->Average number of accesses =2= 1/2(1+1/(1-A)) .

This gives, A ( load factor)=2/3

A=Items to put in hash table/size of array= 1000/size of array=2/3

So, Size of array=1500.

The answer to Question 10. B->Average number of accesses =2= (1+A/2) .

This gives, A ( load factor)=2

A=Items to put in hash table/size of array= 1000/size of array=2

So, Size of array=500.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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