Warning: This study guide is still in draft form, the definitive version will be updated no later than Sunday (April 18) morning.

I will try to 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
• stack diagram and difference between the function call stack and the heap (dynamic memory)
• 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
• Dynamic memory management and responsibilities

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

• Segmentation fault -- memory errors caused by invalid memory accesses
• new and delete for basic types and one-dimensional arrays
• Role of class destructors and constructors
• Roles of keywords protected and public
• different kinds of constructors
• Pointer/array equivalence
• this pointer
• comparison operators
• operator overloading
• parameters passed by reference and returning a reference

Practice problems

1. As usual completing any lab problem you did not complete before is always good practice.
2. Write a Student class 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 two variables. First, declare a variable of type Student (make sure you give the constructor the proper arguments), then declare a variable of type pointer to Student and assign a dynamically allocated Student object to it. Then, call setMajor from the Student pointer.


3. Draw a stack diagram of the state of memory when the constructor for the first Student variable just started.


4. Draw a stack diagram of the state of memory when the call to setMajor is just about to end (you are still in the method, but all the code has been executed).


5. You should be able to understand and explain implement all of the methods of DoublyLinkedList and ArrayList classes as well as provide a stack diagram of a sample main() program.
6. 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.


7. Implement replaceItem for a DoublyLinkedIntList implementation. Compare and contrast the expected run time with the ArrayIntList implementation.


8. Write a program that prompts the user for an integer n, then reads n strings into a dynamically allocated array of strings, 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 boolean function isSorted(string* 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.


9. Draw a stack diagram of the state memory at the place indicated in the following code snippet:

    #include "doublyLinkedList.h"
    using namespace std;
   
    int main() {
       DoublyLinkedIntList dlList;
       dlList.insertAtTail(5);
       dlList.insertAtHead(7);
       dlList.insertAtTail(3);
       dlList.insertAtHead(8);
       dlList[2] = 8;
       // Draw stack diagram here
       for (int i=0; i<dlList.getSize(); i++) {
          cout << dlList[i] << " " << flush;
       }
       cout << endl;
       return 0;
    }