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. Write a function strcpy that will take a string as its single parameter. This function should malloc storage for another copy of the input string parameter. Then it should copy the input parameter into the new storage, character-by-character. Finally it should return the new copy of the string using a pointer. (Do not use any library string functions, but only the library function malloc.)

2. Consider the following C program:

   int main() {
      int a[4][3];
      int i, j;
      for (i = 0; i < 4; i++)
         for (j = 0; j < 3; j++)
            a[i][j] = i*10 + j;
      a[2][4] = 777;
      i =   ;
      j =   ;
      if (0 <= i && i < 4 && 0 <= j && j < 3 &&
            a[2][4] == a[i][j]) 
         printf("OK\n");
      printf("a[2][4]: %i\n",  a[2][4]);
      printf("a[%i][%i]: %i\n", i, j, a[i][j]);
   }

   1. Determine values to fill into the blanks for i and j so that the program will print "OK".
   2. Draw a careful 1-dimensional picture of the array, showing the rows, and showing why your answer above is correct.
   3. Give the rest of the output of this program exactly as it will appear.

3. Suppose we want to create an int array of 4 rows, each row 3 long, but this time as an array of pointers to 1-dimensional arrays. The following C program should use malloc to create an array of 4 pointers, each pointing to an array of 3  ints:

   int main() {
      int **a =                                 /* MISSING A */;
      int i, j;
      for (i = 0; i < 4; i++) {
         *(a + i) =                               /* MISSING B */;
         for (j = 0; j < 3; j++)
                                /* MISSING C */ = i*10 + j;
      }
   
   
   
                                             /* MISSING D */
   
   
   }

   When you finish adding answers to the first four questions below, you should have a single, complete, and correct program.

   1. Fill in the missing part A that will use malloc to inialize the array a.
   2. Fill in the missing part B that will use malloc to inialize each of the four elements of the array a.
   3. Fill in the missing part C that will work as the array reference a[i][j] without using any square brackets [].
   4. Fill in the missing part D that will print the elements of the array, with each row on a separate line.
   5. Would a reference to a[2][4] be the same as a reference with different array indexes in bounds, just as in the first program in this test? (Yes or no, with a brief reason.)

4. Consider the following structure definition:

   
   struct person {
      char *name;
      int age;
   };
   

   1. Does the definition above allocate any storage? (Yes or No).

      Answers to the remaining 5 questions should be combined with the above struct definition into a single, complete, and correct program.

   2. Give code that will declare a "bare" struct named john of the above type.
   3. Give a declaration of a pointer p that can point to such a struct.
   4. Give code that will set the pointer to point to this struct.
   5. Using the pointer, put the string "John von Neuman" into the first field, and put age of 58 into the second field.
   6. Write a function named printstruct that will take a pointer to the struct above, and will print the two fields.

5. Show step-by-step how to use the "railroad" diagrams to translate the following example of an arithmetic expression into RPN. (Give a very brief reason for each step.):

   
   2 * ( 1 + 3 * 4 + 5 ) $
   

6. Consider the following incomplete program that creates a linked list:

   
   #include <stdio.h>
   
   struct link {
      char c;
      struct link *next;
   };
   
   int main() {
      struct link *list = NULL, *save;
      char ch;
      while ((ch = getchar()) != '\n') {
         save = list;
         list = (struct link *)malloc(sizeof(struct link));
         list -> c = ch;
         list -> next = save;
      }
      printlist(list);
      printreverse(list);
      printf("\n");
   }
   

   1. If the input characters are: "abcdef\n", draw a diagram of the resulting linked list.
   2. Supply code for a function printlist that should print the list from front to back, all on one line. Give a prototype also.
   3. Supply code for a function printreverse that should use recursion to print the list from back to front, all on one line. Give a prototype also.

7. This question is about queues implemented using linked lists.
   1. Draw a diagram of a queue, showing the front and rear pointers, and the direction of the queue as a linked list.
   2. Besides the normal insert at the rear and remove from the front, a queue will support one more operation that can be programmed to occur in constant time. What is this operation?

8. This question is the merge algorithm.
   1. Suppose you are merging two files, reading words from each file into two different buffers. Explain carefully what you should do in case the two buffers contain the same word, not the sentinel.
   2. We had two merge algorithms for two files, one using EOF on the two files, and the other using a sentinel entry at the end of each file. Pick one or the other algorithm and describe it in English or pseudocode or actual code.
   3. Does essentially the same merge algorithm work if you are merging three files that are already in sorted order? Explain briefly.