Sample Final Examination, COM1101, Spring 1999


Problem 1. Suppose you are writing an organizer/day planner program. Among other things, you need to manage the user's appointments. An appointment has a date, time of the day and a short description. Write a class to represent an appointment. Write the member functions that will allow to change the date, the time and the description of an existing appointment, and the member function that prints the info about the appointment nicely formatted.

Problem 2. Assume the following declarations of functions foo(..), bar(..), boo(..). Describe the results of calling these functions ob the string ``abracadabra'' as in

  string str = "abracadabra";
  foo(str);   // respectively, bar(str) and boo(str)
  cout << str << endl;
If you think a function is illegal, explain why you think so.
  void foo( const string & s )
    for( int i=0; i < s.length(); i++)
      if( s[i] == 'a' ) s[i] = 'A';
  }

  void boo( string s )
    for( int i=0; i < s.length(); i++)
      if( s[i] == 'a' ) s[i] = 'A';
  }

  void bar( string & s )
    for( int i=0; i < s.length(); i++)
      if( s[i] == 'a' ) s[i] = 'A';
  }

Problem 3. Assume the following definition of a singly linked list.

template< class T >
struct Node {
  T data;
  Node<T> * next;

  Node( const T& d, Node<T> * n ) :
    data(d), next(n) {}
};

template< class T >
class List {
  Node<T> * first;

public:
  List() : first(NULL) {}
  //...
  void add( const T& d ){
    first = new Node<T>( d, first );
  }
  void remove( int pos );

};

For example, the code

  List<int> l;
  l.add(40);
  l.add(30);
  l.add(20);
  l.add(10);
will produce
  +----+    +----+    +----+    +----+
  | 10 |    | 20 |    | 30 |    | 40 |
  +----+    +----+    +----+    +----+
  |  --+--->|  --+--->|  --+--->|  --+-> NULL
  +----+    +----+    +----+    +----+

(a) Using this definition, write a member function

   T List<T>::nth( int n )
that returns the n-th item in the list. If the list is shorter than n items, report an error. In the above example l.nth(1) returns 20.

solution

(b) Write a member function

   int List<T>::find_first( const T& item )
that returns the position at which the item first occurs in the list. If the item is at the first node, this function returns , returns 1 if the item is the second node etc. If the item does not occur in the list at all, the function returns -1. In the above example l.find_first(30) returns 2, l.find_first(7) returns -1.

solution

(c) Write the code to implement the member function remove(int pos), which removes the element at position pos. If the list is shorter than pos elements, remove the last element (if the list is empty, do nothing). In the above example, after l.remove(2) the list becomes

  +----+    +----+    +----+
  | 10 |    | 20 |    | 40 |
  +----+    +----+    +----+
  |  --+--->|  --+--->|  --+-> NULL
  +----+    +----+    +----+

(d), extra Write a member function

   void List<T>::remove_all_such( const T& item )
that removes all items equal to item from the list. For example, if we had a List<string> lst
  +----+    +----+    +----+    +-----+   +----+   +----+
  |"to"|    |"be"|    |"or"|    |"not"|   |"to"|   |"be"|
  +----+    +----+    +----+    +-----+   +----+   +----+
  |  --+--->|  --+--->|  --+--->|   --+-->|  --+-->+  --+-> NULL
  +----+    +----+    +----+    +-----+   +----+   +----+
then after lst.remove_all_such( "to" ) it would be
  +----+    +----+    +-----+   +----+
  |"be"|    |"or"|    |"not"|   |"be"|
  +----+    +----+    +-----+   +----+
  |  --+--->|  --+--->|   --+-->+  --+-> NULL .
  +----+    +----+    +-----+   +----+

Problem 4. The following are code fragments for a table of strings, which can hold up to 100 entries. Strings (we will call them values) can be added, looked up and printed.

const int MAX_TABLE_SIZE = 100;       // max capacity

class StringTable {
  int idx;                           // the number of actual entries,
    				     //  the index of the first free slot
  string values [MAX_TABLE_SIZE];
public:
  //....
  //....
  void add( const string& new_val );  // add a value
  bool contains( const string& val ); // true if val occurs in the
                                      //   table, false otherwise.
  void print();                       // print all values
};

void StringTable::add(const string& s){
    if( idx == MAX_TABLE_SIZE ){
      // capacity exhausted -- signal error and abort
    }
    else{
      values[ idx ] = s;              // add the value
      idx++;                          // increment the size
    }
}

For the following problems, write the code of the required member functions using correct syntax for out-of-class definitions.


(a) The above code defines no constructors. Write one. It should make the table initally empty.

(b) With the member functions as declared above, is it possible to determine which position in the table a string occupies after it has been added? Explain.

(c) Write the member functions bool contains(..) and void print().

(d) The following code reads words (words are separated by whitespace, i.e. spaces, newlines and tabs) one by one, and adds them to s StringTable.

  ifstream f( "sometext.txt" );
  string s;
  StringTable words;
  while( f >> s )   // f >> s fills s with a new word and returns true,
                    // or fails (when at eof) and returns false
    words.add( s );

  // now words contains all words from the file
  ...
  if( words.contains( "computer" ) ) cout << "Must read!";
  else cout << "Don't bother.";
  ...
  words.print();

Modify the add(..) function so that a word is added if and only if it doesn't occur in the StringTable already. Assuming this modification, words.print(); will print each word that occurs in sometext.txt exactly once.

(e) Modify the class StringTable so that it keeps only one copy of each added value (as in (d)), and also counts how many times it was added. Modify print() so that it prints these counts. As a result, words.print(); in the above code will print each word that occurs in sometext.txt and the number of times it occurs.

(f, extra) The original class StringTable will work for files of no more than 100 words (in modifications (d) and (e), only different words count). Suppose that the programmer who is going to use your code knows approximately how many words will be in his file. Therefore, he would like to be able to declare StringTables of various initial capacities (say, 20 or 3000 values). If the capacity he specifies turns out to be too small, the table should expand itself, i.e. increase its capacity, each time the current capacity is exhausted. Make sure that your code doesn't leak memory.

Hint: You will need new [] and delete [], the operators for dynamic memory allocation. You can specify the desired initial capacity as a parameter to the constructor.

Problem 5. Look at the following excerpts from an implementation of class Fraction and answer the questions below.

class Fraction {
  int num;
  int denom;
public:
  Fraction( int n, int d ) : num(n), denom(d) { }
  // ....
  friend Fraction operator * ( const Fraction& , const Fraction & );
  // ....
};

Fraction operator * ( const Fraction & X, const Fraction & Y ){
  return Fraction( X.num * Y.num, X.denom * Y.denom );
}

(a) Assuming this declaration, is the following legal? If it is, describe its effect, if not, provide the fix needed to make it legal.

Fraction arr_frac[ 100 ];

(b) List all member functions that are called as a result of the following statements. Be sure to list all member functions, including those that may be automatically generated by the compiler. Also, make sure you consider the long-term effects as well as short-term ones.

Fraction a( 1, 2 ), b( 1, 3 );

Fraction c = a * b;   // makes c == 1/6


(c) Write the overloaded operator< that compares two fractions and returns true or false respectively. Make it a friend (not a member) of the class Fraction. The prototype:

  bool operator < (const Fraction & f1, const Fraction & f2 );



Sergey Bratus
6/8/1999