CSCI 103L - Fall 2024 Introduction to Programming

Disclaimer. This practice final exam resembles the actual final exam in general composition and length. However, it will not cover the exact same set of topics. You should look at the final exam information page and see the list of topics that could come up. We recommend you set aside 2 hours and try to practice this exam in a realistic setting without your computer.

Resist the urge to look up the answers until you’ve really tried it once.

Q1

(Select one answer.) C++ templates allow:

• The same generic code to operate on different variables/arguments
• The same generic code to operate on different types of data
• Code skeletons to be easily distributed
• Users to re-write their code for different implementation options

Q2

(Select all correct answers.) Constructors:

• Are called when the instance goes out of scope or is de-allocated
• Can be used to set data members to a known initial value/state.
• Can be overloaded (i.e. multiple constructors with different argument lists)
• Are called automatically only when the instance is allocated dynamically with ‘new’ and not when the instance is declared statically as a local variable

Q3

For each of the two data types below, and each of the six properties listed, circle the correct answer (True or False).

Q4

(a) Suppose we have a program that takes an N-byte file as input. We measure its performance and find that it takes 20 seconds when N is 20000, 2 minutes when N is 50000, and 8 minutes when N is 100000. What is the most likely order of growth of this program’s running time?

choose one:     O(log N)   O(N)   O(N log N)   O($N^2$)   O($N^3$)   O($2^N$)

(b) Estimate the approximate running time of this program when N is 1 million (1000000). You can leave your answer in either minutes or seconds.

(c) Describe the order of growth of the running time of the following code fragment.

for (int i=0; i<N; i++)
  sum += v[i];
for (int i=N-1; i>=0; i--)
  sum -= v[i];

choose one:    O(log N)   O(N)   O(N log N)   O($N^2$)   O($N^3$)   O($2^N$)

(d) Describe the order of growth of the running time of the following code fragment.

for (int i=0; i<N; i++) {
   for (int j=0; j<2*N; j++) {
      if (i==j) {
         for (int k=0; k<N; k++) {
            cout << i << " " < j << " " << k << endl;
         }
      }
   }
}

choose one:     O(log N)   O(N)   O(N log N)   O($N^2$)   O($N^3$)   O($2^N$)

Q5

Consider the following recursive function.

int g(int n) {
   if (n % 2 == 0) return n/10;
   int tmp = g(n/10);
   return g(tmp);
}

(a) What is g(2469)?

(b) Draw the recursive call tree that occurs when we evaluate g(3122013). Show the return value of each recursive call on the tree.

Q6

Consider the following program:

void mystery(int n) {
   cout << n << endl;
   if (n > 0) {
      mystery(n/2); // integer division
      mystery(n/4); // integer division
   }
}
int main() {
   mystery(4);
   return 0;
}

(a) Draw the recursive call tree that occurs when we run this program.

(b) What is the output of this program?

Q7

Consider the following program:

string x = "";
for (int i=0; i<3; i++) {
   ostringstream oss;
   oss << x << i << x;
   x = oss.str();
   cout << x << endl;
}

What are the 3 lines of output that this program produces?

Q8

Suppose we are creating a Point class to represent a point in two-dimensional Euclidean space. It should support the operations shown in the following example code:

// operation 1. a constructor with given x and y coordinates
Point p(1.5, 2.0);

// operation 2. a function to get a string representation, e.g. "(1.5, 2)" in this case
cout << p.as_string() << endl;

// operation 3. a function to get the distance to another point, e.g. 2.5 in this case
Point q(3.0, 4.0);
cout << p.distance_to(q) << endl;

// operation 4. a function to transform the point by swapping its coordinates
p.swap_coordinates();
cout << p.as_string() << endl; // now gives "(2, 1.5)"

Fill in the following header file for this class. You do not have to actually implement the functions (there’s no need to write the .cpp file). However, you should include appropriate data members.

#ifndef POINT_H
#define POINT_H

#include <string>
using namespace std;

class Point {
 // your code here


public:
   Point(double x, double y); // constructor
   string as_string(); // get text representation
   double distance_to(Point other);
   void swap_coordinates();
private:
   double x;
   doubly y;


};
#endif

Q9

Suppose we have a singly-linked list with a tail and head pointer, using the following struct and class.

struct Node {
   Node* next;
   int val;
};
class List {
 private:
   Node* head;
   Node* tail;
 public:
   // not shown
};

Suppose furthermore that the following List has been created, containing 3, 9, 6 in that order.

(a) Suppose we want to move the element at the start of the list to the end of the list. (So the new list will be 9, 6, 3.) By drawing on the diagram, show which pointers would change by crossing them out, and write in what their new values should be just above or below. You should not create/destroy any Nodes, nor change any “val.”

(b) Write code to complete a member function that will move the element at the start of any list to the end of the list. If the list is empty, it should do nothing.

Hint: you definitely need a special case for an empty list. But you might not need any other special cases. Write the code for the general case first and review it to see if it works for a length-1 list.

void List::move_last_to_first() {
    // your code here

   // many other solutions are possible
   if (head == NULL) // empty list
      return;
   tail->next = head;
   tail = tail->next;
   head = head->next;
   tail->next = NULL;


}

Q10

In this exercise you will create a program that reads any number of integers from a text file specified as a command-line argument, and then prints them in reverse order, one per line.

The program is partially completed for you. However, for several lines we list two possibilities. Select the correct possibility from each pair by circling it.

    1 : int main(int argc, char* argv) {
    2A:    vector<int> v;
OR  2B:    vector<int> v();
    3A:    ifstream in(argv[0]);
OR  3B:    ifstream in(argv[1]);
    4 :    int x;
    5 :    while (true) {
    6A:       in >> x;
OR  6B:       x << in;
    7A:       if (in.fail()) {
OR  7B:       if (in) {
    8 :          for (int i=signed(v.size())-1; i>=0; i--) {
    9A:             cout << v[i] << endl;
OR  9B:             cout << v.back() << endl;
   10 :          }
   11 :          return 0;
   12 :       }
   13A:       v.push_back(x);
OR 13B:       v.push_front(x);
   14 :    }
   15 : }

Q11

Write a function get_even that takes an input int arr[] and its length int n and returns a dynamically-allocated int array consisting of just the even integers it contains. For example,

int a[] = {2, 8, 9, 6, 3, 1, 0};
int* b = get_even(a, 7); // b is of length 4 and contains 2, 8, 6, 0

You do not have to worry about how the user will delete the dynamically-allocated memory or know its size.

int* get_even(int arr[], int n) {
   // need to count first
   int result_size=0;
   for (int i=0; i<n; i++)
      if (arr[i]%2==0)
         result_size += 1;

   // allocate and copy
   int* result = new int[result_size];
   int pos = 0; // position for next copy
   for (int i=0; i<n; i++)
      if (arr[i]%2==0) {
         result[pos] = arr[i];
         pos++;
      }
   return result;
}

Q12

Define a class Fibonacci that supports the following member functions:

• a constructor that takes no parameters, and initializes the object so that it is ready to produce the Fibonacci sequence
• a member function int get_next() that returns the next number in the Fibonacci sequence, with the first two numbers being 1, and every other number being the sum of the two previous

This is an example test program and what it should produce.

Fibonacci f; // create a new instance
cout << f.get_next() << endl; // prints 1
cout << f.get_next() << endl; // prints 1 again
cout << f.get_next() << endl; // prints 2
cout << f.get_next() << endl; // prints 3

Fill in the following parts:

// in fibonacci.h
class Fibonacci {
   public:
      Fibonacci();
      int get_next();
   private:
      // add some code here

      // other solutions are possible!
      int previous;
      int next;



};

// in fibonacci.cpp
Fibonacci::Fibonacci() {
   // add some code here

   // other solutions are possible!
   previous = 0; // set to zero so that second number is 0+1
   next = 1;

}

// define get_next here, including its header:

int Fibonacci::get_next() {
   // other solutions are possible!
   int result = next;
   int newNext = previous + next;
   previous = next;
   next = newNext;
   return result;
}

Q13

Assume a simplified version of football where teams score touchdowns (7 points), field goals (3 points), and safeties (2 points). Assume a team has scored a certain number of times (say, 10) but you don’t know what mix of field goals, touchdowns, or safeties. Write a function that prints all the possible total scores of that team. You cannot use loops and therefore must use recursion; you may define one or more helper functions. For example, if all ten scores were touchdowns the score would be 70. If all ten were field goals the score would be 30. If 5 were touchdowns and 5 were safeties the score would be 45. So your program should print out a list of numbers including 70, 30, and 45. You don’t need to print in sorted order or remove duplicates.

void print_all_possibilities(int times_scored) { // e.g., call print_all_possibilities(10)
  // your code here

// solution 1: mock loops
   helper1(times_scored, 0);


}

// define additional function(s) here
// you may assume their prototypes were defined at the top of the file

// solution 1: mock loops
void helper1(int times_scored, int touchdowns) {
   helper2(times_scored, touchdowns, 0); // try this many touchdowns
   if (touchdowns < times_scored)
      helper1(times_scored, touchdowns+1); // try more touchdowns
}

void helper2(int times_scored, int touchdowns, int fieldgoals) {
   // try this many fieldgoals
   int safeties = times_scored - touchdowns - fieldgoals;
   cout << touchdowns*7 + fieldgoals*3 + safeties*2 << endl;
   if (touchdowns + fieldgoals < times_scored)
      helper2(times_scored, touchdowns, fieldgoals+1); // try more fieldgoals
}



// solution 2: go through all 3^(times_scored) many sequences
void print_all_possibilities(int times_scored) { // e.g., call print_all_possibilities(10)
   helper(times_scored, 0);
}
void helper(int scores_left, int point_sum) {
   if (scores_left == 0) // base case
      cout << point_sum << endl;
   else {
      helper(scores_left-1, point_sum+7); // this is a touchdown
      helper(scores_left-1, point_sum+3); // this is a fieldgoal
      helper(scores_left-1, point_sum+2); // this is a safety
   }
}