CMPT 225 Sample Midterm Questions
=================================

In the following questions, assume ``Node`` is defined as follows::

    struct Node {
        int val;
        Node* next;
    }; 

#. Suppose ``H`` is of type ``Node*`` and points to the first node of a singly-
   linked list that has already been created.

   Write a function that returns the sum of all the elements on the list. Do
   it in two different ways:

   a. Using recursion (and no loops). Use a helper function if a necessary.

   b. Without using recursion. 

   Write your answers in C++. Note that the question has not precisely defined
   the function headers, so you will need to write them.

     
#. Suppose ``H`` is of type ``Node*`` and points to the first node of a 
   non-empty singly-linked list that has already been created. Write a 
   function that takes a ``Node*`` called ``p`` as input, and returns 
   ``true`` if ``p`` points to a node in the list, and ``false`` otherwise.

   Give both a recursive and non-recursive solution.


#. Suppose ``G`` and ``H`` are both of type ``Node*`` and both point to the 
   first nodes of *different* singly-linked lists that have already been 
   created. Write a function called ``equals`` that returns ``true`` if 
   both lists have exactly the same values in the order, and ``false``
   otherwise.

   Give both a recursive and non-recursive solution.


#. Implement the following function using recursion and no loops. While 
   you cannot use any helper functions from the C++ standard library or 
   course header file, you can write your own helper function if 
   necessary::

     // Pre:
     // Post: Returns true if v and w contain the same elements
     //       in the same order, and false otherwise.
     // Examples:
     //       equals({1, 3, 2}, {1, 3, 2}) returns true
     //       equals({}, {}) returns true
     //       equals({1, 3, 2}, {3, 1, 2}) returns false
     bool equals(const vector<int>& v, const vector<int>& w)