10. 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 unbalanced subtree in T. Let y be 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, 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 (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 x, y, z storing the smallest key 11. A very large collection of data items is to be stored in a ordered dictionary that resides in the hard disk of a computer. Which of the following data structures provides the most efficient implementation in the worst case for the ordered dictionary? The operations that we wish to perform on the ordered dictionary are put, get, remove, smallest, largest, successor and predecessor (A) An AVL tree. Since AVL trees are balances search trees they minimize the number of accesses to the disk (B) A hash table that uses separate chaining to resolve collisions. Since this data structure allows us to find information in O(1) time in average, each operation of the ordered dictionary needs to access the disk only once. (C) A B-tree in which each node stores one data item. Since nodes store one data item, this tree minimizes the amount of information transferred between the disk and main memory (D) A B-tree with nodes of the same size as a disk block. This data structure minimizes the number of disk accesses (E) A linked list sorted increasingly according to the keys of the data items. Each node of the linked list stores one data item. This data structure allows most operations of the ordered dictionary to be performed while accessing the disk only a constant number of times 12. Let G be an undirected, connected graph. Let u be a vertex of G. Consider the following algorithm. At the beginning all vertices of G are unmarked. Algorithm B(G, u) Mark u ? 0 for each edge (u, v) incident on u do { if v is not marked then c c+ B(G, v) ret urn c What does the algorithm do? (A) It computes the number of edges in G (B) It computes the sum of the degrees of all the vertices in G C) It computes the number of edges in the path from u to v (D) It computes the number of edges incident on u (E) It computes the number of vertices in G