Data Structures and Algorithms

Test 1 Study Guide

Tests in this course may contain any material covered in lecture up until this point, although much stronger emphasis will be placed on material for which you have received graded feedback. This page contains a collection of exercises that you may wish to complete to prepare yourself for the test. Note that you do not need to complete all of the offered exercises; more questions appear here than will appear on your test.

Programming in C++

Write a function arraySum that takes three int* arrays and an int length. All three arrays are assumed to be the same length. For each index in the arrays, the sum of the first and second value is stored in the third.
Write a function average which computes the average of the values in an array of floats. You must take a float* parameter; you may take other parameters as you see fit. Your function should return the average of the values in that array.
Write a function fibonacci which takes a parameter int n and returns an int* to a new array which contains the first n Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, …).
Write a function zerowash which allocates space for a million int values, sets them all to 0, and then deallocates the memory.
Explain the difference between delete and delete[].

void arraySum(int* first, int* second, int* third, int length) {
    for (int i=0;i<length;i++) {
        third[i] = first[i] + second[i];
    }
}

float average(float* data, int count) {
    float total = 0;
    for (int i=0;i<count;i++) {
        total += data[i];
    }
    return total/count;
}

int* fibonacci(int n) {
    int* result = new int[n];
    for (int i=0;i<n;i++) {
        if (i<2) {
            result[i] = i;
        } else {
            result[i] = result[i-1] + result[i-2]
        }
    }
    return result;
}

void zerowash() {
    int* space = new int[1000000];
    for (int i=0;i<1000000;i++) {
        space[i] = 0;
    }
    delete[] space;
}

Debugging C++

Each of the following code fragments contains a bug. Identify the bug and explain how to correct it.

Code to create an array of ten elements and set each element equal to its index.
```
int* array = new int[10];
for (int i=1;i<=10;i++) {
    array[i] = i;
}
```

Code to define a function which sums all of the values in an array.

int sum(int* array) {
    int acc = 0;
    for (int i=0;i<len(array);i++) {
        acc += array[i];
    }
    return acc;
}

Code to define a class which represents a single (X,Y) coordinate.

class Point {
public:
    Point(int x, int y);
    int getX();
    int getY();
private:
    int x;
    int y;
};
Point::Point(int x, int y) {
    x = x;
    y = y;
}
int Point::getX() {
    return x;
}
int Point::getY() {
    return y;
}

Code to calculate the distance between two points.

Point* p;
Point* q;

float dx = p->getX() - q->getX();
if (dx<0) {
  dx = -dx;
}
float dy = p->getY() - q->getY();
if (dy<0) {
  dy = -dy;
}
float dist = sqrt(dx*dx+dy*dy); // assume sqrt exists (in the cmath library)
cout << "The points are " << dist << " unit(s) apart." << endl;

The body of the constructor will not do anything. It should read

this->x = x;
this->y = y;

For consistency, the getX and getY methods should also be using this->.

Object-Oriented Programming

What is the purpose of a class? What is the difference between a class and an object?
Define polymorphism as it pertains to C++. Give an example which was not given in lecture.
What is the purpose of the private keyword?

Draw a stack diagram of the following code when it reaches the end of main. Be sure to be clear what is on the stack and what is on the heap.

class LabAssignment {
public:
    LabAssignment(int number, int score);
    int number;
    int score;
}
LabAssignment::LabAssignment(int number, int score) {
    this->number = number;
    this->score = score;
}

int main() {
    LabAssignment a(1,98);
    LabAssignment* b = new LabAssignment(2,84);
    LabAssignment* c = b;
    b = new LabAssignment(3,95);
    c->score = 92;
    return 0;
}