An ordered dictionary containing 10^12 data items of the form (key data) needs t
ID: 3579026 • Letter: A
Question
An ordered dictionary containing 10^12 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 efficiently as possible in the worst case? A B-tree of order b A B-tree in which every node stores 10^12/b data items A B-tree in which every node stores b data items. A B-tree in which every node has size b. An AVL tree. 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 different. x y The node among x, y, z storing the largest key. The node among x, y, z storing the middle key The node among z, y, z storing the smallest key.Explanation / Answer
2.(D) The node among x,y,z storing the middle key.
Lets see why consider an AVL tree with root (12)[z] its left child as (10)[y] and 10's left child as (9)[x]. We can see that the tree is unbalanced rooted at z. After perfroming rotation we will get the tree rooted at (10)[y] with its left child as (9)[x]. and right child as (12)[z] .
Lets consider one more case , an AVL tree with root (12)[z] its left child as (10)[y] and 10's right child as (11)[x]. We can see that the tree is unbalanced rooted at z. After perfroming rotation we will get the tree rooted at (11)[x] with its left child as (10)[y]. and right child as (12)[z] .
Which means we the node among x,y,z storing the middle key.
1)(C) , A Btree in which every node stores b data items such that , During each access, whole b size nodes will be fetched, which will help us in faster retrieval.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.