FINAL EXAM: CMPT 125
2023-08-15
SOLUTIONS
1. Consider Inheritance. Indicate if the following statements are True
or False
a. When using private inheritance
2. Consider pointers and addresses. Answer each question below.
For questions requiring explanation, 1-3 sentences per point is the
maximum expected.
a. [4.5 points] Consider C++ function overloading. Given the
following three overloaded prototypes
i. int F1( double A, int B, char C);
ii. int F1(int H, int K, char P);
iii. int F1( int Y, double B, char M);
Which function would be called for each of the following
cases. Why?
Called with int int and char
ii because there is an exact match in function
signature (all types match)
Called with double double and char
Fails with error message, cannot choose between i
and iii because both require one promotion, and there
is no exact match
Called with double int and char
ii because there is an exact match in function
signature (all types match)
b. [3 points] Declare and initialize an integer variable (to a
value of 11) and an integer pointer variable initialized to
NULL. Then make the integer pointer variable pointer variable
point at the integer variable.
int v2 = 11;
int *integerp = NULL;
integer = &v2;
c. [2.5 points] You are given the following two function
prototypes
int fool(double, int, char);
void folly(char, double);
and the following variables are defined in the calling function
int A=0, B=23, C=88;
double Q=34.4, R=55.6;
char name=’z’, date=’o’, question= ‘4’;
Write correct call for each function, do not use a variable for
an argument more than once.
A = fool(Q, B, name);
folly(date, C);
d. [2 points] An array is declared as
int A[55]=0;
in the calling program. The array is passed to a function Q.
Function Q has only one argument. Function Q returns a
double. Write the prototype of function Q and the call to the
function as it would be made in the calling program.
double Q( int X[ ] ); //prototype
double Y;
Y = Q(A);
3. [9 points] Consider a class Queue which implements a last in
first out queue. Write the functions ~Stack(), enqueue, dequeue
as they would be written int the [Link] file for class Queue.
The class Queue is defined below. Remember that the
destructor destroys the queue not the Node.
typedef struct Node {
int data;
Node* front;
Node* rear;
}Node;
class Queue {
private:
Node* top;
public:
Queue();
~Queue();
void enqueue(int item);
int dequeue();
int peek();
bool is_empty();
int size();
};
Queue::~Queue() {
while (front != nullptr) {
Node* temp = front;
front = front->next;
delete temp;
}
}
void Queue::enqueue(int item) {
Node* newNode = new Node(item);
if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
int Queue::dequeue() {
if (!is_empty()) {
int frontItem = front->data;
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
return frontItem;
} else {
throw std::runtime_error("Queue is empty");
}
}
4. [8 points] Consider a linked list with unordered elements. Write the function
described below. When you write your function you may use any of the following
functions (You do not need to write them).
ListNode * createNode(int num);
void displayList(ListNode *head);
The following two functions add in order, or remove the node
with value num.
ListNode* insertNode(ListNode *head, int num);
ListNode* deleteNode(ListNode *head, int num);
ListNode* moveSmallestLink(List Node *startNode);
The function moves the link with the smallest value to the front (start) of the list
startNode is the the root of the list
This function returns the head of the list after moving the link containing the
smallest data value to the front of the list.
ListNode* moveSmallestLink(ListNode *startNode)
{
ListNode* smallest;
ListNode* nodePtr;
smallest = startNode;
nodePtr = startNode;
int smallestValue = 0;
while (nodePtr)
{
/*Action done to each link*/
if (nodePtr->value < smallest -> value)
{
smallest = nodePtr;
}
nodePtr = nodePtr->next;
}
nodePtr = startNode;
if (startNode != smallest)
{
smallestValue = smallest->value;
nodePtr = deleteNode(nodePtr, smallestValue);
nodePtr = insertNode(nodePtr, smallestValue);
}
return nodePtr;
}
5. [8 points] Express the running time of the following program
using Big-O notation. Operations counted to determine running
time are print, add, subtract, multiply divide, < = . Remember K+
+ is shorthand for K = K + 1. Explain, step by step, how you
determined the Big-O order of the code. To solve the problem
determine T(N)
int foo(int N) {
if (N > 1)
{
for( int K = 0; K < N; K++ )
{
fprintf( “%5d”, K);
}
return (foo (N/2));
}
else
{
fprintf(“1”);
return 1;
}
}
T(N) = T (N/2) + O(N) 2 points
T(N) = T(N/4) + O(N/2) + O(N)
= T(N/8) + O(N/4) + O(N/2)+ O(N)
2 points for first and second substitution
….
= O(N/(2k))+…+O(N/4)+O(N/2)+O(N) 2 points for generalization
The number of times that recursion happens is k=log2(N)
So T(N) is O(NlogN) 2 point for final conclusion
6. [12 points] Write a main function to do the following tasks. Your main function will
be complete enough to compile and run and will not contain any memory leaks or
hanging pointers. You can use scanf to read the user inputs. Assume the data is of
the type you are trying to read and that you do not need to check that input data
was correctly read. Your main program must do each of the following.
a. [1 point] prompt for and read the length N of the 1-D array you will use.
½ point each for, prompt, correct conversion (“%d”), correct actual
parameter (&N)
b. [2 points] Declare an automatic integer array with 100 elements and
initialize all the elements to 0
1 point for declaring the array with the correct size
1 point for initializing the array so all elements are 0
c. [4 points] Fill the array with random integers, 100<=integer<=200, (use
rand() and srand()). Declare the seed and initialize its value to 1234;
1/2 point for declaring the seed as an unsigned int
1/2 point for initializing the random number generator using srand. The
initialization must be done only once to get this point
1 point for putting a different random number in each element of the array
2 points for converting the number returned by rand to an integer between
10 and 50 inclusive
d. [5 points] Write the contents of the array into a file with filename requested
from the user. You do not need to check if the file opened correctly
1 point for declaring a file pointer
1 point for prompting for and reading the filename
1 point for opening the file (making the file pointer point at the file)
1 points for writing the array into the file. 1 for loop writing N elements of
your array, 1 for first argument of fprintf being your file pointer, 1 for
printing array elements.
1 point for closing the file
int main()
{
/*problem 5b )*/
int N = 0;
printf("Enter the length of the array");
scanf("%d", &N);
/*problem 5c also includes deallocation at end of
program*/
int *myArr = NULL;
myArr = (int*)malloc(N * sizeof(int));
if (myArr == NULL)
{
printf("ERROR: could not allocate memory for myArr");
return 1;
}
/*problem 5d*/
unsigned int myseed = 1234;
srand(myseed);
for (int k = 0; k < N; k++)
{
myArr[k] = rand() % 41 + 100;
}
/*problem 5e*/
FILE* mystream = NULL;
printf(“please enter the filename for your output file\n”);
char filename[128];
scanf(“%s”, filename);
mystream = fopen("[Link]", "w");
if (mystream == NULL)
for (int k = 0; k < N; k++)
{
fprintf(mystream, "%15d", myArr[k]);
if (k % 9 == 0) fprintf(mystream, "\n");
}
fclose(mystream);
return 0;
}
7. Consider the C++ code below;
a. [4 points] What does this code print for n=4
b. [4 points] Write an iterative version of the function.
#include <iostream>
void printPattern(int n, int current) {
if (current <= n) {
for (int i = n; i >= current; i--) {
cout << setw(4) << i * i << " ";
}
cout << endl;
printPattern(n, current + 1);
16 9 4 1
} 16 9 4
} 16 9
16
1 point per line
b)
void func3(int n)
{
for (int K = n; K >= 0; K--)
{
for (int U = 0; U <= K; U++)
{
printf("%4d ", (n-U)*(n-U));
}
printf("\n");
}
}
This is not the only possible solution, give points for the corresponding
parts of any correct solution.
1.5 points for outer loop, 1/2 each for initialization of counter, testing of
counter, incrementing of counter.
1.5 points for the inner loop, same breakdown as outer loop
½ point for printing correct value
½ point for correctly breaking the output into lines