CSCI 160 Final Exam Fall 2015

Name: ________________________________

Number:_______________________________

Instructor: Dave Wessels


Question 1: syntax errors [10]

Identify at least 10 syntax errors in the following C++ program:

For each error, be sure to give the line number and briefly explain the precise nature of the error.

Note: No line contains 2 errors. If there are 2 errors on the same line it is part of the same error.

1  #include [cstdio]
2  int A = { 3, 1, 4, 5, 6, 2};
3
4  void swap(int index1, int index2)
5  {
6     temp = A[index1];
7     A[index1] = A[index2];
8     A[index2] = temp;
9  }
10
11 void printArray()
12    printf("      [");
13    for(int i = 0; i < 6; i++)
14    {
15       printf("%d, ", A[i]);
16    }
17    printf("]\n");
18 }
19
20 int partition(int low, int high)
21 {
22    printf("   Partition(A, %d, %d)\n", low, high);
23    int pivot = [Alow];
24    int leftwall = low;
25
26    for (int i = low+1, i <= high , i++)
27    {
28       if (A[i] < pivot)
29       {
30          leftwall++;
31          swap(i, leftwall);
32       }
33    }
34    swamp(low,leftwall);
35    printf("      Pivot %d\n, pivot);
36    printf("      LeftWall \n", leftwall);
37    printArray();
38    return(leftwall);
39 }
40
41 void quicksort(int low, int high)
42 {
43    printf(`Quicksort(A, %d, %d)\n', low, high);
44    if (low < high)
45    {
46       int pivot == partition(low, high);
47       quicksort(low, pivot-1);
48       quicksort(pivot+1, high);
49    }
50 }
51
52 void main()
53 {
54    quicksort(0, 5);
55 }
Sample solution
#include <cstdio>  // wrong type of brackets used ([])
int A[] = { 3,1,4,5,6,2};  // missing the array brackets [ ]

void swap(int index1, int index2)
{
   int temp = A[index1];   // temp wasn't declared
   A[index1] = A[index2];
   A[index2] = temp;
}

void printArray()
{                         // missing the { for the function
   printf("      [");
   for(int i=0; i<6; i++)
   {
      printf("%d, ", A[i]);
   }
   printf("]\n");
}

int partition(int low, int high)
{
   printf("   Partition(A, %d, %d)\n", low, high);
   int pivot = A[low];               // A was inside brackets instead of outside
   int leftwall = low;

   for (int i = low+1; i<=high ; i++)   // used , instead of ; separating for loop parts
   {
      if (A[i] < pivot)
      {
         leftwall++;
         swap(i, leftwall);
      }
   }
   swap(low,leftwall);                 // called swamp instead of swap
   printf("      Pivot %d\n", pivot);  // was  missing closing "
   printf("      LeftWall %d \n", leftwall);  // was missing %d
   printArray();
   return(leftwall);
}

void quicksort(int low, int high)
{
   printf("Quicksort(A, %d, %d)\n", low, high); // had ` and ' instead of " and "
   if (low


Question 2: Show output I [10]

Carefully study the program below and show the precise output it would produce.

#include <cstdio>

void drawChr(char c, int times);
void update(int &s, int &m);

int main()
{
   int rows = 15;
   int side = 0;
   int middle = rows/2;
   while (middle > 2) {
      drawChr('.', side);
      drawChr('#', middle);
      drawChr('.', side);
      update(side, middle);
      printf("\n");
   }
   for (int i = 0; i < 3; i++) {
      drawChr('.', side);
      drawChr('#', middle);
      drawChr('.', side);
     printf("\n");
   }
   drawChr('#', side+middle+side);
   printf("\n");
}

void drawChr(char c, int times)
{
   for (int i = 0; i < times; i++) {
      printf("%c", c);
   }
}

void update(int &s, int &m)
{
   s++;
   m = m - 2;
}
Sample solution
#######
.#####.
..###..
...#...
...#...
...#...
#######


Question 3: Implement an algorithm [10]

Part 1: use the following algorithm to implement a function, digitSum, that finds the sum of all the digits in a positive integer. For example, if the number is 478, the function should calculate that 4+7+8=19 and return 19.

   sum = 0
   repeat until input = 0
      add the last digit of input to sum
      remove the last digit from sum
   once the loop completes return sum
Part 2: It is possible to determine if a number is divisible by 9, by calling digit sum on the number repeatedly until the result is a 1 digit number. If that number is 9 then the number is a multiple of 9, otherwise it is not.

Write a complete and correct C++ program that takes a positive integer as a command line argument and displays "9 multiple" if it is a multiple of 9, or "Not 9" if it is not.

Your program must have at least three functions: digitSum, nineMultiple, and main.

Sample solution
#include <cstdlib>
#include <cstdio>

int digitSum(int input);

int main(int argc, char *argv[])
{
   if (argc > 1) {
      int input = atoi(argv[1]);
      int sums = input;
      while (sums > 9) {
         sums = digitSum(sums);
      }
      if (sums == 9) {
         printf("9 multiple\n");
      } else {
         printf("Not 9\n");
      }
   }
}

int digitSum(int input)
{
   int sum = 0;
   while (input > 0) {
      sum += (input % 10);
      input /= 10;
   }
   return sum;
}


Question 4: Write a function [10]

Write a C++ function named receipt that conforms to the following specifications:

Sample solution
void receipt(Item arr[], int numElements)
{
   float total = 0;
   for (int i = 0; i < numElements; i++) {
       float subtotal = arr[i].quantity * arr[i].price;
       printf("%s %d@$%.2f $%.2f\n", arr[i].name, arr[i].quantity, arr[i].price, subtotal);
       total = total + subtotal;
   }
   printf("Total $%.2f\n", total);
}


Question 5: Fix a program [10]

The program below contains at least five syntax and/or logic errors. Assuming the comments are correct, modify the code so that it would compile cleanly and behave as specified in the comments.

// Given two arrays that are the same width, secretCode contains a code the
// user is trying to break and guess contains the user's guess at the code.
// The secret code is not necessarily in base 10, NUMBASE indicates which base
// it is in.  So if NUMBASE is 4 then only digits 0, 1, 2, and 3 are possible.

#include <cstdio>
const int WIDTH = 5;

// count and return the number of times the value target
//   appears in the array
int countOccurances(int array[], int target);

// This function counts how many of the digits in guess are a correct digit,
// whether or not they are in the right location, by taking the minimum of the
// number of times they occur in each of the two arrays.
int evaluateGuess(int secretCode[], int guess[]);

int main()
{
   int code[]  = { 1, 2, 3 };
   int guess[] = { 3, 1, 5 };
   printf("%d are correct\n", evaluateGuess(code, code);
}
int evaluateGuess(int secretCode[], int guess[])
{
   int result;
   int inGuess;
   int inAnswer;
   for (int i = 1; i <= NUMBASE; i++) {
      inGuess = countOccurances(guess, i);
      inAnswer = countOccurances(secretCode, i);
      if (inGuess > inAnswer) {
         result += inGuess;
      } else {
         result += inAnswer;
      }
   }
   return true;
}

int countOccurances(int array[], int target)
{
   int count = 0;
   for (int i = 0; i < WIDTH; i++) {
      if (array[i] != target) {
         count++;
      }
   }
   return count;
}
Sample solution
#include 
const int WIDTH = 5;
const int NUMBASE = 6;       // NUMBASE wasn't declared, not sure how big it should be

int countOccurances(int array[], int target);

int evaluateGuess(int secretCode[], int guess[])
{
   int result;
   int inGuess;
   int inAnswer;
   for (int i = 1; i <= NUMBASE; i++)
   {
      inGuess = countOccurances(guess, i);
      inAnswer = countOccurances(secretCode, i);
      if (inGuess < inAnswer)         // was taking the maximum
      {
         result += inGuess;
      }
      else
      {
         result += inAnswer;
      }
   }
   return true;
}

int countOccurances(int array[], int target)
{
   int count = 0;
   for (int i = 0; i < WIDTH; i++)
   {
      if (array[i] == target)    // was counting # not equal to target
      {
         count++;
      }
   }
   return count;
}

int main()
{
   int code[] = {1, 2, 3};
   int guess[] = {3, 1, 5};
   printf("%d are correct\n", evaluateGuess(code, guess));   // missing final )
                      // and forgot to pass the guess (passed code twice)
}


Question 6: File I/O [10]

Write the following function:

// This function opens srcfile for reading and destfile for writing.
// It then reads srcfile character by character, converts each character
//    to uppercase, and writes to destfile.
// It returns true if successful, or false if either file could not be opened.
bool copyFileToUpperByChars(const char srcfile[], const char destfile[])
Sample solution
bool copyFileToUpperByChars(const char srcfile[], const char destfile[])
{
   FILE* fpin = fopen(srcfile, "r");
   if (fpin == NULL) {
      return false;
   }
   FILE* fpout = fopen(destfile, "w");
   if (fpout == NULL) {
      fclose(fpin);
      return false;
   }
   while (!feof(fpin)) {
      char nextc = getc(fpin);
      if (!feof(fpin)) {
         fprintf(fpout, "%c", toupper(nextc));
      }
   }
   fclose(fpin);
   fclose(fpout);
   return true;
}


Question 7: Recursion and loops [10]

Part I: What is the output of this program?

#include <cstdio>

int main()
{
   int counter = 0;
   for (int a = 0; a < 5; a++) {
       int x = 0;
       while (x < a) {
          x++;
          counter++;
       }
   }
   printf("Counter is %d\n", counter);
}
Sample solution
Counter is 10

Part II: Rewrite the factorial function so that it uses a loop instead of recursion.

// recursive function calculates n!
int FactorialRecursive(int n)
{
   if (n <= 1) {
       return 1;
   }
   return n * FactorialRecursive(n - 1);
}
Sample solution
int Factorial(int n)
{
   int result = 1;
   while (n > 1) {
      result *=n;
      n--;
   }
   return result;
}


Question 8: Dynamic allocation [10]

Write the following function:

// given an array, arr, that is size arrSize,
//    try to allocate a new array that is twice the size of the original
// if successful, copy the contents across, delete the old array,
//    make arr point to the new array, set the new size, and return true
// otherwise return false (without altering arr or size)
bool resize(float* &arr, long &arrSize)
Sample solution
bool resize(float* &arr, long &arrSize)
{
   long newSize = 2 * arrSize;
   float* newArr = new float[newSize];
   if (newArr == NULL) {
      return false;
   } else {
      for (int i = 0; i < arrSize; i++) {
          newArr[i] = arr[i];
      }
      delete [] arr;
      arr = newArr;
      arrSize = newSize;
      return true;
   }
}


Question 9: Show output II [10]

Show the output that would result from running the program below.

#include <cstdio>

enum States {
   fetching, decoding, executing, done
};

void execute(int i);

int main()
{
   States myState = fetching;
   int statementNumber = 0;

   while (myState != done) {
      switch(myState) {
         case fetching:
            printf("Fetching instruction %d\n", statementNumber);
            myState = decoding;
            break;
         case executing:
            printf("Executing\n");
            execute(statementNumber);
            myState = done;
            if (statementNumber < 2) {
               statementNumber++;
               myState = fetching;
            }
            break;
         case decoding:
            printf("Decoding\n");
            myState = executing;
         default:
            myState = done;
            break;
      }
   }
}

void execute(int i)
{
   switch (i) {
      case 1: printf("Look out for number 1 but\n");
              // note no break
      case 2: printf("But do not step in number 2\n");
              break;
      case 3: printf("So this is what a computer does?\n");
              break;
      default: printf("Error line %d\n", i);
              break;
   }
}

Sample solution
Fetching instruction 0
Decoding
Executing
Error line 0
Fetching instruction 1
Decoding
Executing
Look out for number 1 but
But do not step in number 2
Fetching instruction 2
Decoding
Executing
But do not step in number 2


Question 10: Cache discussion [10]

  1. What is a segmentation fault?

  2. What is the purpose of the cache in the execution cycle?

  3. What are three causes of a cache miss? Briefly explain each one.
Sample solution
A segmentation fault is a fault or failure, used to notify the operating system that
a program has tried to inappropriately access memory - usually either by attempting
to dereference a null pointer, attempting to access an invalid memory address, or
attempting to access a memory address it doesn't have appropriate access rights to.

The cache is used to store frequently (or recently) accessed data or instruction,
providing faster access to the data than by retrieving the data from main memory.
(The cache is faster than main memory, but smaller and more expensive byte-for-byte.)

Cache misses occur when the requested data is not in the cache.  This can occur
because the data in question has not yet been loaded in the cache (it is still
in main memory), or when it was previously in the cache but has since been forced
out by more recent data accesses, or when the data in question is not in memory
at all (neither the cache nor main memory).


  CSCI 160 Exam Quick Reference Sheet: Sections F13N01-F13N04
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("%[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
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;
}              

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 {                         struct node {
   char initials[2];                     float data;
   int id;                               node *next;
   float value;                       };
};
                                      node *n;
Info i;                               n = new node;
i.id = 0;                             if (n != NULL) {
i.value = -34.216;                       n->data = 0;
i.initials[0] = 'D';                     n->next = NULL;
i.initials[1] = 'W';                  }
                                      delete n;

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