MTH 4300 Midterm 1 Practice Questions

Tracing

1. What is the output of the following program? Trace through each statement, tracking x, y, and z after every change — including what happens inside transform.

   #include <iostream>
   
   void transform(int a, int& b, int* c) {
       a *= 2;
       b += a;
       *c = b - a;
       std::cout << a << " " << b << " " << *c << std::endl;
   }
   
   int main() {
       int x = 3, y = 5, z = 0;
       std::cout << x << " " << y << " " << z << std::endl;
   
       transform(x, y, &z);
   
       std::cout << x << " " << y << " " << z << std::endl;
   
       int* p = &y;
       *p += z;
       x = *p - z;
       std::cout << x << " " << y << " " << z << std::endl;
   
       return 0;
   }

2. What is the output of the following program? For each recursive call to compress, show the value of lo, hi, mid, and the return value. Also show the final state of nums.

   #include <iostream>
   #include <vector>
   
   int compress(std::vector<int>& v, int lo, int hi) {
       if (lo == hi) return v[lo];
       int mid  = (lo + hi) / 2;
       int left  = compress(v, lo, mid);
       int right = compress(v, mid + 1, hi);
       v[mid] = left + right;
       std::cout << "v[" << mid << "] = " << v[mid] << std::endl;
       return v[mid];
   }
   
   int main() {
       std::vector<int> nums = {1, 2, 3, 4, 5};
       int result = compress(nums, 0, 4);
       std::cout << "result: " << result << std::endl;
       std::cout << "nums: ";
       for (int x : nums) std::cout << x << " ";
       std::cout << std::endl;
       return 0;
   }

3. What is the output of the following program? Trace through each statement, tracking the values of a, b, c, and ptr — especially what ptr->next = &c and the subsequent pointer operations do.

   #include <iostream>
   
   struct Node {
       int val;
       Node* next;
   };
   
   void printList(Node* head) {
       while (head != nullptr) {
           std::cout << head->val;
           if (head->next != nullptr) std::cout << " -> ";
           head = head->next;
       }
       std::cout << std::endl;
   }
   
   int main() {
       Node a{1, nullptr};
       Node b{2, nullptr};
       Node c{3, nullptr};
   
       a.next = &b;
       b.next = &c;
   
       Node* ptr = &a;
       std::cout << ptr->val << std::endl;
   
       ptr->next = &c;
       ptr = ptr->next;
       ptr->val *= 2;
   
       printList(&a);
       std::cout << b.val << std::endl;
   
       return 0;
   }

4. What is the output of the following program? Trace through the sort, the find_if, the count_if, and the accumulate calls step by step.

   #include <iostream>
   #include <vector>
   #include <algorithm>
   #include <numeric>
   
   int main() {
       std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
   
       int threshold = 4;
       std::sort(v.begin(), v.end());
   
       auto it = std::find_if(v.begin(), v.end(), [threshold](int x) {
           return x >= threshold;
       });
   
       if (it != v.end()) {
           std::cout << "first >= " << threshold << ": " << *it << std::endl;
           std::cout << "index: " << (it - v.begin()) << std::endl;
       }
   
       int count = std::count_if(v.begin(), v.end(), [](int x) {
           return x % 2 == 0;
       });
       std::cout << "evens: " << count << std::endl;
   
       int sum = std::accumulate(v.begin(), it, 0);
       std::cout << "sum before threshold: " << sum << std::endl;
   
       return 0;
   }

Debugging

1. The program below is supposed to create an array filled with a given value, reverse it in-place, print it, and free the memory. It contains 4 bugs. For each one, state the line, explain the problem, and write the fix.

   #include <iostream>
   #include <cstddef>
   
   double* makeArray(std::size_t n, double fill) {
       double* arr = new double(n);
       for (std::size_t i = 0; i <= n; ++i) {
           arr[i] = fill;
       }
       return arr;
   }
   
   void reverseArray(double* arr, std::size_t n) {
       for (std::size_t i = 0; i < n / 2; ++i) {
           double tmp = arr[i];
           arr[i]     = arr[n - i];
           arr[n - i] = tmp;
       }
   }
   
   int main() {
       double* data = makeArray(4, 1.5);
       reverseArray(data, 4);
       for (std::size_t i = 0; i < 4; ++i) {
           std::cout << data[i] << " ";
       }
       std::cout << std::endl;
       delete data;
       return 0;
   }

2. The program below is supposed to count how many words in a list are palindromes. It contains 3 bugs. For each one, state the line, explain the problem, and write the fix.

   #include <iostream>
   #include <string>
   #include <vector>
   
   bool isPalindrome(const std::string& s, int lo, int hi) {
       if (lo >= hi) return false;
       if (s[lo] != s[hi]) return false;
       return isPalindrome(s, lo + 1, hi);
   }
   
   int countPalindromes(const std::vector<std::string>& words) {
       int count = 0;
       for (const std::string& w : words) {
           if (isPalindrome(w, 0, (int)w.size())) {
               ++count;
           }
       }
       return count;
   }
   
   int main() {
       std::vector<std::string> words = {"racecar", "hello", "level", "world", "madam"};
       std::cout << countPalindromes(words) << std::endl;  // expected: 3
       return 0;
   }

Implementation

1. Given the following function signature:

   int digitSum(int n)
   
   // digitSum(0)    → 0
   // digitSum(7)    → 7
   // digitSum(123)  → 6
   // digitSum(9009) → 18

   Returns the sum of all decimal digits in n. Assume n >= 0. No loops allowed.

2. Given the following function signature:

   std::vector<int> mergeSorted(const std::vector<int>& a, const std::vector<int>& b)
   
   // mergeSorted({1, 3, 5}, {2, 4, 6}) → {1, 2, 3, 4, 5, 6}
   // mergeSorted({1, 2, 3}, {})        → {1, 2, 3}
   // mergeSorted({}, {4, 5})           → {4, 5}
   // mergeSorted({1, 1}, {1, 2})       → {1, 1, 1, 2}

   Both a and b are already sorted ascending. Returns a new sorted vector containing all elements from both. No std::sort or std::merge allowed.

3. Given the following function signature:

   bool hasDuplicate(const std::vector<int>& v)
   
   // hasDuplicate({1, 2, 3, 1}) → true
   // hasDuplicate({1, 2, 3})    → false
   // hasDuplicate({})           → false

   Returns true if any value appears more than once. No sorting. No std::set, std::unordered_set, or similar containers. O(n²) is acceptable.