CS 1713 Section 3
Spring 1997
Exam 2

Write your name and answer the following problems on the paper provided. You may keep this question paper. This exam is worth 100 points. Keep your answers concise. Points will be taken off for handwriting that is hard to read; take an extra sheet of paper if you need it, rather than erasing an entire answer and starting over on the same sheet.

I. True/False (20 points). Answer True or False for each of the following.

  1. A string in C is represented by a null-terminated array of char.
  2. Accessing all elements of a two-dimensional array usually involves at least two loops.
    True: one loop for each array index.
  3. If you read past the end of the file, fscanf() automatically begins reading from the beginning again.
    False.  This was one freebie from the last test.
  4. A Finite State Automaton actually has an infinite number of states.
    False.  This was the other freebie.
  5. Integers that are too big to fit in a C int can still be represented using arrays of ints and special functions to add, convert, etc.
    True.  We saw an example of this in class.
  6. The Game of Life is a two-player game similar to ``Pac-Man.''
  7. Doing a selection sort on n elements takes less time than doing a binary search on n elements.
  8. You should use scanf() to write structs to binary files.
  9. Using the standard qsort() function is generally slower than coding your own selection sort.
  10. Using a header file that contains typedefs and other definitions allows one to separate more easily the interface from the implementation of an abstract data type.
II. Short Answer (24 points). Answer the following in one or two sentences each.
  1. Two-dimensional arrays have many uses in computing. Briefly describe two examples.
    Computer graphics and text terminals; the screen is represented by a 2D array.
    Matrix math.
    Keeping student records with one row per student, one column per grade.
    Games played on a 2D grid, like Chess and The Game of Life.
    There are other acceptable answers...
  2. What reason do we have to use malloc()? Why can't we always just declare arrays and use them?
    You don't always know how big to declare an array.  If you overestimate,
    you waste memory.  If you underestimate, your program is out of space
    and may crash.  With malloc(), you can get just as little or as much
    as you need dynamically (i.e., at run-time).  Also, a program compiled to
    use a huge array may not run on a computer with a small memory.  With
    malloc(), you know at run-time that you're out of memory (malloc() returns
    NULL) and you can give the user options to lower the memory requirement,
    use a different algorithm, or just quit.
  3. Any program you can imagine can be written in C without using struct or typedef. Why, then, do we still use them?
    struct and typedef allow the programmer to mentally group concepts into
    abstract data types.  The implementation of these types can be hidden
    from the person using the types; they will seem like just another C type
    with operations (functions) defined on them.  This enhances usability
    and readability of the code.
  4. We have seen two searching algorithms: linear search and binary search. Linear search must examine, on average, half of the n elements of an array while binary search needs to only see log n. Thus, binary search is a great deal more efficient than linear search. Why, then, should we still study and use linear search?
    Binary search can only be used when the data are sorted.  Sorting takes
    more time than searching, so if you're only going to do a few searches
    in a program, linear search will be the best choice rather than sorting
    and then using binary search.
III. Program Analysis (24 points). Consider the following C program. It is supposed to read 100 struct of type ``stuff'' from the file named on the command line into an array, then print the contents of the array to standard output.
#include <stdio.h>

typedef tag {
	int	a;
	char	b;
	float	c
} stuff;

int main () {
	int	i;
	stuff	v[100];
	FILE	*f;

	f = fopen (argv[1], "r");
	for (i=1; i<=100; i++)
		fread (&v[i], sizeof (stuff), 1, f);
	fclose ();
	for (i=1; i<=100; i++)
		printf ("%d\t%c\t%f\n", v[i]->c, v[i]->b, v[i]->a);
There are several errors in this program. Briefly describe four errors.
1. 'typedef' should be immediately followed by 'struct', since we are 
declaring a struct type.
2. 'float c' needs a semicolon after it.
3. 'argv' and 'argc' are not declared as parameters to main(), but they are
used in the program.
4. The two 'for' loops should let 'i' take on values from 0..99, not 1..100,
since the array 'v' starts at element 0.
5. 'fclose()' is missing its argument.
6. The order of the arguments to 'printf()' is jumbled.
7. 'v[i]->c' etc. should be 'v[i].c' since 'v[i]' is a struct, not a pointer
to struct.

IV. Programming Problems (32 points).
  1. Write a C function that accepts as a parameter a 10x10 two dimensional array of floats and returns the average of all the elements in the array. The first line of the function should look like this:
    float average2d (float v[10][10]) {
    Note: this function prints nothing. It reads nothing from either the keyboard or a file. It just finds and returns the average of numbers that have already been placed into an array.
    float average2d (float v[10][10]) {
    	float	sum;
    	int	i, j;
    	sum = 0.0;
    	for (i=0; i<10; i++) for (j=0; j<10; j++) sum += v[i][j];
    	return sum / 100.0;
  2. Write a C program that reads a integers from a file called numbers, then prints the list in reverse order. Your program should work for any size file, up to the capacity of the machine, so you should use malloc to allocate an array of the appropriate size. Use the following pseudocode when writing your program:
    	open the file called "numbers" for reading
    	count the number of items in the file using 
    	the following algorithm:
    		read integers from the file, incrementing a count 
    		each time, until end of file is reached.
    	close the file
    	allocate space for an array called 'v' using malloc and the
    	number of items counted above.
    	open the file again for reading
    	read all the numbers into 'v'
    	close the file
    	print 'v' from last element to first element
    int main () {
    	FILE	*f;
    	int	count, i, tmp, *v;
    	/* open the file called "numbers" for reading */
    	f = fopen ("number", "r");
    	if (!f) {
    		fprintf (stderr, "hey!\n");
    		exit (1);
    	/* count the number of items in the file */
    	for (count=0; !feof (f); count++) fscanf ("%d", &tmp);
    	/* close the file */
    	fclose (f);
    	/* allocate space for an array called 'v' */
    	v = (int *) malloc (sizeof (int) * count);
    	/* open the file again for reading */
    	f = fopen ("numbers", "r");
    	/* read all the numbers into 'v' */
    	for (i=0; i<count; i++) fscanf (f, "%d", &v[i]);
    	/* close the file */
    	fclose (f);
    	/* print 'v' from last element to first element */
    	for (i=count-1; i>=0; i--) printf ("%d\n", v[i]);
    	exit (0);