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.

   Solution:

   a. A recursive solution::

        int sum(Node* p) {
            if (p == nullptr) {
                return 0;
            } else {
                return p->val + sum(p->next);
            }
        }

        int sum() {
            return sum(H);
        }

   b. An iterative solution::

        int sum() {
            Node* p = H;
            int result = 0;
            while (p != nullptr) {
                result += p->val;
                p = p->next;
            }
            return result;
        }
     
#. 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.

   Solution::

        // iterative solution
        bool points_to_node1() {
            Node* q = H;
            while (q != nullptr) {
                if (p == q) {
                    return true;
                }
                q = q->next;
            }
            return false;
        }

        // recursive solution: call points_to_node2(H)
        bool points_to_node2(Node* begin) {
            if (begin == nullptr) {
                return false;
            } else if (p == begin) {
                return true;
            } else {
                return points_to_node2(begin->next);
            }
        }

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

   Solution::

       // a recursive solution
       bool equals1(Node* p, Node* q) {
            if (p == nullptr && q == nullptr) {  // both empty?
                return true;
            } else if (p == nullptr || q == nullptr) {  // only one empty?
                return false;
            } else {  // both non-empty?
                if (p->val == q->val) {
                    return equals1(p->next, q->next);
                } else {
                    return false;
                }
            }
       }

       // an interative solution
       bool equals2() {
            Node* p = G;
            Node* q = H;

            while (p != nullptr && q != nullptr) {
                if (p->val == q->val) {
                    p = p->next;
                    q = q->next;
                } else {
                    return false;
                }
            }
            // invariant:  !(p != nullptr && q != nullptr)
            //           = p == nullptr || q == nullptr
            return p == q;
       }


#. 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)

   Solution::

      // Pre: v.size() == w.size()
      // Post: returns true iff v[begin] == w[begin], 
      //       v[begin + 1] == w[begin + 1], ..., v[v.size() - 1] == w[w.size() - 1]
      bool equals(const vector<int>& v, const vector<int>& w, int begin) {
          if (begin >= v.size()) {
              return true;
          } else if (v[begin] != w[begin]) {
              return false;
          } else {
              return equals(v, w, begin + 1);
          }
      }

      // 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) {
          if (v.size() != w.size()) {
              return false;
          } else {
              return equals(v, w, 0);
          }
      }