3. An ordered dictionary containing 1012 data items of the form (key ,data) need

Question

3. An ordered dictionary containing 1012 data items of the form (key ,data) needs to he stored in disk. The disk hardware allows data blocks of size b to he transferred to main memory every time that the disk is accessed. Which of the following data structures would allow the find (key) operation to be performed as efficiently as possible in the worst case? (A) A B-tree of order b. (B) A B-tree in which every node stores 1012/b data items. (C) A B-tree in which every node stores b data items. (D) A B-tree in which every node has size b. (E) An AVE tree. 4. Let T be an AVL tree. Suppose that after adding a new data item to T, the tree becomes unbalanced. Let node z he the root of the smallest unbalance subtree in T. Let y he the child of z with larger height., and let r be the child of y with larger height. After re-balancing the tree (and. regardless of whether an LL, LII., RB. or RL rotation was performed), which node will he the root of the subtree formerly rooted at z? Assume that all keys stored in T are different. (A)x (B)y (C) The node among r, y, z storing the largest key. (D) The node among r, y, z storing the middle key. (E) The node among r, y, z storing the smallest key.

Explanation / Answer

3. (D) A B-tree in which every node has size b.

4. (D) The node among x, y, z storing the middle key.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.