Feb 4, 2004

**Name:**________________________________________

- (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.

- (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.

- (2 pts) What are the two rules for writing a recursive
program that is guaranteed to halt?

- (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 expressiona * ( ( b + c ) - 7 )