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.

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.

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.

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)