CSCI 241 -- Spring, 2011

The Final Exam is a 100-point test which counts as 15% of the grade.

It contains multiple-choice and true-false questions as well as some short-answer and coding questions.

You should also look back at the recent homework assignments and at the quiz questions.

What topics are on the final exam?

Here are most of the topics. You may also find something on the test having to do with Quick Sort or some other kind of sorting (not too complicated) that involves recursion.

Linked Lists

• Be able to insert a node into a list in various locations.
• Be able to insert a node in ascending order into a list.
• Be able to delete a node from a list from various locations.
• Be able to search a list.
• Be aware of both singly-linked and doubly-linked lists and of lists that have both Head and Tail pointers.

Stacks and Queues

• Know the type of data structure category that a stack or queue fall into.
• Know the types of errors that can occur when using a stack or queue.
• Be able to add an item to a stack or queue.
• Be able to remove an item from a stack or queue.

Inheritance

• Know what a base and derived class are.
• Know the different types of inheritance (single - multiple) (public, protected, private).
• Know the difference between public, private and protected inheritance.
• Be able to code the header for a derived class.
• Be able to code a constructor for a derived class.
• Know what polymorphism is.
• Know what virtual and pure virtual functions are.
• Know what abstract and concrete classes are.

Templates

• Know how to write a template class or function - and what all of the requirements are.
• Do not be surprised to find template classes in coding questions.

Recursion

• Understand what is involved in recursion.
• Be able to write a simple recursive function to do something. like counting the nodes in a linked list or testing whether two linked lists are equal.

Exceptions

• Know how to use try and catch blocks to throw and process an exception.
• Know how to throw an "out_of_range" exception in particular.
• Know how to code a catch block to rethrow an exception.

Final Exam Practice Questions

1. What are the basic operations we can do with a stack? Write the code for push, pop and empty operations, assuming the stack is implemented as (a) a linked list or (b) a fixed-size array.

2. What are the basic operations we can do with a queue? Suppose we implement a queue as a linked list with head and tail pointers. Write the code for the push and pop operations.
3. Write a recursive function to print the data in the links of a singly-linked list, in reverse order.

4. Why would we use a linked list instead of an array to implement a stack? Or a queue?

5. Suppose I want to store data (not in order) and I want to be able to insert items as fast as possible. What data structure should I use? (Think about fixed-size arrays, dynamic arrays, and linked lists.) If I must store them in order, does the answer change?

6. I want to have a class called Pair which provides ordered pairs (A, B) of elements of type T. It should be a template class. The data elements of class Pair are two items of type T.

7. Can I use the default copy constructor, destructor and assignment operator for Pair?

8. Suppose I want to have a method called MakeMirror which returns a Pair containing the same two elements in the opposite order. (If the current instance contains (A, B), then MakeMirror() gives us (B, A).) Write the prototype statement for MakeMirror.

9. Suppose I want to have a bool-valued function called IsMirror which will return true if two Pair objects contain the same elements in the opposite order. Write the prototype for IsMirror as a friend function.

10. Suppose we have a doubly-linked list made of Nodes. Each Node contains a char and two Node * variables called Next and Back. We have a Head pointer and a Tail pointer. We would like to have a function which will remove all occurrences of a character called Target from the list. Write the code for the function.

11. When do we use the word "protected" in a class definition?

12. Suppose we have a List class which stores bool values, implemented using a dynamic array which is always exactly as large as is needed:

             class ListBool
             {
              private:
               bool * Array;
               int Index;     // Index = size of the list
              public:
               ListBool();
               // probably other things as well, such as operator !=
             };

    Write the code for operator != as a method of the ListBool class.