• CLEARLY PRINT YOUR NAME HERE:

• This exam includes a short C++ quick-reference sheet.
• You have 3 hours to complete the exam (9:00-12:00)
• There are 11 questions on the exam, your best 10 answers will be used.
• Questions are worth 8 marks each, for a total of 80 marks.
• Answer directly on the exam paper, using the backs of pages if extra space is required.
• The exam is closed book, closed notes, no calculators, phones, or other electronic aids of any form may be used during the exam.
• The exam pages are two sided, be sure to check your exam to make sure all 11 questions and the reference sheet are included.

Question	Mark
0. Write a program [8 marks]
1. Nested loops [8 marks]
2. Scope and parameters [8 marks]
3. Writing functions [8 marks]
4. Recursion [8 marks]
5. Arrays and searching [8 marks]
6. Command line args [8 marks]
7. File I/O [8 marks]
8. Structs [8 marks]
9. Dynamic allocation [8 marks]
10. Pointers, structs, and linked lists [8 marks]
Exam Total [80 marks]

Question 0: Write a program [8]

Write a complete and correct C++ program that meets the following specifications:

• The program prompts the user to enter two numbers, and attempts to read the first two user responses.
• If the user entered two numbers, the program displays whichever number was closest to 100, otherwise the program displays the message "Incorrect data entered" and ends.

Sample solution
#include <cstdio>

int main()
{
   const float target = 100;
   printf("Please enter two numbers\n");
   float m, n;
   if (scanf("%g", &m) && scanf("%g", &n)) {
      float diffm = m - target;
      if (diffm < 0) {
         diffm = -diffm;
      }
      float diffn = n - target;
      if (diffn < 0) { 
         diffn = -diffn;
      }
      float answer = m;
      if (diffn < diffm) {
         answer = n;
      }
      printf("Of your two numbers, %g and %g, ", m, n);
      printf("%g is closer to %g\n", answer, target);
   } else {
      printf("Incorrect data entered\n");
   }
}

Question 1: Nested loops [8]

Write the printFactors function following the algorithm below, using ints for all variables. (Assume cmath has been included.)

void printFactors(int n)
// for each integer x from 1 to n (inclusive)
//    limit = sqrt x
//    for each integer f from 1 to limit (inclusive)
//       if f evenly divides x then:
//          d = x / f
//          print a message saying f and d are factors of x

Sample solution
void printFactors(int n)
{
   for (int x = 1; x <= n; x++) {
       int limit = sqrt(x);
       for (int f = 1; f <= limit; f++) {
           if ((x % f) == 0) {
              int d = x / f;
              printf("%d and %d are factors of %d\n", f, d, x);
           }
       }
   }
}

Question 2: Scope and parameters [8]

The program below is a valid (though unusual) C++ program that uses a variety of different variable scopes. Study the program carefully, and show the precise output produced by the program.

#include <cstdio>

const int X = 1;
const int Y = 2;

void swap(int &X, int Y);
int f(int &X);

int main()
{
   int X = 3;
   swap(X, Y);
   printf("main(%d,%d)\n", X, Y);
   int Y = f(Y) * X;
}

void swap(int &X, int Y)
{
   int tmp = Y;
   X = Y;
   X = tmp;
   printf("swap(%d,%d)\n", X, Y);
}

int f(int &X)
{
   X = 4;
   int Y = 1;
   printf("f1(%d,%d)\n", X, Y);
   do {
      int X = Y*6;
      printf("f2(%d,%d)\n", X, Y);
      X--;
      Y++;
   } while (Y < X);
   return X;
}

Sample solution
swap(2,2)
main(2,2)
f1(4,1)
f2(6,1)
f2(12,2)
f2(18,3)

Question 3: Writing functions [8]

Write the two functions prototyped below.

// returns the negated square of x
// e.g. negSquare(3) returns -9
double negSquare(double x);

// alters the first n array values,
// multiplying each by s
void scale(float a[], int n, float s);

Sample solution
double negSquare(double x)
{
   return (- (x * x));
}

void scale(float a[], int n, float s)
{
   for (int i = 0; i < n; i++) {
       a[i] *= s;
   }
}

Question 4: Recursion [8]

Show the six lines of output produced by the following (valid) program:

#include <cstdio>

void mix(char arr[], int left, int right);
void swap(char &x, char &y);

int main()
{
   char arr[6] = "abcde";
   mix(arr, 1, 3);
}

void mix(char arr[], int left, int right)
{
   if (left > right) {
      return;
   } else if (left == right) {
      printf("%s\n", arr);
   } else {
      mix(arr, left+1, right);
      for (int pos = left+1; pos <= right; pos++) {
          if (arr[left] != arr[pos]) {
             swap(arr[left], arr[pos]);
             mix(arr, left+1, right);
             swap(arr[left], arr[pos]);
          }
      }
   }
}

void swap(char &x, char &y)
{
   char tmp = x;
   x = y;
   y = tmp;
}

Sample solution
abcde
abdce
acbde
acdbe
adcbe
adbce

Question 5: Arrays and searching [8]

Write a C++ function that meets the specifications below:

• The function prototype is
  int together(int arr[], int n, int size);
• The function searches the array starting from position 0, looking for a pair of adjacent positions which both contain value n (e.g. n is in positions 6 and 7).
• The function returns the first such position found (6 in the example above), and returns -1 if no such position is found.

Sample solution
int together(int arr[], int n, int size)
{
   for (int pos = 0; pos < (size-1); pos++) {
       if ((arr[pos] == n) && (arr[pos+1] == n)) {
          return pos;
       }
   }
   return -1;
}

Question 6: Command line arguments [8]

Part 1: Write a function that meets the following specifications:

• The function prototype is as follows:
  void embed(char str1[], char str2[], char result[]);
  (The function assumes str1 and str2 are both null-terminated character arrays and that result is large enough for the purposes described below.)
• The function copies str1 into result,
  then concatenates str2 onto the end of that,
  then concatenates str1 onto the end of that.
  E.g. if str1 was "abc" and str2 was "xyz" then the result would be "abcxyzabc".
  (You may assume the cstring library has been included.)

Part 2:Write a main routine that:

• expects two command line arguments (aside from the executable name), and generates an appropriate and informative error message if an incorrect number of arguments is supplied
• if a correct number of arguments is supplied, the program
  i. declares a local character array of size 256 (using a constant),
  ii. calls the embed function on the two arguments (storing the result in the local array),
  iii. displays the result.

Sample solution
void embed(char str1[], char str2[], char result[])
{
   strcpy(result, str1);
   strcat(result, str2);
   strcat(result, str1);
}

int main(int argc, char *argv[])
{
   if (argc != 3) {
      printf("Correct usage is:  %s str1 str2\n", argv[0]);
      return 0;
   }
   const int StrSize = 256;
   char result[StrSize];
   embed(argv[1], argv[2], result);
   printf("combining %s and %s gives %s\n", argv[1], argv[2], result);
}

Question 7: File I/O [8]

Write a function that has a bool return type and takes three parameters: two character arrays (file1, file2), and an integer value (n).

The function copies the first n characters of file1 into file2, with appropriate error checking.

The function returns true if both files opened successfully and all n characters were copied successfully and false otherwise.

Sample solution
bool copyn(char file1[], char file2[], int n)
{
   FILE *fpin;
   FILE *fpout;
   fpin = fopen(file1, "r");
   if (!fpin) {
      printf("Unable to open file %s for reading\n", file1);
      return false;
   }
   fpout = fopen(file2, "w");
   if (!fpout) {
      printf("Unable to open file %s for writing\n", file2);
      fclose(fpin);
      return false;
   }
   int count = 0;
   while ((count < n) && (!feof(fpin))) {
       char curr = fgetc(fpin);
       if (!feof(fpin)) {
          fprintf(fpout, "%c", curr);
          count++;
       }
   }
   fclose(fpin);
   fclose(fpout);
   if (count == n) {
      return true;
   } else {
      printf("Only able to copy %d of %d characters\n", count, n);
      return false;
   }
}

Question 8: Structs [8]

Given the struct definition and the two function prototypes below, complete the implementation of the functions.

// the maximum number of values in a data set
const int MaxVals = 500;

// a data set is a collection of up to 500 values,
// numVals records how many are actually stored at the moment
struct DataSet {
   double values[MaxVals];
   int numVals;
};

// calculate and return the average of the values in data set d
//    (i.e. the sum of the values / the number of values)
double average(DataSet d);

// calculate and return the average of all the data sets in array S
//    (the sum of the data set averages / the number of data sets)
double overallAverage(DataSet S[], int numSets);

Sample solution
double average(DataSet d)
{
    double sum = 0;
    for (int i = 0; i < d.numVals; i++) {
        sum += d.values[i];
    }
    return (sum / d.numVals);
}

double overallAverage(DataSet S[], int numSets)
{
   double grandTotal = 0;
   for (int i = 0; i < numSets; i++) {
       grandTotal += average(S[i]);
   }
   return (grandTotal/numSets);
}

Question 9: Dynamic allocation [8]

Suppose that someone else has written a function processarray with the following specifcations:

// the function does something with the contents of the array of floats
void processarray(float arr[], int size);

• declares a float pointer variable
• gets the user to specify how many values they intend to enter
• uses the 'new' operator to dynamically allocate an array of the desired number of floats, and uses the declared pointer variable to keep track of where it is
• if the call to new succeeded then the program passes the pointer variable and array size to function processarray and afterwards deletes the array
• if the call to new failed then the program displays an appropriate and informative error message

Sample solution
int main()
{
   float *fptr;
   int n;
   printf("How many values would you like to enter?\n");
   if (scanf("%d", &n)) {
      fptr = new float[n];
      if (!fptr) {
         printf("Unable to allocate enough space for %d floats\n", n);
      } else {
         processarray(fptr, n);
         delete [] fptr;
      }
   } else {
     printf("That was not a number\n");
   }
}

Question 10: Pointers, structs, and linked lists [8]

Part I: Given the struct definition and the function prototype below, complete the implementation of the function.

// stores a time as three integer values, hour (1-12), minutes (0-59), seconds (0-59)
struct time {
   int hour, minute, second;
};

// displays a time in the format hh:mm:ss
// e.g. 12:05:15
void display(time *tptr);

Part II: Given the struct definition and function prototype below, complete the implementation of the function. Be sure to include all appropriate null-pointer checking.

// Fraction represents an individual fraction (numerator/denominator)
//    that can be held as one element of a doubly-linked list
struct Fraction {
   long numerator, denominator;  // the Fraction data fields
   Fraction *next; // pointer to the next Fraction in the list (i.e. closer to the back)
   Fraction *prev; // pointer to the next Fraction in the list (i.e. closer to the front)
};

// given pointers to the front and back of the list, and a pointer to the
//    fraction, f, to be inserted,
// inserts the supplied fraction supplied fraction at the back of the list,
//    returning true if successful, false otherwise
bool insertF(Fraction* &front, Fraction* &back, Fraction* f);

Sample solution
void display(time *tptr)
{
   printf("%02d:%02d:%02d\n", tptr->hour, tptr->minute, tptr->second);
}

bool insert(Fraction* &front, Fraction* &back, Fraction* f)
{
   if (!f) {
      return false;
   }
   if (front == NULL) {
      front = f;
      back = f;
      return true;
   }
   back->next = f;
   f->prev = back;
   back = f;
   return true;
}

  CSCI 160 Exam Quick Reference Sheet: Sections F16N01-F16N04

Comments:    Single line //
          or Multi-line  /* ....
                            .... */

C++ operators
=============
Arithmetic operators:     +   -   *   /   %   ++  --
Assignment operators:  =  +=  -=  *=  /=  %=
Boolean operators:     &&  ||  !  ==  !=  <=  >=  <  >

Data Types
=======================================================
Data        Keywords             Literal Examples    Special values
integers:   short, int, long     3, -200, 0          INT_MAX, INT_MIN  (climits library)
reals:      float, double        3.14, -0.0003       FLT_MAX, FLT_MIN  (cfloat  library)
character:  char                 'x'                 \'  \"  \\  \t \n  \0
boolean:    bool                 true, false

Sample variable declarations (with/without initialization)
==========================================================
int    i;       int    i = 3;
char   c;       char c = 'Q';   char c = '\n';
bool   b;       bool b = true;
long arr[5];    long arr[5] = { 0, 0, 0, 0, 0 };   // array assignment only valid
char str[10];   char str[] = "some text";          //    at point of declaration

Sample constant declarations
============================
const double Pi = 3.1415;
const char[] ErrMsg = "Error: something terrible happened!\n";

Sample enumerated type definitions
==================================
enum Weekdays { Sun, Mon, Tue, Wed, Thu, Fri, Sat };
enum Commands { Quit = 'Q', Continue = 'C', Print = 'P' };

Sample input with scanf, fgets, and getc (cstdio library)
=========================================================
// scanf returns a count of the number of variables "filled"
scanf("%c", &x);  // read a character into char variable x
scanf("%d", &i);  // read an integer into int variable i
scanf("%ld", &n);  // read an integer into long variable n
scanf("%g", &f);  // read a real number into float variable f
scanf("%s", &a);  // read text into variable a (char[])
scanf("%*s");     // read and discard the next word of input
scanf("%[abc]", &x); // read an a, b, or c into variable x
scanf("%*[ \t\n]%c", &x); // skip tabs, spaces, and newlines and read next char into x
scanf("%4d", &i); // read a maxium of 4 digits into int variable i
fgets(arr, 100, stdin); // read the rest of the line (up to 100 chars max) into the char array
x = getc(stdin);  // read a single character into char variable x
ungetc(c, stdin); // take char c and push it into the input buffer

Sample output with printf (cstdio library)
==========================================
// printf returns a count of the number of characters printed
printf("%c", x);  // print the contents of  char variable c
printf("%d", i);  // print the contents of int variable i
printf("%ld", n);  // print the contents of long variable n
printf("%g", f);  // print the contents of float variable f
  // (%f gives fixed point, %e gives exponential notation, %g can do either)
printf("%5.2g, f); // print the contents of f with width 5, 2 decimal places
printf("%s", a);  // print the contents of character array a

Some useful library functions and constants
===========================================
cctype                 cfloat                   cmath
------                 ------                   -----
bool isalpha(char)     FLT_MIN, FLT_MAX         double ceil(double)
bool isalnum(char)     DBL_MIN, DBL_MAX         double floor(double)
bool isdigit(char)                              double fabs(double)
bool islower(char)     climits                  double log(double)
bool isupper(char)     -------                  double pow(double, double)
bool ispunct(char)     CHAR_MIN, CHAR_MAX       double cos(double)
bool isspace(char)     SHORT_MIN, SHORT_MAX     // also acos, sin, asin, tan, atan
char tolower(char)     INT_MIN, INT_MAX         double sqrt(double)
char toupper(char)     LONG_MIN, LONG_MAX

cstring                            cstdlib
-------                            -------
char* strcat(char*, char*)         int abs(int)
char* strncat(char*, char*, int)   int atoi(char*)
char* strcpy(char*, char*)         float atof(char*)
char* strncpy(char*, char*, int)   void srand(time(NULL)) // needs ctime lib
int   strcmp(char*, char*)         int rand(int)
int   strncmp(char*, char*, int)
int   strlen(char*)




Sample control structures
=========================
if (expr) {                  // works on short, int, long,      for (x = 1; x < 9; x++) {
   .......                   //    char, or enum values             ....
} else if (expr) {           switch (expr) {                    }
   ........                     case value1:
} else {                            .....                       while (x < 9) {
   ........                         break;                          ....
}                               case value2:                        x++;
                                    .....                       }
// is X between 3 and 9?            break;
if ((3 < X) && (X < 9)) {       default:                        do {
   // yes it is                     .....                           ....
} else {                            break;                          x++;
   // no it isn't            };                                 } while (x < 9);
}
         Sample function prototypes and implementations         Sample calls
         ==============================================         ============
void swap(int &a, int &b);      float calc(int x, float f)      int main()
......                          .....                           {
void swap(int &a, int &b)       float calc(int x, float f)         int i = 1;
{                               {                                  int j = 2;
    int temp = a;                  float result = x * f;           swap(i, j);
    a = b;                         return result;                  float f = calc(i, 2.5);
    b = temp;                   }                                  int array[20];
}                                                                  initArray(array, 20);
                                                                }
void initArray(int arr[], int size)
{
   for (int i = 0; i < size; i++
       arr[i] = 0;
}

Pointer examples
================
int i;       // an integer variable i
int *iPtr;   // iPtr can point at integers in memory
iPtr = &i;   // iPtr now points at variable i (& takes the address of i)
(*iPtr) = 3; // store 3 whereever iPtr points in memory

Sample function prototype with a pointer passed by reference
============================================================
void doSomething(int* &ptr);

Dynamic memory allocation and deallocation
==========================================
using new/delete            using malloc/free
----------------            -----------------
int *i = new int;           int *i = (int*)malloc(sizeof(int);        // alloc new int
delete i;                   free i;                                   // free the int
float *f = new float[10];   float *f = (float*)malloc(sizeof(float)); // alloc new arr of floats
delete [] f;                free f;                                   // free the array
// remember to test for NULL after any call to new or malloc

Sample struct definition and use
===================================
struct Info {                         Info i;
   char initials[2];                  i.id = 0;
   int id;                            i.value = -34.216;
   float value;                       i.initials[0] = 'D';
};

The C++ string class (using the  library)
====================
std::string str; // declare a string variable str
str = "blah blah blah"; // assign text to a string
printf("%s", str.c_str()); // print the string contents
str[3] = 'x'; // change the fourth character in the string to x