Directions: Fill in answers on the pages below. Don't spend too much time on any one problem. Even if you have forgotten some things, fake it as well as you can.

1. Here are some simple questions about pointers. Each part is to be used by later parts:
   1. Declare x to be an int.
   2. Declare xp to be a pointer to an int.
   3. Give xp a value so that it points to x.
   4. Use xp to give x the value 47.
   5. At this point, what is the value of *&x.
   6. What does the statement (*xp)++; do?
   7. What does the statement *(xp++); do?
   8. Give two forms for the type of an array of strings in C. (If an array of strings was a parameter, how would you declare it?)
   9. Given the declaration int *a, b;, what is the type of a and what is the type of b?

2. Java has a method in the String class: toLowerCase that converts each character of a string to lowercase if it was uppercase and leaves the other characters unchanged. C only has the function tolower that will convert a single character to lowercase and return it. (If the character is not uppercase, tolower just returns it unchanged.)

   Write a C function to_lower that will take a C string as input parameter, and will return a new malloced string that is a copy of the input parameter except that any uppercase letter has been converted to lowercase.

3. Complete the program below by supplying single function and two calls to this function to print the two arrays of strings (one string to a line). For full credit, your function must not use square brackets. You must use a loop, and you must use the NULL at the end.

   #include <stdio.h> /* prototype here */ void main(void) { char *sins[] = {"ENVY", "SLOTH", "GLUTTONY", "WRATH", "PRIDE", "LUST", "GREED", NULL}; char *laws[] = {"Trustworthy", "Loyal", "Helpful", "Friendly", "Courteous", "Kind", "Obedient", "Cheerful", "Thrifty", "Brave", "Clean", "Reverent", NULL}; /* 2 calls to the function here */ } /* code for the function here */

4. Standard C has a problem with 2-dimensional arrays -- unlike Java and Fortran, C cannot declare an "ordinary" 2-dimensional array with dimensions determined at run-time, nor can C pass such an array as a parameter. Here "ordinary" means that it is declared as with a[5][4]. All dimensions of such a declaration must be constants known at compile time. Thus the following function is illegal in standard C:

   void f(int m, int n) { double r[m][n]; /* other stuff */ }

   1. In the above example, would it be possible to use malloc to declare r as an array of pointers to 1-dimensional arrays? (Yes or No). If "No", say why not, and if "Yes", say why this method nevertheless might not be used.

      For the above reasons, it is not straightforward to write a function in C that will take an arbitrary 2-dimensional array as input parameter. Instead, one must resort to trickery, as in the following examples:

#include <stdio.h>

void readarray(double *r, int m, int n);
void writearray(double *r, int m, int n);

int main() {
   int m, n; /* m-by-n arrays */
   double *r;
   scanf("%i %i", &m, &n);
   r = (double *)malloc(sizeof(double)*m*n);
   readarray(r, m, n);
   writearray(r, m, n);
}

void readarray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++)
      for (j = 0; j < n; j++) {
         scanf("%lf", &r[index(i, j, n)]);
      }
}

void writearray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++)
         printf("%6.1f", r[index(i, j, n)]);
      printf("\n");
   }
}

/* DEFINITION FOR FUNCTION "index" HERE */

#include <stdio.h>
/* DEFINITION FOR MACRO "R" HERE */
void readarray(double *r, int m, int n);
void writearray(double *r, int m, int n);

int main() {
   int m, n; /* m-by-n arrays */
   double *r;
   scanf("%i %i", &m, &n);
   r = (double *)malloc(sizeof(double)*m*n);
   readarray(r, m, n);
   writearray(r, m, n);
}

void readarray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++)
      for (j = 0; j < n; j++) {
         scanf("%lf", &R(i, j, n));
      }
}

void writearray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++)
         printf("%6.1f", R(i, j, n));
      printf("\n");
   }
}

2. For use on the left, give a definition for a function index that will return the correct value for use in the program.

3. For use on the right, give a macro definition for a macro R that will return the correct value for use in the program.

4. (Extra credit) Can you think of some other (perhaps better) way to do this?

5. Suppose we are using hashing with open addressing to insert into a hash table h of size 11 (an array of pointers to char, each initially NULL, with indexes from 0 through 10, inclusive). We want to insert the following items into this table.
   "rat", with hash("rat") == 8
   "cat", with hash("cat") == 10
   "dog", with hash("dog") == 8
   "pig", with hash("pig") == 9
   "cow", with hash("cow") == 0
   "bat", with hash("bat") == 0
   1. Show in a diagram the result of inserting into the array the above items with the given hash values. (Assume that the search goes to the next larger item, and wraps around.)

   2. In the above situation, if one now wants to delete the entry for "pig", explain why it doesn't work to just set the pointer equal to NULL. Say what we did in class to handle this problem.

6. Consider the following incomplete program (left) and data (right):

   #include <stdio.h> #include <stdlib.h> #define N 5 struct gnode { int v; int dist; struct gnode *next; }; void adjlist(struct gnode *g[]); void main(void) { struct gnode *g[N]; int i; for (i = 0; i < N; i++) g[i] = NULL; adjlist(g); } void adjlist(struct gnode *g[]) { /* POSSIBLE ADDITIONAL DECLARATION(S) HERE */ FILE *edges; int i; int v1, v2, d; for (i = 0; i < N; i++) g[i] = NULL; if ((edges = fopen("edges.dat", "r")) == NULL) { printf("Can't open file: edges.dat\n"); exit(1); } while (fscanf(edges, "%i %i %i", &v1, &v2, &d) != EOF) { /* PUT PART OF YOUR ANSWER HERE */ } } /* POSSIBLE ADDITIONAL FUNCTION(S) HERE */

   0 1 10 0 3 5 1 2 1 1 3 2 2 4 4 3 1 3 3 2 9 3 4 2 4 0 7 4 2 6

   1. The numbers at the right above describe a directed graph, where first come two vertices, the starting and ending vertex of an edge, and then the weight of the edge. The graph has 5 vertices: 0, 1, 2, 3, and 4. Draw a diagram showing the adjacency list representation of this graph.

   2. The program on the left above reads the data at the right: a list of pairs of vertices representing a directed edge, each pair followed by a number representing the weight on the edge. The program should then construct the adjacency list representation of the graph as it was presented in the course. The program is missing the key code that actually inserts each new edge into the adjacency list and puts in the weight. Otherwise the program is complete. You are to supply the missing code. (Some code must be supplied inside the while loop. You may want to or need to supply one or more additional declarations or functions.)

7. Consider the array: int A[] = {0, 7, 29, 10, 14, 8, 9, 2, 3, 11};, where A[0] is not used.
   1. Write this array in diagram form as a complete binary tree.
   2. Show on the diagram how to convert this tree to a heap. (Just move elements around, crossing out as you go. Ignore element A[0]. You must write this carefully enough so that I can read it.)
   3. Show the first step of heapsort, where the largest element ends up in its proper place, and the heap property is restored for the remaining elements.