MATH-A 100: Quiz 6 - Hash Table

Question 1

What is a hash table? A structure that maps values to keys A structure that maps keys to values A structure used for storage A structure used to implement stack and queue, Question 2 If several elements are competing for the same bucket in the hash table, what is it called? Diffusion Replication Collision Duplication, Question 2 What is direct addressing? Distinct array position for every possible key Fewer array positions than keys Fewer keys than array positions Same array position for all keys, Question 4 What is the search complexity in direct addressing? O(n) O(logn) O(nlogn) O(1), Question 5 In simple chaining, what data structure is appropriate?Singly linked list Doubly linked list Circular linked list Binary trees, Question 6 What is simple uniform hashing? Every element has equal probability of hashing into any of the slots A weighted probabilistic method is used to hash elements into the slots Elements has Random probability of hashing into array slots Elements are hashed based on priority, Question 7 What is the load factor? Average array size Average key size Average chain length Average hash table length, Question 8 What is the hash function used in the division method? h(k) = k/m h(k) = k mod m h(k) = m/k h(k) = m mod k, Question 9 What is the hash function used in multiplication method? h(k) = floor(m(kA mod 1)) h(k) = ceil(m(kA mod 1)) h(k) = floor(kA mod m) h(k) = ceil( kA mod m), Question 10 Using division method, in a given hash table of size 157, the key of value 172 be placed at position _____ 19 72 15 17, Question 11 What is the table size when the value of p is 7 in multiplication method of creating hash functions? 14 128 49 127 Question 12 The task of generating alternative indices for a node is called? Collision handling Collision detection Collision recovery Closed hashing, Question 13 Which of the following is not a collision resolution technique? Separate chaining Linear probing Quadratic probing Hashing, Question 14 What should be the load factor for separate chaining hashing? 0.5 1 1.5 2, Question 15 What is the worst case search time of a hashing using separate chaining algorithm? O(N log N) O(N) O(N2) O(N3)