this operation without visiting every node in the tree. 4. Hashing. The set of a
ID: 3906017 • Letter: T
Question
this operation without visiting every node in the tree. 4. Hashing. The set of all possible keys is the set of all integers from 0 to 10,000 inclusive. Consider (a) (4) Insert the keys 45,33,67,70, 19,81 into a hash table with separate chaining. The hash (b) (4) Start with an empty hash table and insert the keys 12, 23, 80,36 using linear probing a hash table of size M = 11 and the hash function h(z) = mod 11 table was initially empty. Draw a sketch of the hash table after the sequence of insertions Determine the final index of each element and the number of probes required to insert each element into the table. (c) (4) Start with an empty hash table and insert t he keys 55, 11,22, 65 using quadratic probing Determine the final index of each element and the number of probes requires element into the table. to insert each (d) (4) Start with an empty hash table and insert the keys 90, 13,24, 17 into a hash table with (e) (2) What is the condition that the load factor should to satisfy in order to have good average () (2) What are the advantages of binary search trees over hash tables? double hashing. The secondary hash function is ha(r)-7-(a mod 7). Determine the final index of each element and the number of probes required to insert each element into the table time performance in linear probing? Page 4 of 5Explanation / Answer
4 a)
0 - 33
1 - 45 ->67
2 -
3 -
4 - 70->81
5 -
6 -
7 -
8 - 19
4 b) 0-
1 - 12
2 - 23
3 - 80
4 - 36
c) 0 - 55
1 - 11
2 -
3 -
4 - 22
5 -
6 -
7 -
8 -
9 - 65
d)
0 -
1 - 13 (number of probe - 1)
2 - 90
3 -
4 - 24 (number of probe - 1)
5 -
6 - 17
e) A good value is 0.75 for linear probing
f) Advantage of binary tree, insertion, search, modifivation, removal are all O(log(n))
and in case of hash table - insertion , deletion, modification - O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.