Midterm exam: sample solution

October 22, 2002

---

1. (35 points) A doubly-linked list of the type we used in the CatalogBrowser of Assignment 3 could be turned into a “circular” list by making the last node point to the first node and the first node point to the last node.

   Given a non-circular list with head pointing to its first node, write a piece of code that turns the list into a circular one.

   There are various ways of doing this ...

   for (tail = head; tail->next != NULL; tail=tail->next);
   tail->next = head;
   tail->next->previous = tail;
   

   for (tail = head; tail->next != NULL; tail=tail->next);
   head->previous = tail;
   head->previous->next = head;
   

   for (tail = head; tail->next != NULL; tail=tail->next);
   head->previous = tail;
   tail->next = head;
   

   tail = head; 
   do {tail=tail->next} while (tail->next != NULL);
   tail->next = head;
   tail->next->previous = tail;
   

   ---

2. (20 points) For such a circular list, which of the following pieces of code would compute the number of nodes in the list? Put a check mark next to all correct answers; cross out all incorrect ones.

   A, C, and D definitely don't work. (Note that the loops in C and D stop immediately.) B and E work except on the empty list. Because of that either answer was accepted.

   A.   length = 0;
   -    for (current = head; 
                 current->next != head; 
                     current=current->next)
            length++;
   
   B.   length = 1;
   +    for (current = head; 
                 current->next != head; 
                     current=current->next)
            length++;
   
   C.   length = 0;
   -    for (current = head; 
                 current != head; 
                     current=current->next)
            length++;
   
   D.   length = 1;
   -    for (current = head; 
                 current != head; 
                     current=current->next)
            length++;
   
   E.   length = 1;
   +    for (current = head; 
                 current->previous != head; 
                     current=current->previous)
            length++;
   

   ---

3. (20 points) Put a check mark next to all true statements; cross out all incorrect ones.
   1. Copy constructors always make “deep” copies. FALSE
   2. The default copy constructors --- the ones that get used when we don't program our own --- always make “deep” copies. FALSE
   3. When a parameter is passed “by value”, a copy of the actual parameter is being passed. TRUE
   4. When a parameter is passed “by reference”, a copy of the actual parameter is being passed. FALSE
   5. When a parameter is passed “by constant reference”, a copy of the actual parameter is being passed. FALSE

   ---

4. (25 points) For the Catalog class of Assignment 3, write a member function deleteSecond that cuts the second node out of the list and delete-s it. Make sure your code works for lists of any length. If the list is empty or consists only of one node it needs to remain unchanged.

   void Catalog::deleteSecond ()
   {
       if (head == NULL)
           return;
   
       if (head->next == NULL)
           return;
   
       CatalogNode* second = head->next;
       head->next = second->next;
       if (second->next != NULL)
           second->next->previous = head;
   
       delete second;
   
       return;
   }