| Question | Mark |
| 1. Recursion [6 marks] | |
| 2. Loops [6 marks] | |
| 3. Nested loops [6 marks] | |
| 4. Arrays [6 marks] | |
| 5. Searching techniques [6 marks] | |
| Exam Total [30 marks] |
Question 1: Recursion [6]
(i) Show the complete and precise output produced by the C++ program below.
#include <cstdio>
void f(int x);
int main()
{
f(4);
}
void f(int x)
{
if (x > 0) {
printf("%d\n", x);
f(x-1);
printf("%d\n", x);
} else {
printf("0\n");
}
}
|
(ii) Rewrite function f from the program above, but using a pair of loops (instead of recursion) to achieve the same functionality and behaviour.
Sample Solution
int i;
// note that the 0 should be printed between the loops
// just in case the original x value is < 0
for (i = x; i >= 0; i--) {
printf("%d\n", i);
}
// 0 needs to
printf("0\n");
for (i = 1; i <= x; i++) {
printf("%d\n", i);
}
|
Question 2: Loops [5]
(i) Rewrite the code segment below to achieve the same functionality and behaviour using a do-while loop.
int a, b, c;
b = 17;
for (a = 1023; a > 0; a = a-2) {
c = a % b;
printf("%d mod %d is %d\n", a, b, c);
}
|
(ii) Rewrite the code segment below to achieve the same functionality and behaviour but using a for loop.
double x = 1.5;
double y = pow(2.5, 11.4);
while (x <= y) {
x = x * 2;
printf("%lg\n", x);
}
|
Question 3: Nested loops [6]
Show the complete and precise output produced by the C++ program below.
#include <cstdio>
int main()
{
int i = 1;
int j = 10;
while (i < j) {
int k = j - 2;
printf("%d,%d:", i, j);
do {
printf(" %d", k);
k = k - 2;
} while (k > i);
printf("\n");
i++;
j--;
}
}
|
Question 4: Arrays [6]
Write the countVals function described in the comments/prototype below.
// countVals counts and returns the total number of times the target value // appears in the array in positions m through n (inclusive), int countVals(double arr[], int m, int n, double target); |
Sample Solution
int countVals(double arr[], int m, int n, double target)
{
// if m > n, some folks assumed there is nothing to search,
// others assumed the range still needs to be searched,
// I accepted either interpretation, the code snippet below
// is for the "yes search it" interpretation
int low = m;
int high = n;
if (m > n) {
low = n;
high = m;
}
int count = 0;
for (int i = low; i <= high; i++) {
if (arr[i] == target) {
count++;
}
}
return count;
}
|
Question 5: Searching arrays [6]
(i) Show the complete and precise output of the C++ program below.
#include <cstdio>
int binSearch(long arr[], int low, int high, long target);
int main()
{
long arr1[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
long arr2[6] = { 1, 3, 2, 4, 5, 6 };
int pos1 = binSearch(arr1, 1, 6, 30);
if (pos1 >= 0) {
printf("Found in position %d\n", pos1);
} else {
printf("Not found\n");
}
int pos2 = binSearch(arr2, 0, 5, 3);
if (pos2 >= 0) {
printf("Found in position %d\n", pos1);
} else {
printf("Not found\n");
}
}
int binSearch(long arr[], int low, int high, long target)
{
while (low <= high) {
printf("Searching from %d to %d\n", 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;
}
|
(ii) Explain why the second call to binary search failed to find the target value, even though the value was present in the array.
Sample Solution Binary search is only reliable if the array content is sorted (and sorted in the appropriate order, non-decreasing or non-increasing). In the example above, the first pass computes the midpoint as 2, compares the value in arr[2] (which is also 2) to the target value (3), and concludes the target value must be in the upper half of the array, which it is not. |
CSCI 160 Exam Quick Reference Sheet: Sections F18N01-F18N04
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("%*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;
}