Topics for the first midterm

The first midterm exam will cover the introductory material on C++ from lecture notes 1-6, chapter 3, and chapter 4.

The main preparation for the exam is to complete the first three programming assignments. Those assignments will force you to grapple with most of the key concepts we have covered. You should also make sure that you read the relevant sections in the text. Those sections are

Chapter 3: 3.1, 3.2, and 3.7

Chapter 4: 4.1, 4.2, 4.4, and 4.5.

Sample exam questions

1. The picture below illustrates a variant on the singly linked list, called the circular linked list.

In this structure the list is composed of nodes, as usual, but now the nodes are always linked together in a circle, with the last node pointing back to the first. The list class itself maintains a single pointer to the node at the tail of the list.

Write a class declaration for the node class for this data structure, and then write the code for these two methods in a CircularList<T> class

void addToTail(const T& item);
void removeFromFront();

Be sure to handle special cases, such as adding an item to an empty list.

Solution

2. Below you will find a pair of class declarations for a stack class and a node class to go with the stack. In this version of the stack class the stack is implemented as a list of nodes, where each node points to the node below it on the stack. The stack class itself then just consists of a pointer to the node at the top of the stack.

template <typename T>
class stackNode
{
public:
  stackNode(const T& el);
  
  T data;
  stackNode<T>* ptr;
};

template <typename T>
class stack
{
public:
  stack();
  ~stack();
  
  void push(const T& el); // Push a new data item on the stack
  bool isEmpty(); // Return true if the stack is empty
  T top(); // Return a copy of the data item on the top
  void pop(); // Remove the top of the stack
private:
  stackNode<T> *topPtr; // Pointer to the top of the stack
};

Write the code for the push() and pop() methods.

Solution

3. A singly linked list class is implemented using nodes of type

template <typename T>
class node {
  public:
    T data;
    node<T> *next;
    
    node() : next(nullptr) {}
    node(const T& item, node<T> *ptr = nullptr) :
      data(item), next(ptr) {}
};

The list class itself contains pointers head and tail that point to the two ends of the linked list. Write the code for a method

void remove(const T& el);

in the list class that will remove all of the nodes from a list whose data member is el.

Solution

4. Using the same classes as in problem 3, write the code for a method

void push_back(const T& el);

in the list class that adds a new node to the back of the linked list.

Solution

5. Using the same classes as in problem 3, write the code for a method

list<T>& operator=(const list<T>& other);

in the list class that is used to assign another list to a list.

Solution