CSCI 160: Fall 2017 Final Exam
Sections F17N01-F17N04 (Dr. Wessels)

Question Mark
Remembering to write your name!
[1 mark]
 
1. Write a program: Loops
[9 marks]
 
2. Implementing functions: Pointers
[9 marks]
 
3. Show the output: Recursion
[9 marks]
 
4. Fix a program: File I/O
[9 marks]
 
5. Modify a function: Arrays
[9 marks]
 
6. Write a program II: Command line arguments, null terminated arrays
[9 marks]
 
7. Write a function II: Structs
[9 marks]
 
8. Show the output II: Arrays of structs
[9 marks]
 
9. Explain a concept: Linked lists
[9 marks]
 
Exam Total

[100 marks]

 

Question 1: Write a program [9]

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

The program prompts the user to enter two integers.
It then reads the two numbers and displays all the integer values strictly between the two numbers. For example,

You may assume the user does enter two numbers (you do not need to perform error checking on the input).

SAMPLE SOLUTION
#include <cstdio>

int main()
{
   printf("Please enter two integers\n");
   long num1, num2;
   scanf("%ld", &num1);
   scanf("%ld", &num2);
   long smaller = num1;
   long larger = num2;
   if (num2 < num1) {
      smaller = num2;
      larger = num1;
   }
   long current = smaller + 1;
   while (current < larger) {
      printf("%ld\n", current);
      current++;
   }
}

Question 2: Implementing functions [9]

Write complete versions of the two functions whose prototypes and descriptions are provided below. Be sure to provide appropriate error checking for the pointers used.

(Part a) [3 marks] swap using pointers
     // Given p1 and p2 are pointers to two integer variables,
     //    swaps the values contained in the two variables referenced.
     // For example, assuming x and y are integer variables,
     //    the following call would swap the contents of x and y:
     //       swap(&x, &y);
     void swap(int *p1, int *p2);
SAMPLE SOLUTION
void swap(int *p1, int *p2)
{
   // ensure neither pointer is null
   if (p1 && p2) {
      // exchange the integer contents of the variables pointed at
      int tmp = *p1;
      *p1 = *p2;
      *p2 = tmp;
   }
}

(Part b) [3 marks] printf with pointers
     // This function displays the address contained in pointer p.
     // For example, assuming x is an integer variable,
     //    the following call would display the address of x:
     //       displayAddr(&x);
     void displayAddr(int *p);
SAMPLE SOLUTION
void displayAddr(int *p)
{
   // note it's ok if p is null, will simply display 0 as the address
   printf("%p\n", p);
}

(Part c) [3 marks] dynamic allocation with pointers
     // This function attempts to allocate an array of ints of the size given
     //    by parameter arrSize, and returns the resulting pointer.
     // For example, the following would attempt to allocate an array of 7 ints
     //    and return a pointer to it.
     int* allocate(int arrSize);
SAMPLE SOLUTION
int *allocate(int arrSize)
{
   int *ptr = NULL;
   if (arrSize > 0) {
      ptr = new int[arrSize];
   }
   return ptr;
}

Question 3: Show the output [9]

Given the implementation of the pr function below, show the complete and precise output that would be produced on the screen during execution of the function call below, assuming the call was part of a larger valid program.
      pr(12,2);

void pr(int F, int curr)
{
   if ((F % curr) == 0) {
      printf("%d ", curr);
   }
   if (F <= curr) {
      printf("\n");
   } else {
      pr(F, curr+1);
   }
}

SAMPLE SOLUTION
2 3 4 6 12 

Explanation:
  pr(12, 2) prints  2 (since 12%2 is 0) then calls pr(12,3)
  pr(12, 3) prints  3 (since 12%3 is 0) then calls pr(12,4)
  pr(12, 4) prints  4 (since 12%4 is 0) then calls pr(12,5)
  pr(12, 5) doesn't print (since 12%5 is 2) then calls pr(12,6)
  pr(12, 6) prints  6 (since 12%6 is 0) then calls pr(12,7)
  pr(12, 7) doesn't print (since 12%7 is 5) then calls pr(12,8)
  pr(12, 8) doesn't print (since 12%8 is 4) then calls pr(12,9)
  pr(12, 9) doesn't print (since 12%9 is 3) then calls pr(12,10)
  pr(12,10) doesn't print (since 12%10 is 2) then calls pr(12,11)
  pr(12,11) doesn't print (since 12%11 is 1) then calls pr(12,12)
  pr(12,12) prints 12 (since 12%12 is 0) then prints \n and does NOT make a recursive call

Question 4: Fix a program [9]

The program below is broken. It is supposed to copy the contents of a file named "data" into a file named "results", but omitting all whitespace in the copy.

The table shows the contents of "data" file and what the contents of the "results" file should look like.

"data" filecorrect "results" file
this is the data
   ...
in the file
x
thisisthedata...inthefilex

The broken version of the program, when run, makes the "results" file an exact copy of the "data" file, except the results file has one extra newline at the end.

#include <cstdio>

const char input[] = "data";
const char output[] = "results";

int main()
{
   FILE *fpin, *fpout;
   fpin = fopen(input, "r");
   if (!fpin) {
      printf("Could not open %s\n", input);
      return 0;
   }
   fpout = fopen(output, "w");
   if (!fpout) {
      printf("Could not open %s\n", output);
      fclose(fpin);
      return 0;
   }
   while (!feof(fpin)) {
      char nextC;
      fscanf(fpin, "%c", &nextC);
      fprintf(fpout, "%c", nextC);
   }
   fclose(fpin);
   fclose(fpout);
   return 0;
}
SAMPLE SOLUTION
#include <cstdio>
#include <cctype>

const char input[] = "data";
const char output[] = "results";

int main()
{
   FILE *fpin, *fpout;
   fpin = fopen(input, "r");
   if (!fpin) {
      printf("Could not open %s\n", input);
      return 0;
   }
   fpout = fopen(output, "w");
   if (!fpout) {
      printf("Could not open %s\n", output);
      fclose(fpin);
      return 0;
   }
   while (!feof(fpin)) {
      char nextC;
      fscanf(fpin, "%c", &nextC);
      if (!feof(fpin) && !isspace(nextC)) {
         // EXPLANATION:
         // (i)  if the fscanf finally ran off the end of the file then
         //         it did NOT read a new char, so we should not print
         // (ii) if the character read was a space then we should not print
         fprintf(fpout, "%c", nextC);
      }
   }
   fclose(fpin);
   fclose(fpout);
   return 0;
}

Fix the program. Note that the correct fix(es) involve relatively small changes to the code - it should not be necessary to revise large portions of the code.

Question 5: Modify a function [9]

The function below currently searches an array from positions 0 to End-1 (inclusive), looking for a target value and returning the first position in which the value is found. It returns -1 if the value is not found in the array.

For example, the call shown here would find the first array position from 0 to 13 that contains value 2.5, and return that position (or -1 if not found):
      pos = findWithin(array, 2.5, 14);

int findWithin(double arr[], double target, int End)
{
   for (int i = 0; i < End; i++) {
       if (arr[i] == target) {
          return i;
       }
   }
   return -1;
}

Modify the function so that it takes an additional integer parameter, Start, and returns the LAST position from Start to End (inclusive) where the value is found. (It should still return -1 if the value is not in that section of the array.) The new prototype would thus be:
      int findWithin(double arr[], double target, int Start, int End);

For example, the call below would find the last array position from 3 to 14 that contains value 2.5, and return that position (or -1 if not found):
      pos = findWithin(array, 2.5, 3, 14);

SAMPLE SOLUTION
int findWithin(double arr[], double target, int Start, int End)
{
   // begin at the end and work down, so we find the match
   //    closest to the end,
   // quit when we get to start (instead of 0)
   for (int i = End; i >= Start; i--) {
       if (arr[i] == target) {
          return i;
       }
   }
   return -1;
}

Question 6: Write a program II [9]

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

The program can be run with any number of command line arguments, and when run the program displays each of its command line arguments that does NOT contain any digits.

For example, if the user ran the program using the command
      ./program test 312 6x ab7 Whatever!

then the output from the program would be

   ./program does not contain any digits
   test does not contain any digits
   Whatever! does not contain any digits

[Reminder: the isdigit function from the cctype library tests a character to see if it is a digit or not.]

SAMPLE SOLUTION
#include <cstdio>
#include <cctype>

// containsDigit returns true if str contains 1 or more digits
bool containsDigit(char str[]);

int main(int argc, char *argv[])
{
   // check each argument, print those that don't contain digits
   for (int i = 0; i < argc; i++) {
       if (!containsDigit(argv[i])) {
          printf("%s does not contain digits\n", argv[i]);
       }
   }
}

bool containsDigit(char str[])
{
   // check each position in str,
   //    if we find a digit then immediately quit and return true
   int pos = 0;
   while (str[pos] != '\0') {
      if (isdigit(str[pos])) {
         return true;
      }
      pos++;
   }
   // if we get to the end then it contained no digits, return false
   return false;
}

Question 7: Write a function II [9]

A constant definition and struct definition are given below, along with the prototype and description of a function that uses the struct.

const int MaxStrSize = 256;
struct Contact {
   char name[MaxStrSize];
   char email[MaxStrSize];
};

// the function prompts the user to provide a name and
//     email address for the contact, and fills in the
//     corresponding fields of parameter C
void fillContact(Contact &C);

(Part a) [6 marks] Provide a complete implementation of the function.

You may assume libraries cstring, cstdio, and cctype have been included.
Be sure your function does not overfill the arrays, but you do not need to perform any other error checking on the user input.

SAMPLE SOLUTION
void fillContact(Contact &C)
{
   // use fgets so we can limit the size and accept whitespace,
   // prompt and read the name
   printf("Enter a name\n");
   fgets(C.name, MaxStrSize, stdin);
   // prompt and read the email address
   printf("Enter an email address\n");
   fgets(C.email, MaxStrSize, stdin);
}

(Part b) [3 marks] Suppose the function prototype was this instead:

void fillContact(Contact *C);

Show a simple set of changes to the function implementation that would provide the same behaviour as your answer from part (a).

SAMPLE SOLUTION
void fillContact(Contact *C)
{
   // we need to ensure C is not a null pointer, and since C is a pointer to
   //    a struct we need to use -> instead of . to access the fields
   if (C) {
      printf("Enter a name\n");
      fgets(C->name, MaxStrSize, stdin);
      printf("Enter an email address\n");
      fgets(C->email, MaxStrSize, stdin);
   }
}

Question 8: Show the output II [9]

Show the complete and precise output that would be shown on the screen if the following program were run.

#include <cstdio>

struct Fraction {
   int num, denom;
};

void fill(Fraction F[], int size);
void display(Fraction F[], int first, int last);

int main()
{
   const int NumF = 6;
   Fraction Fracs[NumF];
   fill(Fracs, NumF);
   display(Fracs, 1, 5);
   return 0;
}


void fill(Fraction F[], int size)
{
   int n = 10; int d = 1;
   for (int i = 0; i < size; i++) {
       F[i].num = n;
       F[i].denom = d;
       n = n + 2;
       d++;
   }
}

void display(Fraction F[], int first, int last)
{
   for (int i = first; i <= last; i++) {
       int result = F[i].num / F[i].denom;
       printf("%d/%d is %d\n", F[i].num, F[i].denom, result);
   }
}

SAMPLE SOLUTION
12/2 is 6
14/3 is 4
16/4 is 4
18/5 is 3
20/6 is 3

Explanation:
   fill uses the following values to initialize the array of structs:
      10/1, 12/2, 14/3, 16/4, 18/5, 20/6
   display(1,5) shows all but the first one,
      and for each displays the numerator/denominator and then the result of
      performing the division, but dropping fractions (i.e. integer division)

Question 9: Explain a concept [9]

In your own words, describe the meaning of each of the terms given below, and briefly describe a situation in which it might be used.

(Part a) [3 marks] linked list

(Part b) [3 marks] abstract data type

(Part c) [3 marks] command line argument

SAMPLE SOLUTION

(Part a) [3 marks] linked list
   A linked list is an abstract data structure, used to hold a series
   of data values in a form that can be dynamically resized: adding new
   values into the list or removing old values from the list whenever needed.

   Such a list might be used in situations where the number of values in
   the list is highly variable, such as concert ticket purchase orders,
   or incoming web page requests.)

(Part b) [3 marks] an abstract data type
   An abstract data type is

(Part c) [3 marks] command line argument
   A command line argument is a block of text passed from the user to a program
   as part of the command by which they invoke the program.  For example, in the
   command "mkdir csci160", mkdir would be the program name and csci160 would be
   a command line argument passed to the program.

   Command line arguments are widely used as a means of running the program on
   specific values or with specific options (such as the mkdir example above).

  CSCI 160 Exam Quick Reference Sheet: Sections F15N01-F15N04
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("%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("%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