1. (Multiple choice) In a binary tree with 100 leaves in which every non-leaf node has two children, the total number of nodes is

(i) 200 (ii) 201 (iii) 199 (iv) none of the given choices

2. Consider a linked list that has the following operations defined on it:

Operation	Description	Cost
AddLast(x)	Adds the element x to the end of the list	1
RemoveFourths()	Removes every fourth element in the list i.e. removes the first, fifth, ninth, etc., elements of the list.	Equals the number of elements in the list

1. Assume we perform n operations on the list. What is the worst case (asymptotic) run time of a call to RemoveFourths()?
2. Using the accounting method, compute the amortized cost per operation for a sequence of these two operations (give the amounts that you will charge AddLast() and RemoveF ourths(), and show how you will use these charges to pay for the actual costs of these operations). Keep your answer brief.