1, (12%) True or False? Circle T if the statement is true and F if it is not tru
ID: 3706239 • Letter: 1
Question
1, (12%) True or False? Circle T if the statement is true and F if it is not true. T T F F Building a heap fron an array of n elements in the worst case requires ?(n log n) time. If the size of a hash table is a prime number p, and it uses quadratic probing, an insertion will always succeed if the table has Ip/2 empty cells. T F Inserting an item into a B-tree all of whose current data nodes are completely full may not cause the height of the tree to increase. F In a hash table using separate chaining, the worst-case number of probes in an unsuccessul search can be greater than the load factor. In a hash table using linear probing with load factor ?, the average number of probe. fr an insertion is (1 +1/(1-A)2). T T F T F After a deletion in an AVL tree, if an LL rotation must be applied at a node p to rebalane the tree, the height of the rebalanced tree may sometimes be the same ns it was before thhe rotation.Explanation / Answer
1. Building a heap from an array of n elements in the worst case requires O(n logn) time . - True, the worst case complexity is O(n logn) for building a heap from an array of n elements.
2. If the size of a hash table is a prime number p, and it uses quadratic probing, an insertion will always succeed if the table has [p/2] empty cells - True, if the size of the hashtable is a prime number and also, if the table has [p/2] empty cells, then quadratic probing will find an empty slot in N/2 probes.
3. Inserting an item into a B-Tree all of whose current data nodes are completely full may not cause the height of the tree to increase. - False, it will cause the height of the tree to increase if we insert a new node on top of the B-Tree all of whose current data nodes are completely full.
4. In a hash table using separate chaining, the worst case number of probes in an unsuccessful search can be greater than the load factor - True, In worst case of separate chaining, all N items will be inserted to the same list and then we will be reduced to linear search on that list, thus the worst case number of probes in an unsuccessful search can be greater than the load factor.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.