## Programming Hash Tables :A

Question 1 |

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below. Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

A | 46, 42, 34, 52, 23, 33 |

B | 46, 34, 42, 23, 52, 33 |

C | 34, 42, 23, 52, 33, 46 |

D | 42, 46, 33, 23, 34, 52 |

Question 1 Explanation:

The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.

Question 2 |

What is a hash function?
a)

A | A function has allocated memory to keys |

B | A function that computes the location of the key in the array |

C | A function that creates an array |

D | None of the mentioned |

Question 2 Explanation:

In a hash table, there are fewer array positions than the keys, so the position of the key in the array has to be computed, this is done using the hash function.

Question 3 |

What is the search complexity in direct addressing?

A | O(n) |

B | O(logn) |

C | O(nlogn) |

D | O(1) |

Question 3 Explanation:

Since every key has a unique array position, searching takes a constant time

Question 4 |

What is the best that can be the techniques to avoid collision?

A | Make the hash function appear random |

B | Use the chaining method |

C | Use uniform hashing |

D | All of the mentioned |

Question 4 Explanation:

Making the hash function random is not really a good choice, although it is considered one of the techniques to avoid collisions along with chaining and simple uniform hashing.Chaining is the best

Question 5 |

Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?

A | 40 |

B | 2 |

C | 5 |

D | 10 |

Question 5 Explanation:

For each entry probability of collision is 1/20 {as possible total spaces =20, and an entry will go into only 1 place}
Say after inserting x values probability becomes ½
(1/20).x = ½
X=10

There are 5 questions to complete.

You have completed

questions

question

Your score is

Correct

Wrong

Partial-Credit

You have not finished your quiz. If you leave this page, your progress will be lost.

Correct Answer

You Selected

Not Attempted

Final Score on Quiz

Attempted Questions Correct

Attempted Questions Wrong

Questions Not Attempted

Total Questions on Quiz

Question Details

Results

Date

Score

Hint

Time allowed

minutes

seconds

Time used

Answer Choice(s) Selected

Question Text

All done

Need more practice!

Keep trying!

Not bad!

Good work!

Perfect!