CS 305, Computer Algorithms I

Fall 2003 - Test 3

1. Write a recursive function to reverse the elements in a list. Your function should return a pointer to the head of the reversed list.

   ---

   The tricky part to this problem is keeping track of both ends of the list; the function has to return the new head, but the elements have to get placed at the end of the list.

   linked_list_node * reverse(
     linked_list_node * old-head, linked_list_node * new-head)
   
     assert old-head
   
     if old-head->next == null
       new-head = old-head
     else
       reverse(old-head->next, new-head)->next = old-head
   
     return old-head
   
   

   ---

2. The swap(a, b) operator swaps the values of its two operands. For example

   int i = 3
   int j = 4
   
   swap(i, j)
   
   // j = 3
   // i = 4
   

   Write a function that uses swap() to remove an element from a linked list. Your function must work for any element in the list.

   ---

   To simplify matters, assume we have a pointer to the linked-list node before the node to be deleted.

   void delete(linked_list_node * np)
     swap(np->next, np->next->next)
   

   ---

3. There are four sources of valid pointer values. Name three of them.

   ---

   The for sources of valid pointer values are:

   1. The null value (or 0).

   2. The address of operator applied to a variable.

   3. The value returned by the new operator.

   4. A properly initialized pointer variable of the same type.

   ---

4. In class we derived an expression to map indices to array elements in left to right order by increasing non-negative index value.
   

   Some languages also provide a mapping in right-to-left order by decreasing negative index value.

   

   Derive the expression to map indices to array elements for right-to-left order by decreasing negative index values. Don't forget to explain your derivation. Only answer the question for 1-dimensional arrays.

   ---

   See Test 1 for the answer.

   ---

This page last modified on 3 November 2003.