CS2023 Final Exam

7:00pm – 10:00pm, December 9, 2006

Write your answers in booklet(s). All code in your answers must be written in C.

1.  (10%) Write a program that merges two input data files, named file1.dat and file2.dat, containing sorted lists of double values. The output file, named file3.dat, should contain a sorted list merged from the values in the two input files. For example, given the following two input files:

file1.dat:

1.2  3.4 6

file2.dat:

2.4  5 9

The output file would contain:

file3.dat:

1.2 2.4 3.4 5 6 9

Note that you cannot use any array in the program.

2.  (8%) Find the output produced by the following program:

#define LOW -2

#define HIGH (LOW + 5)

#define PR(arg) printf(“%d\n”, (arg))

#define FOR(arg) for(; (arg); (arg)--)

#define SHOW(x) x

int main() {

int i = LOW;

int j = HIGH;

FOR(j)

Switch(j) {

case 1: PR(i++);

case 2: PR(j); break;

default: PR(i);

}

printf(“\n%s\n”, SHOW(3));

return EXIT_SUCCESS;

}

3.  (8%) If you calculate the sum

1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + … + 1/n

then this sum can be arbitrarily large; that is, for any positive integer M , you can find an integer n for which this sum is greater than M. Write a function to test the above claim:

int sum(int M);

sum() returns the smallest positive integer value of n for which the sum shown above is greater than M (assuming M > 0). If M <= 0, then sum() returns -1.

4.  (8%) Write a function with two parameters x and y of double type which changes the values of x to x-y, and the value of y to 2.

5.  (8%) Write a function:

int strcmpIgnoreCase(const char *s1, const char *s2);

that returns 1 if s1 and s2 differ only in the case of letters, that is, they contain different sequences of letters ignoring their cases. For instance, “abc” and “Abc” are not differ in this sense. It returns 0 otherwise.

6.  (10%) Write the following two functions.

(a)  This function takes an array of integers and the array size as the parameters, and returns a new array that contains the same integers in the reversed order.

int *reverse(int numbers[], int size);

(b)  This function takes an array of integers and the array size as the parameters, and re-arranges the elements of the same array in the reversed order

void reverseMyself(int numbers[], int size);

7.  (8%) Consider the following struct definition:

typedef struct {

int data[100];

int size;

} *DataTP;

Write a function divisible(), which returns the number of elements in d which are divisible by factor:

int divisible(const DataTP d, int factor);

8.  (20%) A priority queue is a queue whose first element is always the smallest among all elements in the queue. A priority queue has the following functions

§  enqueue() : this function adds a new element into the queue.

§  dequeue() : this function removes the first element from the queue and returns it.

§  is_empty() : this function returns true if the queue is empty, otherwise returns false.

Write a module that implements generic priority queues as an abstract data type (ADT). The following is the prototypes of the functions that apply to the priority queue ADT.

void enqueue(PQueue *pqueue, char *key, void *element);

void *dequeue(PQueue *pqueue);

int is_empty(PQueue *pqueue);

Here the parameter “char *key” in enqueue() is used to compare elements in the queue to determine the smallest.

You must use linked-list to implement this ADT.

9.  (20%) Write a multi-module program to do the follows. The program inputs a sequence of student records and outputs the input records in two different sorted orders.

A student record consists of 3 elements, student name as a string, student number as a string, and GPA as a real number.

The user inputs student records one by one from standard input, and the program outputs the results to screen. The program outputs the student records twice in the following two orders:

(a)  sorted by student names

(b)  sorted by student numbers

The program should consists of 3 modules: main processing module, user interface module,

and the priority queue ADT module that is defined in question 8.

You must use priority queue(s) form the ADT module to hold the records in the program.

Page 3 of 3