Warning: This study guide is still in draft form, the definitive version will be updated Friday (Nov 09) morning.

I will add more practice problems as I find new interesting questions, so come back to this page every few days, more practice problems may have appeared.

In addition to all concepts from Test 1,

You should be able to define or explain the following terms:

• class vs instance of a class (i.e. object)
• encapsulation and object invariant
• stack diagram and difference between the function call stack and the heap
• pseudocode
• Abstract data types; interface vs. implementation; advantages to using ADTs
• The List interface, including implementation details and runtime analysis using array lists, linked lists
• Stack interface and operations
• Queue interface and operations
• Dynamic memory management and responsibilities

You should be familiar with the following C++-related concepts:

• Segmentation fault.
• new and delete for basic types, one-dimensional arrays, and two-dimensional arrays
• Role of class destructors and constructors
• different kinds of constructors
• Pointer/array equivalence
• comparison operators
• operator overloading
• parameters passed by reference and returning a reference
• Declaring and using (basic methods only) of STL vector, forward_list, list, stack and queue

Practice problems

1. Write a Student class of Person with the following features:
   • a protected name (string), age (int), major (string) and gradYear (int)
   • a constructor which takes a name, age, and grad, which it uses to initialize the data members, except the major which is initialized to "Undecided".
   • the Student object should have methods getName, getAge, print, setMajor, getMajor and getGradYear. The print function should print on screen a message like: "Siona is a 20 year old Economics major who will graduate in 2019."
   Finally, write a main() function that declares a pointer p to a Person, creates a single Student on the heap and saves the pointer to that Person as p, and then prints the Person and releases its memory.


2. You should be able to implement all of the methods of DoublyLinkedList and ArrayList classes as well as provide a stack trace of a sample main() program. Declare and implement a new method for ArrayIntList , replaceItem(int i, int val), that replaces the existing value at position i with val. It should return the previously held value.


3. Define replaceItem for a DoublyLinkedIntList implementation. Compare and contrast the expected run time with the ArrayIntList implementation.


4. Write a program that prompts the user for an integer n, then reads n strings into an array of strings stored on the heap, prints true if the array is sorted and false otherwise, and then frees the memory on the heap. As part of this program declare and implement a templated boolean isSorted(T* a, int n) function that, given a pointer to an array a and the length of that array n, returns true if the array is sorted and false otherwise.


5. In class, we defined a Queue using various List implementations. Let's flip this around. Consider the following (somewhat strange) List definition, QueueIntList, that uses an awesomely cool MagicIntQueue to represent the data in the list. (Note that the details of MagicIntQueue are not given, but are also unnecessary given what you know about interfaces.)

                 #ifndef STUDYGUIDE_QUEUEINTLIST_H
                 #define STUDYGUIDE_QUEUEINTLIST_H
   
                 #include "list.h"
                 #include "magicIntQueue.h"
   
                 class QueueIntList : public List<T> {
                 private:
                 MagicIntQueue values;
   
                 public:
                 QueueIntList();
                 ~QueueIntList();
                 void insertAtHead(int item);
                 void insertAtTail(int item);
                 int getSize();
                 bool isEmpty();
                 // ...etc. all List methods are declared here
                 };
   
                 #endif //STUDYGUIDE_QUEUEINTLIST_H
               

   Using the above declarations, complete an implementation for the methods getSize(), insertAtHead(T item), and removeTail(). Your answers should be written as they would appear in queueList-inl.h, paying attention to the scope and template operators. Once complete, describe the O() of each of your methods. Again, the details of MagicQueue are not important; you should assume it implements a Queue interface properly in O(1) time.

Home Page