COSC 2436 - Data Structures
Bob Comer, Professor of Computer Studies

Exam 1 will cover Chapters 1-5, and sections 6.1 - 6.3 in Chapter 6. I recommend that you do the following exercises as you study the chapters in the textbook. Answers to the Quick Quiz exercises are in Appendix F at the back of your textbook. Questions marked with an asterisk (*) have answers or additional comments - click here to view them.

The exam will emphasize both C++ coding and concepts. Be sure to review the Summary (Chapter Notes, Programming Pointers, and ADT Tips) at the end of each chapter. Following is a sample question over concepts.

Give a brief description of pass-by-value and pass-by-reference. In what situations should pass-by-value be used? In what situations should pass-by-reference be used?

Chapter 1

Quick Quiz 1.5: 1-2, 4-18.

Other questions and comments

1. How are preconditions and postconditions used?

2. Overview of C++.

Chapter 2

Quick Quiz 2.3: 2-5, 10, 12.

Quick Quiz 2.4: 1-3, 5-15.

Other questions and comments

1. What is a pointer? What does a pointer store? What does it mean to dereference a pointer?

2. How is the new operator used to dynamically allocate memory?

3. Know how to use the typedef statement and what it does.

4. What is data abstraction?

5. Given:

int i = 5,
    j = 8;

Write declarations for two variables called ptr1 and ptr2 that can hold the address of an integer (int). Store the address of i in ptr1 and the address of j in ptr2.

6. Using the variables from the previous question, write code to print the values stored in i and j using the pointer variables ptr1 and ptr2.

7. Using the variables from question 5, write code that will copy the value stored in the memory location pointed to by ptr2 in the memory location pointed to by ptr1.

8. Write C++ code to dynamically allocate an integer and store its address in pointer variable intPtr. Then store a value of 100 in the integer and print the integer. Include the declaration for the pointer variable.

9. Write code to free the memory that was dynamically allocated in the previous problem.

Chapter 3

Quick Quiz 3.2: 1-10.

Add a question like print array element.

Section 3.3 Multidimensional arrays - I will not cover multidimensional arrays on the exam, but this is interesting material.

Quick Quiz 3.4: 1-8, 10.
I will not cover using function names as parameters on this exam.

Quick Quiz 3.5: 1-8.

Other questions and comments

1.* Given the array declaration:

int list[5] = { 10, 20, 30, 40, 50 };

cout << *(list+2) << endl;

2. What is an ADT?

3. What is an array?

4. What is the relationship between arrays and pointers?

5. How do we dynamically allocate an array?

6. How do you use a dynamically allocated array?

7. How do you free the memory used by a dynamically allocated array?

8. Are C-style structs compatible with object-oriented programming?

9. How are C++ arrays and C-style structs similar? How are they different?

10. Write C++ code to input an integer called n and then dynamically allocate an array of n double values. Store the address of the array in pointer variable dblPtr. Include declarations for all variables that you use.

11. Write code to free the memory that was dynamically allocated in the previous problem.

Chapter 4

Quick Quiz 4.1: 1-5.

Quick Quiz 4.2: 1-9.

Quick Quiz 4.5: 1-13.

Other questions and comments

1. Know how to write a declaration for a simple class. Why should most data members be private? why should most member functions be public?

2. Know how to write basic mutator (set) member functions. Know how to write basic accessor (get) member functions.

3. Know how to write a constructor for a class. You should be able to write multiple constructors for a class - a default constructor (with no parameters) and constructors with parameters.

4. Know how to overload a "simple" binary operator for a class. See: http://www.austincc.edu/comer/ds10f/binaryop.htm

5. What is the "this" pointer?

6. Know how the assert() mechanism works.

7. What is a const (constant) member function?

8. What is a class invariant?

9. What is information hiding?

10. Create a class called Point for a point (x,y) in a Cartesian coordinate system. All data members should be private. All function members should be public. The function definitions (implementation) should be placed outside the class definition. Inside the function definition you should only have function prototypes. Your class should include the following:

    a. Private data members for the point x and y coordinates (float values).

    b. A default (no argument) constructor that sets the x and y values of the new point to zero.

    c. An explicit-value constructor that has two parameters - an initial value for the x coordinate and an intial value for the y coordinate.

    d. A void member function called set that stores new values in the x and y coordinates. It should have two parameters - the new value for the x coordinate and the new value for the y coordinate.

    e. A constant member function called getX that returns the value of the x coordinate.

    f. A constant member function called getY that returns the value of the y coordinate.

    g. A constant member function called display that displays a point in the standard "(x,y)" format. This function should have one parameter - the output stream where the point should be displayed.

    h. Overload the insertion operator << to display a point. This operator can only be voerloaded with a non-member function.

    i. A constant member function called getMagnitude that returns the distance from the origin (0,0) to the point. The distance is the square root of the sum of x squared and y squared.

    j. Overload the + operator for the Point class as a member function. The sum of two Points is the Point whose x coordinate is the sum of the x coordinates of the arguments, and whose y coordinate is the sum of the y coordinates of the arguments.

Write a driver program to test your class.

11. Overload the + operator for the Point class from question #10 using a member function. Can you use the driver from question #10 to test this function?

12. A class called Box has 3 data members: length, width and height (double values). Write an overloaded + operator for the Box class as a non-member function. The sum of two boxes is a Box that is barely large enough to hold the two boxes stacked on top of each other. That is, the sum is a Box whose:

    length is the maximum of the lengths of the argument Boxes.

     width is the maximum of the widths of the argument Boxes.

     height is the sum of the heights of the argument Boxes.

Chapter 5

Quick Quiz 5.1: 1-24.

Quick Quiz 5.2: 1-9.

I expect you to read and understand the material in sections 5.1 and 5.2. I expect that you should be able to perform basic input from the keyboard and basic output to the monitor. You should also know how to perform basic file input and output, although this may not be required for the class.

In Table 5.2 I expect that you should be familiar with the use of: the extractor operator >>, the get function for inputting character data, the getline function for inputting strings and the ignore function.

In Table 5.3 I expect that you should be familiar with the use of: the insertion operator <<.

In Table 5.4 I expect that you should be familiar with the use of: fixed, endl, left, right, setprecision(n) and setw(n).

For the string class, I expect that you should be familiar with: basic input and output operations, finding the length, comapring strings, concatenating strings and assigning strings.

It is good to be familiar with the use of C-strings (character arrays), but you may not need them in this class.

Section 5.4 Pattern Matching - This section will not be covered on the exam.

Section 5.5 Data Encryption - This section will not be covered on the exam.

Chapter 6

Quick Quiz 6.3: 1-16. * Two of the answers in this section are missing, and the rest are mis-numbered, so I have added the answers on the Review 1 Answers page (see above).

Other questions and comments

1. Know how to implement a List class using a "static" array (an array declared as a List member). Pay particular attemtion to how the List items are stored in the array.

2. Know how to declare a List class using a dynamically-allocated array (a pointer to the array is the List member)

3. Know how to write a class destructor function. What is the purpose of a destructor? When is it called?

4. Every class has a copy constructor. If the class programmer does not write a copy constructor, C++ creates a default copy constructor. What is the purpose of a copy constructor? When is it used (called)? What does a default copy constructor do? When does a class programmer need to write a "customized" copy constructor for a class?

5. What does the default assignment operator for a class do? When does a class programmer need to write a "customized" assignment operator for a class?

6. Given the array-based implementation of a list from section 6.2 of the textbook with mySize = 4, where is the first element of the list stored? Where is the last element of the list stored?

7. Given the array-based implementation of a list from section 6.2 of the textbook with mySize = 4: Inserting an element in a list can cause data to be moved in the array that holds the list elements. What insertion position will cause the most data shifting? How many elements will have to be moved in this case?

Return to Data Structures Home Page

Copyright: © 2015 by the Austin Community College
Department of Computer Studies. All rights reserved.
Comments to: Bob Comer
Last updated: February 25, 2015