In Java Language 3. An ordered dictionary containing 10 12 data items of the for
ID: 3580914 • Letter: I
Question
In Java Language
3. An ordered dictionary containing 1012 data items of the form (key,data) needs to be stored in disk. The disk hardware allows data blocks of size b to be 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 eciently 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 AVL 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 be the root of the smallest unbalance subtree in T. Let y be the child of z with larger height, and let x be the child of y with larger height. After re-balancing the tree (and, regardless of whether an LL, LR, RR, or RL rotation was performed), which node will be the root of the subtree formerly rooted at z? Assume that all keys stored in T are dierent.
(A) x
(B) y
(C) The node among x, y, z storing the largest key.
(D) The node among x, y, z storing the middle key.
(E) The node among x, y, z storing the smallest key.
Explanation / Answer
3.An ordered dictionary containing 1012 data items of the form (key,data) needs to be stored in disk. The disk hardware allows data blocks of size b to be 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 eciently as possible in the worst case?
answer:
(D) A B-tree in which every node has size b.
4.Let T be an AVL tree. Suppose that after adding a new data item to T, the tree becomes unbalanced. Let node z be the root of the smallest unbalance subtree in T. Let y be the child of z with larger height, and let x be the child of y with larger height. After re-balancing the tree (and, regardless of whether an LL, LR, RR, or RL rotation was performed), which node will be the root of the subtree formerly rooted at z? Assume that all keys stored in T are dierent.
(D) The node among x, y, z storing the middle key.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.