Final Exam for C Programming Language (CS2402)

Instructor: Roger Jang

1. Correctness
2. Efficiency
3. Clarity
4. Brevity

You may add comments freely if they help make your code more easily understood.

LISTNODE and TREENODE are two data types that you are going to used in answering some of the questions in this exam. These two data types are defined as follows.

struct listNode {
	char data;
	struct listNode *next;
};
typedef LISTNODE struct listNode;

struct treeNode{
	char data;
	struct treeNode *left;
	struct treeNode *right;
};
typedef TREENODE struct treeNode;

1. (10%) Suppose there are two integers a and b in a C program. We want to exchange the values of these two integer by a function call.
   1. Write a function swap() to accomplish the task.
      Answer:

      void swap (int *a, *b) {
      	int temp;
      	temp = *a;
      	*a = *b;
      	*b = temp;
      }
      	

   2. How do you invoke the function?
      Answer:

      swap(&a, &b);
      	

2. (10%) Write a one-line macro MAX(x, y) that gives the maximum of two numbers.
   Answer:

   #define MAX(x,y) ((x)>(y)?(x):(y))
   	

3. (10%) Write a one-line macro DISP(x, format) that prints a variable in an appropriate format. For instance, if x is an integer with 24 as its value, DISP(x, %d) should print out

   	x = 24
   	

   Answer:

   #define DISP(x, format) printf(#x " = " #format "\n", x); 
   	

4. (20%) Write a recursive function that returns the depth of a given node. Note that a terminal node should have a depth of zero. The prototype of the desired function looks like this:

   	int treeDepth(TREENODE *root);
   	

   Answer:

   int treeDepth(TREENODE *root) {
   	if (root == NULL)
   		return(-1);
           return(1+MAX(treeDepth(root->left), treeDepth(root->right)));
   }
   	

5. (25%) Write a recursive function to reverse a given list. The prototype of the function looks like this:

   	LISTNODE *reverseList(LISTNODE *head);
   	

   Note that you are only allowed to do pointer manipulation; no data manipulation is allowed.
   Answer:

   LISTNODE *reverse(LISTNODE *head) {
   	LISTNODE *p, *q;
   	if (head == NULL || head->next == NULL)
   		return(head);
   	p = head;
   	q = p->next;
   	while (q->next != NULL) {
   		p = q;
   		q = q->next;
   	} /* Now q is pointing to the last element of the list. */
   	p->next = NULL;
   	q->next = reverse(head);
   	return(q);
   }
   	

6. (25%) A set can be implemented as a linked list. Write a function that returns a new list that represents the union of two given lists. Note that:
   • Since the list represents a set, there is no special ordering and no duplicated items in the given and returned lists.
   • The function should not change either of the given lists.
   Answer:

   LISTNODE *newlist (LISTNODE *head1, LISTNODE *head2) {
   	LISTNODE *temp1, *new, *new_head, *temp2;
   	int test = 0;
   
   	/* Duplicate the first list */
   	new = (LISTNODE *)malloc(sizeof(LISTNODE)); 
   	new_head = new;
   	new->data = head1->data;
   	temp1 = head1;
   	while (temp1->next != NULL) {
   		new->next = (LISTNODE *)malloc(sizeof(LISTNODE));
   		new->next->data = temp1->->next->data;
   		new = new->next;
   		temp1 = temp1->next;
   	}
   	new->next = NULL;
          
   	/* Insert the second list */
   	temp2 = head2;
   	while (temp2 != NULL) {
   		temp1 = new_head;
   		test = 0;
   		while (temp1 != NULL) {
   			if ( temp2->data == temp1->data)
   				test = 1;
   			temp1 = temp1->next;
   		}
   		if (test == 0) {
   			new->next = (LISTNODE *)malloc(sizeof(LISTNODE));
   			new->next->data = temp2->data;
   			new = new->next;
   		}
   		temp2 = temp2->next;
   	}
   	new->next = NULL; 
   	return new_head; 
   }