CSCI 159: exam practice questions

These are just meant as a way to get some practice answering exam-style questions with pen/paper. I'd encourage students to attempt them with minimal references to their notes, but for the final exam you will be permitted one double-sided sheet of notes.

There is one question on each side of the page.

After you've attempted the question, a good way to evaluate your answer while also getting additional practice is to coding and compiling/running the answer you came up with.

Question 1: searching

Write a function that does a linear search of an array for a target value and returns its position (or -1 if not found) but returns the position of the last element in the array that has the target value.

Thus if the array contents were 6,17,-3,92,18,17,82,1 and we searched for the target 17 it would return position 5.

Hint: start at the end of the array and search towards the beginning. 
int find(double arr[], int size, double target)
{
   //Sample solution, searching positions from size-1 down to 0
   // and quitting the first time we find the target
   int pos = size-1;
   while (pos >= 0) {
      if (arr[pos] == target) {
         return pos;
      }
      pos--;
   }
   return -1;
   
}

Question 2: sorting

The algorithm below is an alternative to bubblesort as a way of sorting. 
algorithm
---------
given an array of N elements
for each position, p, from 0 through N-2:
    find the smallest element in the array from positions p through N-1
       and swap it with array element p
(effectively working forward through the array, repeatedly finding the
 smallest remaining value to go into the current position)
Finish the sort function below, but following the new algorithm to carry out the sort. 
void sort(double arr[], int N)
{
   //Sample solution
   for (int p = 0; p <= N-2; p++) {
       int smallest = arr[p];
       int smallpos = p;
       for (int pos = p+1; p < N; p++) {
           if (arr[pos] < smallest) {
              smallest = arr[pos];
              smallpos = pos;
           }
       }
       swap(arr[p], arr[smallpos]);
   }
}

// assuming there's a swap like this available
void swap(double &x, double &y)
{
   double tmp = x;
   x = y;
   y = tmp;
}