| Question | Mark |
| 1. Implement an algorithm [10 marks] | |
| 2. Recursion [10 marks] | |
| 3. Nested loops [10 marks] | |
| 4. iostream, strings [10 marks] | |
| 5. Binary search [10 marks] | |
| 6. Arrays [10 marks] | |
| 7. Command line arguments, cstring [10 marks] | |
| 8. File I/O [10 marks] | |
| 9. structs [10 marks] | |
| 10. Pointers, dynamic allocation [10 marks] | |
| Exam Total [100 marks] |
Question 1: Implement an algorithm [10]
(i) Based on the algorithm for function f below, what value should be returned
by f(1709)?
(ii) Complete the implementation of function f below so that it matches the comments as closely as possible.
int f(int n)
{
// if n is less than 100 then return 0
// initialize int variables rem (with value n) and m (with value 1)
// while rem is greater than nine
// divide rem by 10 and multiply m by 10
// subtract rem*m from n then divide n by 10
// return the resulting value of n
}
Sample solution
int f(int n)
{
if (n < 100) return 0;
int tmp = n;
int m = 1;
while (tmp > 9) {
tmp = tmp / 10;
m = m * 10;
}
n = n - tmp*m;
n = n / 10;
return n;
}
|
Question 2: Recursion [10]
Function f has the prototype and implementation shown below:
void f(int n, int i=2);
void f(int n, int i)
{
cout << "f(" << n << "," << i << ")" << endl;
if (n > 1) {
if (n < 4) cout << n << endl;
else if ((n % i) == 0) {
cout << i << endl;
f(n/i,i);
} else if (n < i*i) cout << n << endl;
else f(n, i+1);
}
}
Show the complete and precise output that would result from
the call f(30)
(assuming it is called from a valid program that has included
the necessary libraries and is using the necessary namespaces).
Sample solution f(30,2) 2 f(15,2) f(15,3) 3 f(5,3) 5 |
Question 3: Nested loops [10]
Complete the function described by the comments and prototype below, using nested loops for the implementation (no recursion, no declaring additional functions).
// for each of N students: // prompt the user to enter M numerical marks // (no range limits on the marks, no error checking required) // compute and display each student's average mark (i.e. their total/M) // compute and return (don't display) the overall average for the group of students // (i.e. grand total / (N*M)) float average(int N, int M);
Sample solution
float average(int N, int M)
{
float gtotal = 0;
for (int s = 1; s <= N; s++ ) {
float tot = 0;
cout << "Please enter " << M << " numeric marks for student " << s << endl;
for (int m = 1; m <= M; m++) {
float curr;
cin >> curr;
tot += curr;
}
float ave = tot/M;
cout << "average for student " << s << " is " << ave << endl;
gtotal += ave;
}
return gtotal/N;
}
|
Question 4: iostream, string [10]
Using the iostream and string libraries (not cstdio/cstring), write a program that reads 1000 lines of input from the user, keeping track of the total number of characters read and the longest line read so far.
After all 1000 lines have been read, display the total number of characters read and the content of the longest line.
Sample solution
#include <iostream>
#include <string>
using namespace std;
int main()
{
int max = 0;
string longline = "";
int numc = 0;
const int NumL = 1000;
for (int i = 0; i < NumL; i++) {
string line;
getline(cin, line);
int curr = line.length();
if (curr > max) {
longline = line;
max = curr;
}
numc += curr;
}
cout << "total chars " << numc << endl;
cout << "longest line:" << endl << longline << endl;
}
|
Question 5: Binary search [10]
For the binary search function provided below, and assuming our data array is
double data[M] = { 1.5, 3.7, 2.1, 5.5, 0.4 }; // (constant M is 5)
(i) Explain why bSrch(data, 5.5, M) successfully finds
the value 5.5 in position 3, but bSrch(data, 3.7, M) does not find
the value 3.7.
(ii) If an array contains duplicate values, explain why bSrch
won't necessaily find the first array value matching a specific target.
int bSrch(double arr[], double target, int size)
{
int low = 0;
int high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
Sample solution
(i) Binary search expects the array to be sorted (in ascending order for
this particular binary search implementation), otherwise there is no
guarantee it will work correctly.
In the case of the search for 5.5 in the example above, we just happen
to get lucky: the first pass through the while loop uses 2 as the midpoint,
sees value 2.1, and decides the target value must be in the upper half.
In the subsequent pass, using 3 as the midpoint, it luckily lands right
on the target value.
In the case of the search for 3.7, things do not go so fortunately.
The first pass goes as above, again expecting 3.7 to be "above" 2.1,
and searching the "right" side of the array in subsequent passes,
where (of course) the target value can never be found.
(ii) The easiest way to demonstrate this is through an example.
Consider the array [ 1, 1, 1, 1, 1 ] and a bSrch for value 1.
The algorithm uses the midpoint (2) as the first spot to look,
and immediately lands on the 1 value in the middle of the array
and returns its position (2), even though there are similar values
located earlier in the array. This demonstrates the problem with
respect to finding the "first" instance of a value: because bSearch
repeatedly searchs the middle of smaller and smaller subsections,
stopping as soon as it finds the target, it has no way of knowing
if there are, in fact, equal preceeding values in the array - it
simply knows it has found an instance of the value.
|
Question 6: Arrays [10]
Implement the two functions described by the comments and prototypes below:
// multiply each element of the array by the scalar value supplied
// e.g. if the array contents were initially { 2.0, 3.6, 4.0 } and scalar was 1.5
// then the resulting array contents would be { 3.0, 5.4, 6.0 }
void scale(float arr[], int size, float scalar);
// compute and return the sum of all the array elements in positions
// low through high (inclusive)
long rangesum(long data[], int low, int high);
Sample solution
void scale(float arr[], int size, float scalar)
{
for (int i = 0; i < size; i++) {
arr[i] *= scalar;
}
}
long rangesum(long data[], int low, int high)
{
long sum = 0;
for (int i = low; i <= high; i++) {
sum += data[i];
}
return sum;
}
|
Question 7: Command line arguments, cstring [10]
Write a complete and correct C++ program that checks each of its command line arguments, displaying each of those that contain nothing but digits.
For example, if run using the command
./q7x foo x10 123 9a 20 9876
the program would display
123 20 9876
Sample solution
#include <cstdio>
#include <cctype>
#include <cstring>
bool allDigits(char str[]);
int main(int argc, char *argv[])
{
for (int i = 0; i < argc; i++) {
if (alldigits(argv[i])) {
printf("%s ", argv[i]);
}
printf("\n");
}
}
bool allDigits(char str[])
{
int i = 0;
while (str[i] != '\0') {
if (!isdigit(str[i])) {
return false;
}
}
return true;
}
|
Question 8: File I/O [10]
Write a C++ program that gets the user to enter two filenames and copies all the digits from the first file into the second file (overwriting the second file). (You may use either the fstream/string libraries or the cstdio/cstring libraries.)
Sample solution
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
string f1, f2;
ifstream infile;
ofstream outfile;
cout << "Enter an input file name";
cin >> f1;
cout << "Enter an output file name";
cin >> f2;
infile.open(f1);
if (!infile.fail()) {
outfile.open(f2);
if (!outfile.fail()) {
while (!infile.eof()) {
char c;
infile.get(c);
if (!infile.eof() && isdigit(c)) {
outfile << c;
}
}
outfile.close();
}
infile.close();
}
}
|
Question 9: structs [10]
Given the Data struct and the two function prototypes described below,
implement both functions.
struct Data {
float f;
int i;
char c;
};
// set the three fields of d with values entered by the user
// (no error checking required)
void fill(struct Data &d);
// in the array of structs, find the largest f value of any element,
// the largest i value, and the largest c value,
// then store those three values in the L parameter
void largeVals(struct Data arr[], int Size, struct Data &L);
Sample solution
void fill(struct Data &d)
{
cout << "Please enter a number, then an integer, then a character";
cin >> d.f >> d.i >> d.c;
}
void largeVals(struct Data arr[], int Size, struct Data &L)
{
if (Size > 0) {
L.f = arr[0].f;
L.i = arr[0].i;
L.c = arr[0].c;
for (int p = 1; p < Size; p++) {
if (arr[p].f > L.f) {
L.f = arr[p].f;
}
if (arr[p].i > L.i) {
L.i = arr[p].i;
}
if (arr[p].c > L.c) {
L.c = arr[p].c;
}
}
}
}
|
Question 10: Pointers, dynamic allocation [10]
(a) Given the swap(int*,int*) function and main routine below, explain
why swap(&x,&y) successfully exchanges the contents of variables x and y.
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main()
{
int x = 10;
int y = 20;
swap(&x, &y);
}
(b) Allocate an array of 73 floats to variable float* f;
(c) Test if the allocation in (b) succeeded, and if it did succeed then deallocate the array contents and set the array to null.
Sample solution
(a) main passes the memory addresses of integers x and y to swap,
where the addresses are stored in pointers a and b respectively.
Within swap, we use the pointers to look in memory and access/change
the contents there, effectively allowing us to change the values
of x and y without technically passing them by reference.
The specific functionality of swap is our usual (store the old value
of var1, replace var1's value with var2's, replace var2's value
with the stored old var1), we're simply accessing the actual integers
through pointers to them.
(b) f = new float[73];
(c) if (f != NULL) {
delete [] f;
f = NULL;
}
|
CSCI 160 Exam Quick Reference Sheet: Sections F19N01-F19N04
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";
const char[] ErrMsg = "Error: something terrible happened!\n"; // works like char*
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
sscanf(str, "%d", &x); // read from the string instead of stdio
// example testing if output fails,
// if so then read and discard one "word" from the input buffer
if (scanf("%g", &f) == 0) scanf("%*s");
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
sprintf(str, "%d", i); // print into the string instead of stdout
Sample input with cin (iostream library, namespace std)
=======================================================
cin >> x;
// example of checking for input failure,
// and, on failure, read/discard up to N characters or until end-of-line
if (cin.fail()) {
cin.ignore(N, '\n');
cin.clear();
}
Sample output with cout (iostream library, namespace std)
=========================================================
cout << "x is " << x << endl; // display text, variable, and newline
setting fixed width and precision (iomanip library, namespace std)
==================================================================
setiosflags(ios::fixed);
cout << setprecision(2) << x; // show exactly 2 digits after decimal place
cout << setw(5) << x; // pad x (with spaces) to width at least 5
The C++ string class (using the library, namespace std)
================================================================
string str; // declare a string variable str
str = "blah blah blah"; // assign text to a string
str[3] = 'x'; // change the fourth character in the string to x
// example of using as a null terminated char arrray (through .c_str())
printf("%s", str.c_str()); // print the string contents
Reading from strings (stringstream library, namespace std)
==========================================================
std::string s = "20 10.5";
istringstream istr(s);
int i; float f;
istr >> i >> f;
File I/O using cstdio
=====================
FILE *fp = fopen(infile, "r"); // "r" for input, "w" for output, "a" for append
if (!fp) // open failed
fclose(fp); // to close an open file
fp.eof() // returns true if it has detected end-of-file
fgets(arr, max, fp); // read line from fpin to char arr[]
char c = fgetc(fp); // read single char
ungetc(c); // put char back into input buffer
fprintf(fp, "x is %d", x); // write to file instead of stdout
File I/O using fstream (and namespace std)
==========================================
ifstream inf; // input file object
ofstrea outf; // output file object
inf.open(filename); // try to open
inf.fail() // returns true if file is not open
inf.eof() // returns true if end of file detected
inf.close(); // closes open file
inf >> var; // read from open file into variable
inf.get(c); // read one char from open file into a char variable
getline(inf, str); // read a line from open file into string
outf << var; // write to an open file
Other 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);
}
// command line args
void initArray(int arr[], int size) int main(int argc, char* argv[])
{ {
for (int i = 0; i < size; i++ for (int i = 0; i < argc; i++) {
arr[i] = 0; printf("%s\n", argv[i]);
} }
}
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';
};