CSCI 161: Spring 2026 Final Exam (Prof. D. Wessels: Sections N01/N02)

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]

1. dynamic data types
2. abstract data types
3. inheritance

1. a memory leak
2. a dangling pointer
3. use of a wild pointer
4. use of a null pointer likely to cause a run-time crash

// assumes string and iostream are included, std namespace is in use
struct listnode {
   int data;
   listnode* next;
   listnode* prev;
};

int main()
{
   listnode* front;
   listnode* back;
   string entry = "";
   listnode* tmp = nullptr;
   back = nullptr;

   do {
      cout << "Enter numbers to insert them into the list, or" << endl;
      cout << "P to print the list, R to remove a number, Q to quit" << endl;
      int i;
      cin >> i;

      if (cin.fail()) {
         // not an integer, read as a command string
         cin.clear();
         cin >> entry;
         if ((entry == "P") || (entry == "p")) { // it was a print command
            tmp = front;
            cout << "list contents:";
            while (tmp) {
               cout << " " << tmp->data;
               tmp = tmp->next;
            }
            cout << endl;
         } else if ((entry == "R") || (entry == "r")) { // it was a remove command
            if (front) {
               front = front->next;
               if (front) {
                  delete front->prev;
                  front->prev = nullptr;
               } else back = nullptr;
            }
         }
      } else { // insert the number in a new node at the back of the list
         tmp = new listnode;
         tmp->data = i;
         tmp->next = nullptr;
         tmp->prev = back;
         if (front == nullptr) front = tmp;
         else back->next = tmp;
         back = tmp;
      }
   } while ((entry != "Q") && (entry != "q"));

   while (front) {    // deallocate all remaining listnodes
      front = front->next;
      if (front) delete front->prev;
      else delete back;
   }
}

// linked list of nodes, each with a number and text string in their data
// assumes iostream and string are #included and std namespace is in use
class LList {
    protected:
       struct lnode {
          double num;
          string text;
          lnode* next;
       };
       lnode* front;

    public:
       LList(); // initialize an empty list
      ~LList(); // deletes each node in the list
       void print(); // prints all nodes in the list

       // inserts new node at front of list
       void insert(double d, string s);

       // removes and deletes node from front of list
       //    (no effect if list is already empty)
       void remove();
};

// assumes iostream and string are #included and std namespace is in use
class bstree {
   protected:
      struct tnode {
         float num;
         string str;
         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 n, string s); // allocate and return a new tnode with the given field values
   public:
      bstree(); // initialize empty tree
      ~bstree(); // deallocate the tree content
      string lookup(float n); // find the node with num field n and return its str field, "" if not found
      void print(); // print whole tree's data in sorted (by num) order
      void insert(float n, string s);
};

class parent {
   private:
      // ... parent private fields and methods

   protected:
      // ... parent protected fields and methods

   public:
      // ... parent public fields and methods

};

class child: protected parent {
   private:
      // ... child private fields and methods

   protected:
      // ... child protected fields and methods

   public:
      // ... child public fields and methods

};

class grandchild: public child {
   private:
      // ... grandchild private fields and methods

   protected:
      // ... grandchild protected fields and methods

   public:
      // ... grandchild public fields and methods
};

// class to represent a dynamically-allocated char array,
// assumes iostream and cstring libraries are #included
class text {
   protected:
      int size;
      char *content;
   public:
      text(const char* str = "");
      ~text();
      text operator=(const text &rhs);
      void print();
};

// sample main using the text class methods
int main() {
   text s("hello world");
   s.print();
   text t = s;
   t.print();
}

// implementation of text class methods
text::text(const char* str) {
   size = strlen(str);
   content = new char(size);
   strcpy(content, str);
}

text::~text() {
   if (content) {
      delete content;
   }
}

void text::print() {
   std::cout << content << std::endl;
}

text text::operator=(const text &rhs)
{
   // implementation to be completed by student