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" file | correct "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 thelibrary) ==================== 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