CMPT 225 Sample Midterm Questions

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

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

1. 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:

   1. Using recursion (and no loops). Use a helper function if a necessary.
   2. 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:

   1. A recursive solution:

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

   2. An iterative solution:

      int sum() {
          Node* p = H;
          int result = 0;
          while (p != nullptr) {
              result += p->val;
              p = p->next;
          }
          return result;
      }
      

2. 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);
       }
   }
   

3. 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;
   }
   

4. 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);
       }
   }