1 . Suppose that an open-address hash table has a capacity of 811 and it contain

Question

1 .

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

#2.

Suppose you are building an open address hash table with double hashing. The hash table capacity is n, so that the valid hash table indexes range from 0 to n. Fill in the blanks:

In order to ensure that every array position is examined, the value returned by the second hash function must be ________________________ with respect to n.

One way to ensure this good behavior is to make n be _______________, and have the return value of the second hash function range from _________ to _________ (including the end points).

One way to ensure this good behavior is to make n be _______________, and have the return value of the second hash function range from _________ to _________ (including the end points).

Suppose you are building an open address hash table with double hashing. The hash table capacity is n, so that the valid hash table indexes range from 0 to n. Fill in the blanks:

#3     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.

   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

Explanation / Answer

1) 6

4) b

5)c

6) a

7)

Total number of entries=10

The entries that may lead to 2 are 7,8,9,10,1,2

So its 6/10 = 0.6

8)d

9) d

10) b

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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