ZuoTi.Pro
Question

13) consider the following sequence of keys to be inserted in a hash table of size...

13) consider the following sequence of keys to be inserted in a hash table of size 13 that uses a quadratic probing to resolve collisions select the choice that indicateds what the hash table looks like after all the keys are inserted (0 indicates an empty slot)

{23, 4, 78 , 17 , 30, 81, 41, 5}

a) 78, 41, 0, 81, 4, 5, 17, 0, 30, 0, 23, 0, 0

b) 78, 17, 41, 81, 4, 5, 0, 30, 0, 23, 0, 0

c) 78, 41, 81, 30, 4, 17, 5, 0, 0, 0, 23, 0, 0

d) 78, 41, 81, 4, 17, 5, 30, 0, 0, 0, 23, 0, 0

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

In quadratic probing we search for if hash(x) % S is full, then we try for (hash(x) + 1*1) % S and if (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S and if (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S...like this it goes on in squared form where s is table size and hash(X) is the key element. Since here no hash function is given we consider it to be h(i) = i % 13.

- Hash table size = 13 : ..23;4,78, 17,30 ,81,41,5. Hash function h (i) = i mad 13 1723 28 7.13 = 10 23 is placed in 10th posies 5%.18 25 (occupied) (5+1)%.13 6 placed in 6th position 5 is According to solution . Order of placement chould be 78 41:81

Most suitable is option d though the zeros are not properly placed.

0 0
Add a comment
Know the answer?
Add Answer to:
13) consider the following sequence of keys to be inserted in a hash table of size...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • 5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and...

    5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and the hash function h(x) = x mod 5. i. (1) Pick 8 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 ... or 10, 20, 30, 40, .. are not acceptable random sequences). ii. (2) Draw a sketch of the hash table...

  • #3 [3 points] Sketch a hash table of size N=11, where the hash function is hash(key) = key mod N and quadratic probing is used to resolve collisions, after the following elements are inserted: 20, 42,...

    #3 [3 points] Sketch a hash table of size N=11, where the hash function is hash(key) = key mod N and quadratic probing is used to resolve collisions, after the following elements are inserted: 20, 42, 45, 49, 62, 72, 95. The probes are based on this equation: (H+c1∗i+c2∗i2)mod(N) and c1=1, c2=1. If direct hashing was used to store the same elements as the previous problems (20, 42, 45, 49, 62, 72, 95), what should be the minimum size of...

  • Assume data is to be stored in a hash table using the following keys: 62,77.26, 42,...

    Assume data is to be stored in a hash table using the following keys: 62,77.26, 42, 52,76 Assume the hash table size is 7, the hash function used is the modulo function i.e. h/key) = key % table_size, and collisions are handled using linear probing. What's the content of the table after all keys are mapped to the hash table? (List keys starting from table index 0 and on Separate numbers by a comma and a single space, and indicate...

  • Use a hash table with a fixed size of 10. Don't grow the table or do...

    Use a hash table with a fixed size of 10. Don't grow the table or do any rehashing. Use the hash function H(x) = x % 10. Use Quadratic Probing to resolve collisions in part a, b and c: a)  Insert the items into an initially empty hash table. Draw the table that results. 71 23 73 99 44 b) Draw the table that results from adding 79 to the table in part a c) Draw the table that results from...

  • 11. Dra The size The hash function used is: the contents of the 13 hash tables...

    11. Dra The size The hash function used is: the contents of the 13 hash tables below. Show your work for partial r hash table is HOk)-k mod 7 13, 17, 6, 24, 3 a) Resolve collisions with chaining b) Double hashing, where W20)-7-0mod 5) 0 1 1 2 2 3 3 4 4 5 5 6 6 c) What is the load factor for the table a? d) What is the load factor for the table b? f) Is...

  • It should be really short and simple to do this. #1 [8 points) Sketch a hash...

    It should be really short and simple to do this. #1 [8 points) Sketch a hash table of size N=11, where the hash function is hash(key) = key mod N and chaining is used to resolve collisions, when the following elements are inserted: 20, 42, 45, 49, 62, 72,95 0 1 2 3 4 5 6 7 8 9 10 What is the size of the largest bucket? — #2 [7 points) Sketch a hash table of size N=11, where...

  • 1. Given a hash table with size 10, hash function is hash(k) = k % 10,...

    1. Given a hash table with size 10, hash function is hash(k) = k % 10, and quadratic probing strategy is used to solve collisions. Please insert the keys 19, 68, 59, 20, 32, 88, 56 in the hash table. 2. Let T be a binary tree with 31 nodes, what is the smallest possible height of T? What is the largest possible height of T?

  • Hash the values 94, 11, 39, 20, 16, 5, 12, 44, 13, 88 and 23 into...

    Hash the values 94, 11, 39, 20, 16, 5, 12, 44, 13, 88 and 23 into a hash table with 11 slots. Handle collisions by linear probing. Use the hash function: h(i) (3 * i + 5) % 11 Type in each key on the same line as the index of the slot where it is eventually inserted. YOUR ANSWER TO QUESTION A: 0: 1: 2: 3: 5: 7: 9: 10:

  • 6. A hash table has size 7, uses quadratic probing (f(i) = 1), and has hash...

    6. A hash table has size 7, uses quadratic probing (f(i) = 1), and has hash function h(2) = 2%7. (Recall, % is the Java "mod" function.) Draw the contents of the hash table after the following sequence of insertions: insert 0, insert 7, insert 14, insert 21. The hash table is initially empty.

  • Separate Chaining A hash table of size 7 uses separate chaining to resolve collisions. A polynomial...

    Separate Chaining A hash table of size 7 uses separate chaining to resolve collisions. A polynomial hash function where a 33 is used. Sketch the table's contents after the following words have been added in the exact order shown: find, edge, body, race, plan, beat, they You may find it useful to create a list of lowercase letters and their ASCII numeric value. The letter a's value is 97 and z's value is 122. Linear Probing: A hash table of...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT