Note: This was given a total of 90 points by mistake. Final total multiplied by 10/9 = 1.111....

1. (12) 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.) Here are 4 answers:

   #include <stdio.h>
   
   char *strcopy(char *s);
   char *strcopy2(char *s);
   char *strcopy3(char s[]);
   char *strcopy4(char s[]);
   
   int main() {
      char u[] = "Ralph Johnson Bunche (August 7, 1904-1971)";
      char *v = strcopy(u);
      printf("\"%s\"\n", v);
            v = strcopy2(u);
      printf("\"%s\"\n", v);
            v = strcopy3(u);
      printf("\"%s\"\n", v);
            v = strcopy4(u);
      printf("\"%s\"\n", v);
   }
   
   char *strcopy(char *s) {
      char *t = (char *) malloc(strlen(s)+1);
      char *tsave = t;
      while (*s) {
         *t = *s;
         t++;
         s++;
      }
      *t = '\0';
      return tsave;
   }
   
   char *strcopy2(char *s) {
      char *t = (char *) malloc(strlen(s)+1);
      char *tsave = t;
      while (*t++ = *s++)
         ;
      return tsave;
   }
   
   char *strcopy3(char s[]) {
      char *t = (char *) malloc(strlen(s)+1);
      int i = 0;
      do {
         t[i] = s[i];
      } while (s[i++] != '\0');
      return t;
   }
   
   char *strcopy4(char s[]) {
      char *t = (char *) malloc(strlen(s)+1);
      int i = 0;
      while ((t[i] = s[i]) != '\0')
         i++;
      return t;
   }
   % cc -o prog0 prog0.c
   % prog0
   "Ralph Johnson Bunche (August 7, 1904-1971)"
   "Ralph Johnson Bunche (August 7, 1904-1971)"
   "Ralph Johnson Bunche (August 7, 1904-1971)"
   "Ralph Johnson Bunche (August 7, 1904-1971)"
   

2. (10) 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 = 3; j = 1; 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]); } % cc -o prog1 prog1.c % prog1 OK a[2][4]: 777 a[3][1]: 777

   Array Array elt a[2][4] offset 0 a[0][0] \ 1 a[0][1] +-- row 0 skip row 0 2 a[0][2] / 3 a[1][0] \ 4 a[1][1] +-- row 1 skip row 1 5 a[1][2] / 6 a[2][0] \ count 0 7 a[2][1] +-- row 2 count 1 8 a[2][2] / count 2 9 a[3][0] \ count 3 10 a[3][1] +-- row 3 count 4 11 a[3][2] /

   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. (12) 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 = (int **)malloc(sizeof(int *)*4)   /* MISSING A */;
      int i, j;
      for (i = 0; i < 4; i++) {
         *(a + i) =  (int *)malloc(sizeof(int)*3)  /* MISSING B */;
         for (j = 0; j < 3; j++)
            *(*(a+i) + j)       /* MISSING C */ = i*10 + j;
            (Note: *(a + i*3 + j) is NOT CORRECT.
            This only works for an array declared as a[4][3];)
      }
   
      for (i = 0; i < 4; i++) {
         printf("Row %i: ", i);        /* MISSING D */
         for (j = 0; j < 3; j++)
            printf("%2i ", *(*(a+i) + j));
         printf("\n");
      }
      a[2][4] = 777;
   }
   % cc -o prog2 prog2.c
   % prog2
   Row 0:  0  1  2
   Row 1: 10 11 12
   Row 2: 20 21 22
   Row 3: 30 31 32
   

   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.) No, it would not -- see the following:

      int main() { int **a = (int **)malloc(sizeof(int *)*4); int i, j; for (i = 0; i < 4; i++) { *(a + i) = (int *)malloc(sizeof(int)*3); for (j = 0; j < 3; j++) *(*(a+i) + j) = i*10 + j; } for (i = 0; i < 4; i++) { printf("Row %i: ", i); for (j = 0; j < 3; j++) printf("%2i ", *(*(a+i) + j)); printf("\n"); } a[2][4] = 777; printf("a[2][4]: %i\n", a[2][4]); for (i = 0; i < 4; i++) { printf("Row %i: ", i); for (j = 0; j < 3; j++) printf("%2i ", *(*(a+i) + j)); printf("\n"); } } % cc -o prog2.1 prog2.1.c % prog2.1 (run on Linux) Row 0: 0 1 2 Row 1: 10 11 12 Row 2: 20 21 22 Row 3: 30 31 32 a[2][4]: 777 Row 0: 0 1 2 Row 1: 10 11 12 Row 2: 20 21 22 Row 3: 777 31 32 % prog2.1 (run on pandora) Row 0: 0 1 2 Row 1: 10 11 12 Row 2: 20 21 22 Row 3: 30 31 32 a[2][4]: 777 Row 0: 0 1 2 Row 1: 10 11 12 Row 2: 20 21 22 Row 3: 30 31 32

      int main() { int **a = (int **)malloc(sizeof(int *)*4); int *dummy; int i, j; for (i = 3; i >= 0; i--) { *(a + i) = (int *)malloc(sizeof(int)*3); for (j = 0; j < 3; j++) *(*(a+i) + j) = i*10 + j; } for (i = 0; i < 4; i++) { printf("Row %i: ", i); for (j = 0; j < 3; j++) printf("%2i ", *(*(a+i) + j)); printf("\n"); } a[2][4] = 777; printf("a[2][4]: %i\n", a[2][4]); for (i = 0; i < 4; i++) { printf("Row %i: ", i); for (j = 0; j < 3; j++) printf("%2i ", *(*(a+i) + j)); printf("\n"); } } % cc -o prog2.2 prog2.2.c % prog2.2 (run on Linux) Row 0: 0 1 2 Row 1: 10 11 12 Row 2: 20 21 22 Row 3: 30 31 32 a[2][4]: 777 Row 0: 0 1 2 Row 1: 777 11 12 Row 2: 20 21 22 Row 3: 30 31 32 % prog2.2 (run on pandora) Row 0: 0 1 2 Row 1: 10 11 12 Row 2: 20 21 22 Row 3: 30 31 32 a[2][4]: 777 Row 0: 0 1 2 Row 1: 10 11 12 Row 2: 20 21 22 Row 3: 30 31 32

4. (12) 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.

   
   #include <stdio.h>
   
   struct person {
      char *name;
      int age;
   };
   
   void printstruct(struct person *p);
   
   int main() {
      struct person john;
      struct person *p;
      p = &john;
      p -> name = "John von Neuman";
      p -> age = 58;
      printstruct(p);
   }
   
   void printstruct(struct person *p) {
      printf("Name: %s\n", p -> name);
      printf("Age: %i\n", p -> age);
   }
   
   % cc -o prog3 prog3.c
   % prog3
   Name: John von Neuman
   Age: 58
   

5. (12) 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. (12) Consider the following incomplete program that creates a linked list:

   
   #include <stdio.h>
   
   struct link {
      char c;
      struct link *next;
   };
   
   void printlist(struct link *p);
   void printreverse(struct link *p);
   
   
   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");
   }
   
   void printlist(struct link *p) {
      while (p != NULL) {
         printf("%c", p -> c);
         p = p -> next;
         /* Students were leaving previous stmt off */
      }
      printf("\n");
   }
   
   void printreverse(struct link *p) {
      if (p != NULL) { /* Students were writing "while" here */
         printreverse(p -> next);
         printf("%c", p -> c);
      }
   }
   % cc -o prob4 prob4.c
   % prob4
   abcdef
   fedcba
   abcdef
   

   1. If the input characters are: "abcdef\n", draw a diagram of the resulting linked list.

      
      (Many students gave this list backwards.)
      
           +-+    +-+-+    +-+-+    +-+-+    +-+-+    +-+-+    +-+-+
      list | |--->|f| |--->|e| |--->|d| |--->|c| |--->|b| |--->|a| | (final NULL)
           +-+    +-+-+    +-+-+    +-+-+    +-+-+    +-+-+    +-+-+
      

   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. (8) 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.

      
           +--+    +-+--+    +-+--+    +-+--+    +-+---+     +--+
      front| -+--->|a| -+--->|b| -+--->|c| -+--->|d|   | <---|  |
           +--+    +-+--+    +-+--+    +-+--+    +-+-+-+     +--+
                                                     |
                                                     v
        Assuming a, b, c, d inserted at rear        NULL
      

   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? You can insert at the front of the queue, so that the queue can also function as a stack. (You cannot remove from the rear in constant time -- need to chase down from the front to do it.) (Some students answered "make queue empty", "to link the rear to the front", "peek at front", and "append a second queue", which are constant time, but not what I had in mind.)

8. (12) 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. Output one copy of the common buffer contents and read new values into both buffers.
   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.

      
      /* with sentinel */
      while(!(bufa equals sentinel && bufb equals sentinel)) {
         if (bufa equals bufb) {
             output one copy of common buffer;
             read new values into bufa and bufb;
         else if (bufa comes before bufb) {
             output bufa;
             read new value into bufa;
         } else {
             output bufb;
             read new value into bufb;
         }
      }
      

   3. Does essentially the same merge algorithm work if you are merging three files that are already in sorted order? Explain briefly.

   The same merge program works pretty much, with a few complications. Of course you will be reading in three buffers, call them abuf, bbuf, and cbuf, from files a, b, and c. If you use a sentinel at the end, you want to keep going

   while(strcmp(abuf, sentinel) != 0 ||
         strcmp(bbuf, sentinel) != 0 ||
         strcmp(cbuf, sentinel) != 0) {
   

   Then I had to use 7 cases for output, instead of the three before:

   1. All three buffers equal
   2. abuf equal bbuf and coming before cbuf
   3. abuf equal cbuf and coming before bbuf
   4. bbuf equal cbuf and coming before abuf
   5. abuf coming before the others.
   6. bbuf coming before the others.
   7. cbuf coming before the others.
   When you get done, all three buffers hold the sentinel.

   Now, without sentinels in the file, the simplest way is to simulate the presense of the sentinels. Check for EOF on each read of each file, setting flags EOFa, EOFa, or EOFb. Then add the code:
   

   
         if (EOFa == EOF) strcpy(abuf, sentinel);
         if (EOFb == EOF) strcpy(bbuf, sentinel);
         if (EOFc == EOF) strcpy(cbuf, sentinel);
   

   Otherwise, I don't see how to avoid messy details of EOF on different combinations of files.

   In the general case with n files, you need the concept of a priority queue, which you will study in the algorithms course.