CSCI 160: Fall 2016 Midterm 2
With Sample Solutions (Dr. Wessels)

Question Mark
1. Write a program
[7 marks]
 
2. Write a function
[7 marks]
 
3. Modify a function
[7 marks]
 
4. Show the output
[7 marks]
 
5. Implement an algorithm
[7 marks]
 
Exam Total

[35 marks]

 

Question 1: Write a program [7]

Write a complete and correct C++ program as described below.

  1. The program asks the user to enter one thousand numeric values, reads them in, and stores them in an array. (You do not have to error check for non-numeric input.)
  2. After all the values have been read and stored, the program asks the user to enter a maximum value, and reads that value (again, you do not have to error check).
  3. The program then goes through the original 1000 values, and prints (one per line) all the values that are less than the maximum value entered in step 2.
SAMPLE SOLUTION
#include <cstdio>

const int NumValues = 1000;

int main()
{
   float Values[NumValues];
   printf("Please enter %d numbers\n", NumValues);
   for (int i = 0; i < NumValues; i++) {
       float val;
       scanf("%g", &val);
       Values[i] = val;
   }
   printf("Please enter a maximum value\n");
   float maxVal;
   scanf("%g", &maxVal);
   printf("The values less than %g are:\n", maxVal);
   for (int i = 0; i < NumValues; i++) {
       if (Values[i] < maxVal) {
          printf("%g\n", Values[i]);
       }
   }
   return 0;
}

Question 2: write a function [7]

Write a complete and correct C++ function that fulfills the requirements below:

For example, the call PrintBetween(3,7) would print integers 4, 5, and 6, and would return 15.
(If low is greater than or equal to high it would not print anything and would return 0.)
SAMPLE SOLUTION
int PrintBetween(int low, int high)
{
   int sum = 0;
   for (int i = low+1; i < high; i++) {
       printf("%d\n", i);
       sum += i;
   }
   return sum;
}

Question 3: modify a function [7]

(I) Rewrite the function below to use a while loop rather than the for loop (keeping the functionality as close as possible to the original).

// reverse the contents of an array
void reverse(long data[], int size)
{
   // work from the ends to the middle of the array,
   // swapping the characters in the two opposing positions
   int midpoint = size/2;
   for (int p = 0; p < midpoint; p++) {
       int opposite = size - (1 + p);
       int oldP = data[p];
       data[p] = data[opposite];
       data[opposite] = oldP;
   }
}
SAMPLE SOLUTION
void reverse(long data[], int size)
{
   int midpoint = size/2;
   int p = 0;
   while (p < midpoint) {
       int opposite = size - (1 + p);
       int oldP = data[p];
       data[p] = data[opposite];
       data[opposite] = oldP;
       p++;
   }
}

(II) Rewrite the function below to use a do-while loop rather than recursion.

// find the last array position containing the target value
//    and return it,
// return -1 if the target is nowhere in the array
int findLast(float arr[], int currPos, float target)
{
   if (currPos < 0) {
      return -1;
   }
   else if (arr[currPos] == target) {
      return currPos;
   }
   else {
      int result = findLast(arr, currPos-1, target);
      return result;
  }
}
SAMPLE SOLUTION
int findLast(float arr[], int currPos, float target)
{
   do {
      if (currPos < 0) {
         return -1;
      } else if (arr[currPos] == target) {
         return currPos;
      } else {
         currPos--;
      }
   } while (currPos >= 0);
   return -1;
}

Question 4: Show the output [7]

Show the output produced by the draw function below if the following call is made
( assuming the call comes from within an otherwise valid program of course):
draw(4,8);

void draw(int x, long y)
{
   long c = 1;
   for (int i = 0; i < x; i++) {
       long tmp = 5;
       printf("%d:", i);
       while (c < y) {
          printf("%ld", tmp);
          tmp++;
          c = c+2;
       }
       printf("\n");
       c = c + i - x;
   }
}
SAMPLE SOLUTION
0:5678
1:56
2:5
3:5

Question 5: Implement an algorithm [7]

Write the function shown in the prototype below, following the algorithm in the comments as closely as possible.

// return the position at which the pattern first appears in the given string,
//    or -1 if not found
// the function assumes the string and the pattern are null-terminated
// e.g. findMatch("test", "mytest"); would return 2,
//      findMatch("test", "testing"); would return 0,
//      findMatch("test", "stuff"); would return -1
int findMatch(char pattern[], char text[]);

// Algorithm:
//   create integer variables for the current text position,
//      the length of the pattern, and the length of the text
//   start the text position at 0,
//   use the strlen function to set the lengths of pattern and text
//   create a boolean variable to keep track of whether or not
//      we have found a match yet, and initialize it to false
//   while found is false and the text position plus pattern length
//      is smaller than the text length, do the following:
//         set the match found variable to true
//         for each position, p, from 0 to the pattern length - 1,
//             if the pattern character in position p does NOT
//                match the text character in position textPos + 1,
//                set the match found variable to false
//         after the for loop ends, if found is still true
//             then we have found a match, return the text position
//         otherwise increment the text position
//   after the while loop ends, we must not have found a match,
//      so return -1
//
SAMPLE SOLUTION
// return the position at which the pattern first appears in the given string,
//    or -1 if not found
int findMatch(char *pattern, char *str)
{
   int strPos = 0;
   int patLen = strlen(pattern);
   int totLen = strlen(str);
   bool found = false;
   while (((strPos + patLen) <= totLen) && !found) {
      found = true;
      for (int p = 0; p < patLen; p++) {
          if (pattern[p] != str[strPos + p]) {
             found = false;
          }
      }
      if (found) {
         return strPos;
      } else {
         strPos++;
      }
   }
   return -1;
}

  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 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("%[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
printf("The value of %d times %g is %g\n", i, f, (i*f));  // combined example

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;
    b = temp;                   }                                  float f = calc(i, 2.5);
}
                                                                   int array[20];
void initArray(int arr[], int size)                                initArray(array, 20);
{                                                               }
   for (int i = 0; i < size; i++
       arr[i] = 0;
}