1. Show the list configuration resulting from each series of list operations using the List ADT of Figure 4.1. Assume that lists L1 and L2 are empty at the beginning of each series. Show where the current position is in the list.

• L1.append(10);
• L1.append(20);
• L1.append(15);
• L2.append(10);
• L2.append(20);
• L2.append(15);
• L2.moveToStart();
• L2.insert(39);
• L2.next();
• L2.insert(12);

2. Show the steps of the following operations on a stack S of Integers graphically. Assume S is empty initially.

s.push(5);
s.push(3);
s.push(7);
s.pop();
s.push(8);
s.pop();
s.pop();
s.push(10);
s.pop();

3. Show graphically the resulting BST trees after inserting the following same set of numbers in different orders. To find the element 5, how many comparisons would you need for each tree structure? Which one needs the least number of comparisons and which one the most? What conclusion can you make about the searching on BST? Namely, when would the searching time for certain element be the best in the worst cases?

1) {9,6,5,4,7,3,8,1,2}
2) {1,2,3,4,5,6,7,8,9}
3) {9,8,7,6,5,4,3,2,1}
4) {5,9,4,8,3,7,2,6,1}

4. Given the following max heap H, show graphically the results of the following operations on H. Use the same following start state when you perform each operation. (Will put in attached document)

1) H.removeMax();
2) H.insert(15);
3) H.remove(4);

Attachment:- Question 4 max heap H.docx