Practice final exam

The questions below are meant to give a feel for the length and difficulty of the final exam, and for the breadth/depth of possible final exam questions. The specific topics/nature of the actual final will of course vary: particularly with respect to which questions are discussion style and which involve a coding component.

  1. Searching/sorting:
    Suppose as part of a game an elementary school teacher was sorting the students in a class by height. To do so, the teacher had all the students stand up, picked the tallest one and put them first in line, then picked the next tallest one and put them next in line, and so on until all students were placed.

    (i) Of the sorting algorithms we studied, which would you say this most closely resembled and why?

    (ii) Does this real life/physical sorting approach have any advantages or disadvantages compared to the programmed approach in terms of order of efficiency or in terms of accuracy? Justify your answer.

  2. Linked lists:
    Given our typical struct-based linked list definition below, write a function that would take a List as a parameter (passed by reference) and would reverse the order of the nodes in the list. I.e. the front node would become the back node (and vice versa) and for each node in the list the next/prev values would swap. 

    struct node {
   double val;
   node* next;
   node* prev;
};

struct List {
   node* front;
   node* back;
};

  3. Standard template library:
    Suppose we were using the standard template library's stack class for a stack of ints, i.e. stack<int> and its associated methods for push(i), pop(), top(), and isempty().

    (i) Implement the inverted function below, that makes the new stack an "upside down" copy of the original (i.e. what was on the top of the old stack is on the bottom of the new one). You may assume the new stack is empty to begin with.
    void inverted(const stack& orig, stack& newstack)

    (ii) Briefly explain why the original would be passed by reference but as a const.

  4. Constructors/operators:
    Suppose we have an StockItem class defined as shown below. 

    class StockItem {
   private:
     std::string description;
     int numInStock;
     float price;
     long itemId;
   public:
     StockItem(std::string d="", int n=0, float p=0, long i=0) {
         description = d; numInStock = n; price = p; itemId = i;
     }
     void printItem();
};

    (i) Would a default copy constructor suffice for this class? Why or why not?

    (ii) Suppose we wanted to be able to use the * operator to scale the item's price, e.g.
    StockItem s("widget", 10, 9.99, 1234);
    s = s * 1.5; // increases price by 50% Write an implementation of the overloaded * operator for StockItem.

  5. Binary search trees:
    Suppose we have a binary search tree class defined as shown below, in which duplicate values are permitted (equal values going into left subtrees).

    (i) Implement the private count method, intended to count the number of times a value appears in the (sub)tree.

    (ii) What order of efficiency is your algorithm? Justify your answer. 

    class tree {
   private:
      struct node {
         int value;
         node* left;
         node* right;
      } *root;
      void deallocate(node* subtree);
      int count(node* subtree, int v);
      void print(node* subtree);
      void insert(node* &subtree, int v);
   public:
      tree() { root = NULL; }
     ~tree() { deallocate(root); }
      int count(int v) { return count(root); }
      void print() { print(root); }
      void insert(int v) { insert(root, v); }
};

  6. Polymorphism/dynamic binding:
    Show the precise output from the program below. 
    #include <iostream>
using namespace std;

class parent1 {
   public:
      virtual void print() = 0;
};

class parent2 {
   public:
      void print() { cout << "print version 1" << endl; }
};

class child1: public parent1 {
   public:
      child1() { cout << "start child type 1" << endl; }
      ~child1() { cout << "end child type 1" << endl; }
      void print() { cout << "print version 2" << endl; }
};

class child2: public parent1 {
   public:
      child2() { cout << "start child type 2" << endl; }
      ~child2() { cout << "end child type 2" << endl; }
      void print() { cout << "print version 3" << endl; }
};

class child3: public parent2 {
   public:
      child3() { cout << "start child type 3" << endl; }
      ~child3() { cout << "end child type 3" << endl; }
      void print() { cout << "print version 4" << endl; }
};

int main()
{
    parent1 *p1 = new child1;
    parent1 *p2;
    child3 c3;

    p1->print();

    p2 = new child2;

    p2->print();

    delete p2;

    c3.print();
}

  7. Inheritance:
    Suppose we have a Circle class as shown below, and we want to create a new ShadedCircle class.

    The new class is to be derived from circle (publicly), but adds three new integer fields: red, green, and blue (to represent an RGB colour for the shaded circle).

    (i) Provide a suitable definition for the new class, assuming it needs to override the print method and needs a new method to set the red, green, blue values. (You do not need to provide the method implementations.) 

    class Circle {
   private:
     float x, y, radius;
   public:
     Circle(): x(0), y(0), radius(1) { }
     void print();
     void setcoords(float newx, float newy);
     void setrad(float newrad);
};

    (ii) Using your class definition, write a main routine that declares a ShadedCircle using the default values, then subsequently changes the coordinates to 3, 5, the radius to 7, and the red, green, blue values to 50, 50, 50.

  8. Exceptions:
    (i) For the program below, explain which (if either) catch block captures a thrown exception for negative numbers and why.

    (ii) If we swapped the two catch blocks, explain which (if either) block would capture a thrown exception for negative numbers and why. 
    #include <iostream>
#include <exception>
#include <cmath>

class myExc: public std::exception {
   protected:
      std::string message;
   public:
      myExc(std::string msg) { message = msg; }
     ~myExc() { }
     // says what kind of exception it was
     void what() { std::cout << message << std::endl; }
};

void f(double val)
{
   try {
     if (val < 0) {
        throw myexc("Negative number");
     }
     std::cout << sqrt(val) << std::endl;
   }
   catch (std::exception e) {
      std::cout << "exception happened" << std::endl;
   }
}

int main()
{
   try {
     double userData;
     cin >> userData;
     f(userData);
     std::cout << "Bye!" << std::endl;
   }
   catch (myExc& e) {
      e.what();
   }
}