Name:________________________________________

1. (1 pt) What is the worst-case time complexity to insert a node at the end of a singly-linked list that has no "last" pointer? Let n be the number of nodes in the list.
   
   
   
   
   
2. (1 pt) What is the worst-case time complexity to delete a node from the end of a singly-linked list that has a "last" pointer? Let n be the number of nodes in the list.
   
   
   
   
   
3. (2 pts) What are the two rules for writing a recursive program that is guaranteed to halt?
   
   
   
   
   
4. (1 pt) Consider the grammar for arithmetic expressions discussed in lecture:

   E -> T + T | T - T | T
   T -> F * F | F / F | F
   F -> ( E ) | letter | digit
   

   Draw the derivation tree for the arithmetic expression

   a * ( ( b + c ) - 7 )