Practice exam 1

The first 6 questions are multiple-choice. Circle the response that best answers each question. (5 points each)

1.

A function funky() is declared with preconditions and postconditions. Which of the following statements is true?

(a)

the calling function is responsible for meeting the preconditions

(b)

funky() is responsible for meeting the preconditions

(c)

funky() must call assert() to make sure that the preconditions are met

(d)

both (b) and (c) are true

2.

Suppose that a bag is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time? (A constant time is not dependent on the number of items in the Bag.)

(a)

insert()

(b)

count()

(c)

erase_one()

(d)

None of (A), (B), and (C) have a constant worst-case time

(e)

TWO of (A), (B), and (C) have a constant worst-case time

(f)

ALL of (A), (B), and (C) have a constant worst-case time

3.

Suppose that the + operator which combines two bags is not declared as a member function of the bag class. How can this function access the private data members of the two bags passed as arguments?

(a)

It cannot.

(b)

The operator can be declared as a friend to the class.

(c)

The operator can be implemented in the header file containing the bag class definition.

(d)

The operator can be implemented in the same implementation file as the bag class.

4.

Suppose cursor points to a node in a linked list (using the node class definition with member functions data() and link()). What Boolean expression will be true when cursor points to the tail node of the list?

(a)

(cursor == NULL)

(b)

(cursor->link() == NULL)

(c)

(cursor->data() == NULL)

(d)

(cursor->data() == 0.0)

(e)

None of the above.

5.

Here is a small function that uses the dynamic bag class from Chapter 4:

         void quiz( )
         {
             bag::size_type i;// Line 1
             bag b;           // Line 2

             b.insert(42);    // Line 3
             i = b.size( );   // Line 4
             cout << i;            // Line 5
         }

When is the bag b's dynamic array allocated?

(a)

During the execution of Line 2.

(b)

During the execution of Line 3.

(c)

Just after Line 4 and before line 5.

(d)

After Line 5.

6.

Suppose that funky() is a function with a prototype like this:

         void funky(________ head_ptr);
         // Precondition: head_ptr is a head pointer for a linked list.
         // Postcondition: The function funky has done some manipulation of
         // the linked list, and the list might now have a new head node.

What is the best data type for head_ptr in this function?

(a)

node

(b)

node&

(c)

node*

(d)

node*&

7.

(25 points) Consider a function named remove() that has the following specification (assume that node is a class with member functions data(), link(), and set_link()):

void remove(node*& head_ptr, const node::value_type& target);
//PRE:  head_ptr is the head pointer of a non-empty linked list.  The
//      list contains at least one occurrence of target.
//POST: the node containing target that is closest to the head of the
//      linked list has been removed

Fill in the following outline to produce a full implementation of the remove() function.

void remove(node*& head_ptr, const node::value_type& target){
// Declare two local pointers, p and previous
// Initialize p to point to the head of the list; initialize previous to NULL





// Move p down the list until it points to the first node containing target.
// Each time you move p down the list, move previous down the list as well
// so that it always points to the node previous to p





// If previous equals NULL, make head_ptr point to the node
// that comes after p.
// Otherwise, make the node previous to p point to the node that comes after p




// Delete the node pointed to by p


}

8.

(15 points) In chapter 4, the bag was implemented using a dynamically-allocated array. The class definition for the bag contains these private member variables:

private:
  value_type *data;
  size_type used;
  size_type capacity;

Suppose there is no copy constructor defined for this class. Draw a picture and provide a short explanation of what can go wrong if a bag object is passed as a value parameter to a function.

9.

(30 points) Given the following class defintion:

class foo
{
  public:
          foo();
          void one() const;
          foo two(int i);
          friend foo f(foo x);
  private:
          int size;
};

A client program declares two foo objects named a and b. A statement is ``legal'' if it compiles without error. Answer each of the following questions YES or NO.

(a)

Is the statement

a = b;

legal in the client program?

(b)

Is the statement

a.one();

legal in the client program?

(c)

Is the statement

a = two(10);

legal in the client program?

(d)

Is the statement

a.size = b.size;

legal in the client program?

(e)

Is the statement

x.size = 0;

legal in the function f?

(f)

Is the statement

size = 0;

legal in the function one?