Data Structures & Algorithms

Exam 1

Sample 3, 75 Minutes

Solutions

1. (a) The code is given below.

   
   public static void split(MyList a, MyList b, MyList c)
   {
      // initialize iterator for a
      Iterator ia = a.iterator();  // iterator for a
   
      // make b and c empty
      b.clear();
      c.clear();
   
      // append elements from a alternately to b and c
      while (ia.hasNext())
      {
         b.append(ia.next());
         if (ia.hasNext())
            c.append(ia.next());
      }
   }
   
   

   (b)

   Let n be the size of list a. The while loop is iterated O(n) times, and each iteration takes O(1) time. So the while loop takes O(n) time. The remainder of the code takes takes O(1) time. Therefore, the total time taken by the method is O(n).

   
   
   
2. (a) The code is given below.

   ---

   public void removeNull()
   {
      int newSize = 0;  // number of non-null elements so far
      
      // do the removing
      for (int i = 0; i < size; i++)
         if (element[i] != null)
             // save this element
             element[newSize++] = element[i];
   
      // clean up for garbage collection
      // this work may be combined into the preceding for loop by
      // adding the statement element[i] = null; into the if statement
      for (int i = newSize; i < size; i++)
         element[i] = null;
   
      size = newSize;  // update size
   }
   

   ---

   
   

   (b)

   Each for loop iterates O(n) times, where n is the initial size of the list. Each iteration of each loop takes O(1) time. Therefore, the complexity of the loops is O(n). The remainder of the code takes O(1) time. Therefore, the overall complexity is O(n).

   
   
   
3. (a) The code is given below.

   ---

   public void merge(MyCHList a, MyCHList b)
   {
      // do the merging
      MyChainNode currentA = a.headerNode.next,
                  currentB = b.headerNode.next,
                  lastThis = headerNode;
   
      while (currentA != a.headerNode || currentB != b.headerNode)
         // elements remain
         if (currentA.element <= currentB.element)
         {// merge from a
            lastThis = lastThis.next = currentA;
            currentA = currentA.next;
         }
         else
         {// merge from b
            lastThis = lastThis.next = currentB;
            currentB = currentB.next;
         }
   
      //  merged all elements
      // close circular list this and update size
      lastThis.next = headerNode;
      size = a.size + b.size;
   
      // make a and b empty
      a.header.next = a.header;
      b.header.next = b.header;
      a.size = b.size = 0;
   }
   

   ---

   
   

   (b)

   In each iteration of the while loop one node/element is added to the result list. Therefore, this loop is iterated n times, where n is the size of the result list. Each iteration of the loop takes O(1) time. Therefore, the complexity of the loop is O(n). The remainder of the code takes O(1) time. Therefore, the overall complexity is O(n).