CS 311 Fall 2007  >  Midterm Exam Review Problems, Part 1

CS 311 Fall 2007
Midterm Exam Review Problems, Part 1

This is the first of three sets of review problems for the midterm exam. For all three sets, see the class web page, or the following links:

Midterm Exam Information

The midterm exam will be given in class on Wednesday, October 24. It will be worth 75 points. The exam will cover all the material of the class from the beginning through Monday, October 22.

Referring to books, notes, electronic devices, or other people during the exam will not be permitted.

Problems

Review problems are given below. Answers are in the Answers section of this document. Do not turn these in.

  1. When we define a (non-templated) class, we generally use multiple files. Indicate what each of these files is called and what it is for.
     
  2. Your instructor has been known to remark that, since we have entered the age of “generic programming”, the fact that certain data structures and algorithms may be complex and difficult to implement is no longer a good reason to avoid them. What is he talking about?
     
  3. What is “abstraction” and why do we use it?
     
  4. What is an “invariant”?
     
  5. Briefly explain the basics of “Design by Contract”. (Hint: pre & post.)
     
  6. Write reasonable preconditions and postconditions for the following function: 
    double myFunc(int * p)
{
    p[0] = 5;
    p[2] = int(std::sqrt(p[1]));
    return 6.2;
}

     
    1. What is a “class invariant”?
    2. How can the use of well chosen class invariants make coding easier?
    3. In terms of class invariants, what is a constructor for?
       

     
  8. Write reasonable class invariants for the following class, which maintains an array whose size is stored in the data member n_. Hint: The destructor is already written. Write your invariants so that the destructor is correctly written. 
    class MyClass {
public:
    // Ctors, dctor

    // Default ctor & ctor from int
    // Pre:
    //     theSize > 0
    // Post:
    //     n_ == theSize
    // May throw std::bad_alloc
    explicit MyClass(int theSize = 10):
        p_(new int[theSize]),
        n_(theSize)
    {}

    // Dctor
    // Pre: None.
    // Post: None.
    // Does not throw
    ~MyClass()
    { delete [] p_; }

private:
    // No copy ctor, copy assn
    MyClass(const MyClass & other);
    MyClass & operator=(const MyClass & rhs);

public:
    // General public functions

    [Various functions go here]

private:
    // Data members
    int * p_;
    int n_;
};

     
  9. List the three ways of passing a parameter (or return value) in C++. For each, indicate:
     
  10. Suppose you are writing a numeric class MyNum, which should act something like the built-in type double. You have already written operator*=. Write binary operator* for this class. You may assume that MyNum has a copy constructor (but you should only use it when necessary). Include pre- and postconditions.
     
  11. List the four primary member functions that C++ compilers will silently write. For each, indicate when the compiler writes it for you. (Don’t worry about the address-of operator.)
     
  12. For each of the following operators, indicate whether we should declare it as a member or a global function and how the parameter(s) should be passed (by value, etc.). Briefly justify your answers.
    1. operator+=.
    2. Binary operator+.
    3. operator<< (for stream output).

     
    1. What are the “Big Three”?
    2. What is the “Law of the Big Three”?
    3. In what circumstances do we usually need to write the Big Three?
    4. If we do not write the Big Three, then who does?

     
    1. What does it mean to “own” a resource?
    2. What does “RAII” stand for, and what is it?
    3. Give two examples of resources what it means to release each one.
    4. How can ownership of a resource be shared?

     
  15. Suppose you are writing a class Widget that has two data members, a bool called valid_ and an int * called p_. If valid_ is true, then p_ points to memory, allocated with new [], which the object owns. If valid_ is false, then the value of p_ is unknown. Write the destructor for class Widget. Include preconditions and postconditions. You may assume that the information above is already in the class invariants.
     
    1. In C++ programming we typically access containers, and ranges of data items, through what kind of object?
    2. What operations are typically defined on the objects from part a?

     
  17. In “modern” C++ programming, how do we usually pass a list of values to a function?
     
    1. What is an “iterator”?
    2. List some things we use iterators for.

     
  19. Suppose we have a variables v1 and v2, declared as follows: 
    const std::vector<int> v1(SIZE);
std::vector<int> v2(SIZE);
    1. Write an iterator-based loop that prints the items in v1, each on a separate line.
    2. Using one of the Standard Template Library algorithms, write a single function call that copies the data in v1 to v2. Note that they are already the same size.

     
    1. What do we mean by an “error condition” (often just “error”)?
    2. List three ways of signalling an error.

     

Answers

  1. We define a class using:
  2. Generic programming means writing code for data structures and algorithms so that it can be used with a variety of types. (C++ templates and the Standard Template Library facilitate generic programming.) In the bad old days, no one could write an implementation that would work in all situations, so if you wanted a fancy data structure that was appropriate for your needs, you had to write it yourself. Now, with generic programming, high quality implementations of good data structures and algorithms can be made available for use in many situations. Thus, first, it becomes worth the trouble to implement complex data structures and algorithms. Second, good implementations are more likely to be available. Therefore, complexity of implementation is no longer an excuse for failing to use the best data structures and algorithms.
  3. Abstraction means separating the purpose and interface of a module from its implementation. Abstraction has a number of advantages, most of which involve the fact that, when we use abstraction, clients typically do not deal with the implementation at all. Thus, the implementation can be changed (bug fixes, etc.) without breaking client code. Furthermore, implementation decisions can be made without consulting everyone involved.
  4. An invariant is a condition that is always true at a particular point in a program.
  5. In Design by Contract, functions have “preconditions” and “postconditions”. A precondition is a statement that must be true when the function is called. A postcondition is a statement that will be true when the function returns (assuming the preconditions were true when it was called). Thus, the operation of a function is described as a contract: the function says to its caller, “I will fulfill my postconditions if you fulfill my preconditions.”
  6. Preconditions Postconditions
    1. A class invariant is an invariant that holds for an object of the class outside of public member functions. That is, it is a precondition of all public member functions, except constructors, and it is a postcondition of all public member functions except the destructor. Generally class invariants are statements about a class’s data members that tell what it means for an object to be in a valid (usable) state.
    2. The existence of class invariants means that public functions can make certain assumptions (usually about class data) when they are called. And it is always easier to code when you know something about the environment your code will be executed in.
    3. The job of a constructor is to make sure that all class invariants hold for the constructed object.
  8. Class invariants:
  9. The three methods are passing by value, by reference, and by reference-to-const.

    Passing by value:

    Passing by reference:

    Passing by reference-ro-const:

  10. operator* for class MyNum should be global: 
    // operator* for MyNum
// Multiplies two MyNum's
// Pre: None.
// Post: Return value is the product of a, b
MyNum operator*(const MyNum & a, const MyNum & b)
{
    return MyNum(a) *= b;
}
    Or, if you do not like squishing everything into one line, you could do it this way. This might be a little slower: 
    MyNum operator*(const MyNum & a, const MyNum & b)
{
    MyNum result = a;
    result *= b;
    return result;
}
  11. Silently written member functions:
    1. We generally want operator+= to be a member function. First, we have no reason to make it a global. Second, this operator is tightly tied to its first argument (which it generally modifies), and provides basic functionality (operator+ is usually written to use operator+=). Its parameter (the second argument) should generally be passed by reference-to-const. This ensures that it can be called with a const object, avoids making an unnecessary copy, properly handles derived types and virtual function calls, and allows for implicit type conversions, where defined. This operator should generally be something like this: 
      Foo & Foo::operator+=(const Foo & other);
    2. We generally want binary operator+ to be a global function, to allow for implicit type conversions on both arguments. Its parameters should generally be passed by reference-to-const, for the same reasons as in part a. This operator should generally be something like this: 
      Foo operator+(const Foo & a,
              const Foo & b);
    3. We must declare the stream output operator as a global function; it cannot be a member, because it would have to be a member of std::ostream, and we are not allowed to create new members of this class. Its first parameter (the stream) should be passed by reference, since we modify it. Its second parameter (the value to be output) should be passed by reference-to-const for the same reasons as in part a. This operator should generally be something like this: 
      std::ostream & operator<<(std::ostream & theStream,
                          const Foo & printMe);
    1. The Big Three are the copy constructor, copy assignment, and destructor member functions in a C++ class.
    2. The Law of the Big Three says that if you write one of the Big Three, then you probably need to write them all.
    3. We generally need to write the Big Three when our class owns a resource. The most common such resource is dynamically allocated memory/objects.
    4. The Big Three are silently written by the compiler, if we do not declare them.
    1. To own a resource means to be responsible for it, in particular, for releasing it.
    2. RAII stands for “Resource Acquisition is Initialization”. It refers (somewhat misleadingly) to the idea that a resource should be owned by an object, and therefore released by the object’s destructor.
      • Dynamically allocated memory. deleteing a pointer to it.
      • An open file. Closing it.
      Other answers are possible.
    4. The usual way to share resource ownership is by reference counting. A reference count keeps track of the number of owners of a resource. It is incremented when ownership is granted to a new object, and decremented when an object relinquishes ownership. When the reference count reaches zero, the resource is released.
  15. // Dctor
// Pre: None.
// Post: None.
~Widget()
{
    if (valid_)
        delete [] p_;
}
    The destructor has preconditions, of course, but they are all class invariants, and so do not need to be given here. The only postcondition is that the memory was deallocated, and this is implied by ownership of the memory, which should be a class invariant. Thus, postconditions do not need to be given here either (although you may want to give them, just to be helpful).
    1. In C++ programming, we typically access containers using iterators.
    2. Typically, we define at least the following operations on iterators:
      • Assignment.
      • Equality/inequality test.
      • Increment.
      • Dereference.
  17. We pass a list of values by passing two iterators: one pointing to the first item in the list, and another pointing just past the last item in the list.
    1. An iterator is an object that acts like a pointer. In particular, it is a pointer-like object that is used to access items in some data set, and which does not own what it points to.
    2. We use iterators to iterate over the items in a container (thus the name). We also use them to specify ranges of data.
    1. We use the usual iterator-based loop. We must use a const_iterator, since v1 is const. 
      for (std::vector<int>::const_iterator citer = v1.begin();
     citer != v1.end();
     ++citer)
{
    std::cout << *citer << std::endl; // Must #include <iostream>
}
      We could also declare the iterator outside the loop. 
      std::vector<int>::const_iterator citer;
for (citer = v.begin();
     citer != v.end();
     ++citer)
{
    std::cout << *citer << std::endl;
}
    2. We can copy using std::copy. 
      std::copy(v1.begin(), v1.end(), v2.begin()); // Must #include <algorithm>
    1. An error condition is a condition that occurs at runtime; it is something that cannot be handled by the normal flow of execution. Alternate Answer: An error condition exists when an operation fails to complete successfully.
    2. We can signal an error in three ways:
      • Using a return code.
      • Setting a flag that can be checked later.
      • Throwing an exception.

CS 311 Fall 2007: Midterm Exam Review Problems, Part 1 / Updated: 21 Oct 2007 / Glenn G. Chappell / ffggc@uaf.edu Valid HTML 4.01!