Data Structures & Algorithms

Makeup Exam 1

Sample 2, 50 Minutes

An abbreviated version of the class LinearList of the text is given below. No members other than those given below are available for this class.


template<class T>
class LinearList {
   public:
      LinearList(int MaxListSize = 10); // constructor
      ~LinearList() {delete [] element;} // destructor
      bool Find(int k, T& x) const;
         // return the k'th element of list in x
      LinearList<T>& InsertZero(int i, int k);
         // insert k zeroes following element i
   private:
      int length;
      int MaxSize;
      T *element; // dynamic 1D array
};

template<class T>
LinearList<T>::LinearList(int MaxListSize)
{// Constructor for formula-based linear list.
   MaxSize = MaxListSize;
   element = new T[MaxSize];
   length = 0;
}

template<class T>
bool LinearList<T>::Find(int k, T& x) const
{// Set x to the k'th element of the list.
 // Return false if no k'th; true otherwise.
   if (k < 1 || k > length) return false; // no k'th
   x = element[k - 1];
   return true;
}

The new member InsertZero inserts k zeroes after element i. The NoMem exception is thrown if the array element doesn't have enough space for the resulting list and the BadInput exception is thrown if k < 0 or i is not within the range of the list length.

(a): [8] Write C++ code for the InsertZero member function.
(b) [2] What is time complexity of your code as a function of the list length and k?

A condensed version of the class Chain is given below.


template <class T>
class ChainNode {
   private:
      T data;
      ChainNode<T> *link;
};

template<class T>
class Chain {
   friend ChainIterator<T>;
   public:
      Chain() {first = 0;}
      ~Chain();
      bool IsBitonic() const; 
   private:
      ChainNode<T> *first;  // pointer to first node
};

template<class T>
Chain<T>::~Chain()
{// Chain destructor. Delete all nodes in chain.
   ChainNode<T> *next;  // next node
   while (first) {
      next = first->link;
      delete first;
      first = next;
      }
}

The new member IsBitonic determines whether the chain elements are in bitonic order (either a nondecreasing subsequence followed by a nonincreasing subsequence or the reverse; either subsequence may be empty) of their data values. The function returns true if the list is bitonic and false if it is not.

(a): [8] Write C++ code for the IsBitonic member function.
(b) [2] What is time complexity of your code as a function of the list length?

In an n x n Z-matrix, all terms other than those in row 1, row n, and the cross diagonal are zero. A Z-matrix has at most 3n-2 nonzero terms. A Z-matrix can be compactly stored in a one-dimensional array by first storing row 1, then row n, and then the remaining elements of the cross diagonal.

                              x x x x x x x x 
                                           x 
                                zero    x 
                                      x   
                                    x   zero  
                                  x     
                                x           
                              x x x x x x x x


                         x denotes a possible nonzero
                         all other terms are zero

(a)

[2] Give a sample 4 x 4 Z-matrix and its compact representation.

(b)

[8] Suppose that we are defining a class ZMatrix that represents an n x n N-matrix in a one-dimensional array

t as above.
The class specification is as follows:

template<class T>
class ZMatrix {
   public:
      ZMatrix(int size = 10)
         {n = size; t = new T [3*n-2];}
      ~ZMatrix() {delete [] t;}
      ZMatrix<T>& Store(const T& x, int i, int j);
      T Retrieve(int i, int j);
   private:
      int n;    // dimension
      T *t;     // 1D array
};


Write C++ code for the member function Store which
stores x as the (i,j)
element
of the N-matrix, 1 <= i <= n
and
1 <= j <= n.
The element is to be stored in the proper position of the one-dimensional
array t.





Solutions