Data Structures & Algorithms

Exam 1

Sample 1, 50 Minutes

An abbreviated version of the class LinearList of the text is given below.


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>& RightShift(int k);
         // shift elements right by k
         // zero fill at left end
   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 RightShift shifts the elements of the linear list right by k positions and fills the empty positions at the left end with zeroes. For example, if the list element[0:5] = [1, 2, 3, 4, 5, 6], whose length is 6, is shifted right by 3, the result is [0, 0, 0, 1, 2, 3, 4, 5, 6], whose length is 9. The NoMem exception is thrown if the array element doesn't have enough space for the shifted list and the BadInput exception is thrown if k < 0.

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

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 IsSorted() 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 IsSorted determines whether the chain elements are in ascending (more accurately nondecreasing) order of their data values. The function returns true if the list is sorted and false if it is not.

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

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

                              x             x 
                              x x           x
                              x   x   zero  x
                              x     x       x
                              x       x     x
                              x  zero   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 N-matrix and its compact representation.

(b)

[8] Suppose that we are defining a class NMatrix 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 NMatrix {
   public:
      NMatrix(int size = 10)
         {n = size; t = new T [3*n-2];}
      ~NMatrix() {delete [] t;}
      NMatrix<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