1. Write a closed form expression for the number of times that the line "I'm here" will be displayed on the screen when the following code fragment has run. for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = j; k < N; k++) cout << "I'm here. "; 2. Write a post order traversal of a general tree. 3. Dene the internal path length of a tree. 4. If a user denes a one-parameter constructor for a class C but no other constructors, what does this code create: C objects[100]; 5. Write a function in C++ that removes a node from a binary search tree, given a pointer to its root and the element to be deleted. 6. What is the worst case time to insert an element into a BST with n nodes. 7. True or False? If a function's running time is O(n3) it can never run in strictly linear time. 8. True or False? Let c be a constant > 1. If f(n) is dened as c raised to the nth power andg(n) is dened as c raised to the (n + 1)st power, then f(n) = o(g(n)): 9. Draw a binary search tree of height no greater than 3 containing the keys 1 2 3 4 5 6 7 8 9 10 11 12. 10. Write a closed form expression of the running time of the function below as a function of N: int foo (int N) { if (N <= 0) return 1; else return foo(N/2) + foo(N/2) + N; } 11. Given an AVL tree in a diagram, insert a specic element into the tree and rotate as necessary to rebalance the tree. You can make up examples.

1. Write a closed form expression for the number of times that the ne "I'm here" will be displayed on the screen when the following code fragment has run for (int i 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = j; k < N; k++) cout << "I'm here. n"; 2. Write a post order traversal of a general tree 3. Define the internal path length of a tree. 4. If a user defines a one-parameter constructor for a class C but no other constructors, what does this code create C objects [100] 5. Write a function in C++ that removes a node from a binary search tree, given a pointer to its root and the element to be deleted 6. What is the worst case time to insert an element into a BST with n nodes 7. True or False? If a function's running time is O(n3) t can never run in strictly linear time. 8. True or False? Let c be a constant >1. If f(n) is defined as c raised to the nth power andg(n) is defined as c raised to the (n + 1)st power, then f(n) = o(g(n)) 9. Draw a binary search tree of height no greater than 3 containing the keys 1 234567 89 101 12 10. Write a closed form expression of the running time of the function below as a function of N: int foo (int N) if (N <= 0) return 1; else return foo (N/2)+foo(N/2)N; 11. Given an AVL tree in a diagram, insert a specific element into the tree and rotate as necessary to rebalance the tree. You can make up examples