312-174

Exam 2 Topics

Spring 2000

Exam date: Thursday, 30 March 2000, 6:30-8:30 PM, Williams 202.

This exam will consist of short answer questions. Some questions will be theoretical in nature, eg "What is the difference between a requirement and a specification", some are mathematical, eg "give the big-oh time of the following function", and some are practical, eg "write a class that ...."

some questions will require you to write code. The code does not have to be perfect (I won't compile your answer!), but must be conceptually correct. For example, forgetting to declare a loop variable is not important, but looping through the correct number of times is important.

The exam will cover chapters 4-7 of the Dale book and labs 6, 7, and 8 of the Roberge book. You are responsible for all of the material in the book chapters and in the labs unless I explicitly exempt material below.

The topics covered on this exam are listed below.

Chapter 4:

1. Know how queues are implemented using both arrays (as in the book) and dynamically (as in lab).

2. Know how to use queues in an application (as in the in-lab exercise).

3. Know how to simulations using queues as we did in lab.

4. Know how to use pointers. Be able to use pointers to implement data structures (such as queues). Know how arrays and pointers are related and be able to use pointer arithmetic to iterate through arrays.

5. You are not directly responsible for stacks (they were covered in the last exam).

Chapter 5:

1. dynamic implementation of stacks and queues.

2. Be able to do big-O analysis of your code.

Chapter 6:

1. Implementation of circular linked lists (as done in lab 8 also)

2. Implementation of doubly linked lists (also done in lab 8).

3. The difference between deep and shallow copying.

4. Know the situations when c++ automatically uses shallow copy:
   • passing parameters by value,

   • returning an object as the value of a function (return yourStack;)

   • initializing a variable in a declaration (StackType myStack = yourStack)

   • Class copy constructors.

   • implementing the assignment operator (stack1 = stack2;)

5. Overloading the assignment operator to make deep copies.

6. Inheritance.
   • Base classes vs derived classes.

   • composition vs inheritance: what's the difference and why it's important.

   • Be able to create something like the countedQueue class that we did in class.

   • Virtual functions: run-time binding. Understand this concept and how its used.

Chapter 7:

1. Recursion. Be able to create recursive functions.

2. Analysis of recursive functions.

3. Verifying that recursive functions work using Dale's three-question method (see page 400).

4. Implementing binary search, insertItem, deleteItem, RevPrint functions. Know how to analyze these functions.

5. How recursion works: static storage allocation vs dynamic storage allocation.

6. Turning tail recursion into iteration.

7. Turning other types of recursion into iteration (stacking).

8. QuickSort and its analysis.

Return to Student Pages

Return to John Barr's Home Page

Last Modified: 23 March 2000

THIS PAGE MAINTAINED BY:
John Barr, Ithaca College