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.

   True
   

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.''

   False
   

7. Doing a selection sort on n elements takes less time than doing a binary search on n elements.

   False.
   

8. You should use scanf() to write structs to binary files.

   False
   

9. Using the standard qsort() function is generally slower than coding your own selection sort.

   False
   

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.

    True
    

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.
   

#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);
}

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.

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);
   	count--;
   
   	/* 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);
   }