Some questions have multiple answers please consider that

1.When we say that a data structure has O(log n) amortized analysis for the T operation, what do we mean by that statement?

a.On average over the entire set of operations on the data structures, operatoin T will take no longer than order log n time.

b.Operaton T will never take less than order log n time.

c.Operation T will take at most order log n time.

d.Operation T will take no longer than order log n time.

2.For the B+-tree below (with the maximum number of children as 5 and the maximum content of a leaf at 5), consider the tree after inserting 60, 61, 62. Select all answers that apply.

a Inserting 61 causes no node splitting

b Inserting 60 can change either the node containing [57,58,59] or the node containing [66,68,69,70]

c Inserting 60 causes no node splitting.

d Inserting 62 causes only one node to split.

e Inserting 62 causes multiple nodes to split.

f After the insertion of all three keys, the tree remains the same height.

g Inserting 61 causes the node to split

3.For the B+-tree below (with L=5 and M=5), consider the tree after deleting 98, 85. Select all answers that are true.

a Deleting 85 causes no node merging or splitting.

b Deleting 98 causes no node merging or splitting.

c Deleting 85 causes the node to become too small.

d Deleting 85 causes node [83,84] and [87,89,90] to merge

e The node [87,92] becomes [92] after its children merge. merge, but this causes no further merging.

4.The text suggests that during deletion, a node might adopt a key from a neighbor. This is sometimes termed "borrowing from a neighbor". What is true of borrowing from a neighbor? (Select all that apply.)

a Borrowing is just an alternative way of handling deletions. Thre is no real savings.

b It is possible that a node needs more keys, but merging with a neighbor would require immediate splitting. Borrowing from a neighbor eliminates the merging and splitting.

c Borrowing from a neighbor requires the keys of parents to be updated.

d Borrowing from a neighbor may eliminate the need to merge, saving time.

818 3538 48 51 5457 72 78 87| 92 2818 4 10 20 6 12 22 26 35|38 28 36 39 301 37 40 32 41148 I51 I54157 66 72178 42149 52 5558 68 73 79 4450 53 56 159 69 741181 46 84 89 93 85 90 95 97 98 14 24 7076 16 818 3538 48 51 5457 72 78 87| 92 2818 4 10 20 6 12 22 26 35|38 28 36 39 301 37 40 32 41148 I51 I54157 66 72178 42149 52 5558 68 73 79 4450 53 56 159 69 741181 46 84 89 93 85 90 95 97 98 14 24 7076 16