CSCI 161: Practice Final Exam

NAME (print clearly):

CSCI 161: Practice Final Exam

Make sure your name is clearly written on the exam
Answer directly on the exam, extra paper and scrap paper is available if needed.
You have 3 hours to complete the exam
The exam is closed book, closed notes, no electronics are permitted, but you are permitted one double-sided 8.5"x11" reference sheet ("cheat sheet").
There are 8 questions worth 10 marks each, for a total of 80 marks: attempt all questions.
All VIU official rules for writing exams in the gym apply.

Question	Mark
1. Definitions and explanations [10 marks]
2. Memory allocation/deallocation [10 marks]
3. Linked lists [10 marks]
4. Mergesort [10 marks]
5. Binary search trees I [10 marks]
6. Binary search trees II [10 marks]
7. Inheritance [10 marks]
8. Overloading and overriding [10 marks]
Exam Total [80 marks]

Question 1: Definitions and explanations [10]

In your own words, explain the meaning of the term dynamic data type and how it relates to lists, stacks, and queues.

Question 2: Memory handling issues [10]

In the context of a linked list class with suitable constructors and destructors and methods to insert, remove, lookup, and print, describe specifically where and how each of the following memory issues is likely to arise:

a memory leak
a dangling pointer
use of a wild pointer
use of a null pointer likely to cause a run-time crash

Question 3: Linked lists [10]

Given the definition of a typical struct-based linked list below, write the code for the remove function. You can assume the shown lookup function has already been implemented and can be called by your remove.

struct lNode {
   string name, email;  // (data fields for list items)
   lNode* next;
   lNode* prev;
};

struct LList {
   lNode* front;
   lNode* back;
};

// returns a pointer to the first lNode in L whose name matches target
// (returns nullptr if no match found)
lNode* lookup(LList L, string targetname);

// finds and removes the first lNode from L whose name matches target,
//    updating front and/or back if needed
// returns true if the target is successfully found and removed, false otherwise
bool remove(LList& L, string target);

Question 4: Mergesort [10]

(i) Provide an implementation for the merge function below, merging the contents of arr1 and arr2 into target with the assumption that arr1 and arr2 are already sorted in non-decreasing order.

(ii) In your own words, describe how the effiency of merge relates to the combined sizes of arr1 and arr2.

// merges the contents of the first N1 elements of arr1 and N2 elements of arr2
//    into the target array, assuming arr1 and arr2 are already sorted and that
//    target is large enough to hold the results
void merge(float target[], float arr1[], int arr1size, float arr2[], int arr2size)

Question 5: Binary search trees I [10]

Suppose we have code that builds a valid binary search tree of numbers (using our usual approach of smaller values in left subtrees, other values in right subtrees) and is given values to insert in the following sequence:

100 200 300 400 50 150 250 350 450 60 40 20

(i) Sketch the binary search tree that would result

(ii) Show the order the tree contents would be printed in if printing used a preorder traversal.

Question 6: Binary search trees II [10]

Given the definition of a binary search tree class below, and assuming we followed the same rules as described in question 5 with respect to tree structure:

(i) Provide a recursive implementation of the private print method.

(ii) Provide a loop-based implementation of the public biggest method.

// assumes iostream and string are #included and std namespace is in use
class bstree {
   protected:
      struct tnode {
         float data;
         tnode* left;
         tnode* right;
      };
      tnode* root;
      void print(tnode* t); // print all nodes of subtree t in sorted order
      void deallocate(tnode* &t); // deallocate all nodes in subtree t
      tnode* create(float d); // allocate a new tnode with the given info
   public:
      bstree(); // initialize empty tree
      ~bstree(); // deallocate entire tree
      float biggest(); // return the largest data value stored in the tree
      void print(); // print whole tree's data in sorted order
      void insert(float d); // insert a new node, with data value d, into the tree
           // (maintaining valid binary search tree structure)
};

Question 7: Inheritance [10]

For the trio of classes defined further below, identify which of the following fields and methods can and cannot be accessed/called directly from inside class Z's print method and why: xdata, xdebug(), xprint(), ydata, ydebug(), yprint(), zdata, zdebug(), zprint()

class X {
   private:
      int xdata;

   protected:
      void xdebug();

   public:
      void xprint();
};

class Y: protected X {
   private:
      float ydata;

   protected:
       void ydebug();

   public:
       void yprint();

};

class Z: private Y {
   private:
      char zdata;

   protected:
      void zdebug();

   public:
      void zprint();
};

Question 8: Overloading and overriding [10]

Given the class definition below, provide an implementation of the overloaded = operator and explain how/why "this" and/or "*this" are needed in your implementation.

// stores the coordinates of a point in n-dimensions
class nPoint {
   private:
      float* coords; // dynamically-allocated array for the coordinates
      int dims; // number of dimensions (array size)
   public:
      nPoint(); // initializes with null coords and 0 dimensions
     ~nPoint();  // deallocatees coords
      bool set(float c[], int size); // allocates coords and sets dims as copies of c and size
      void print(); // displays current coordinates in form (x1,x2,...)
      nPoint operator=(const nPoint& rhs); // e.g. allows P1 = P2 = P3;
};