Midterm 2 Solutions

 1. 100 = 64 + 32 + 4 = 0000 0000 0110 0100,
                 -100 = 1111 1111 1001 1011 + 1
                      = 1111 1111 1001 1100

 2. 4102

 3. 5 8 7 6 1 9 3 2 4
    2 8 7 6 1 9 3 5 4
    2 3 7 6 1 9 8 5 4
    2 3 1 6 7 9 8 5 4
    2 3 1 4 7 9 8 5 6 (only this line was required)

 4. 2N, because each call eliminates 1 value, and there
    are 2 recursive calls.

 5. f(n) returns the number of 1 bits in n.

 6. 1 hour = 60*60 seconds = 36*10^2*10^6 microseconds
    N^2 = 36*10^8, so N = 6*10^4 = 60,000.

 7. ptr = erealloc(ptr, size*sizeof (struct word));

 8. No; the value passed to free is invalid, because ptr is changed in
    the loop. Change the loop to, for example,

    struct word *p = ptr;
    for ( ; n-- > 0; p++)
       { printf("%d\t%s\n", p->count, p->str); free(p->str); }

    or
    
    int i;
    for (i = 0; i < n; i++)
       { printf("%d\t%s\n", ptr[i].count, ptr[i].str); free(ptr[i].str); }

 9. word is uninitialized.

10. reverse(a + 1, a, 8) sets a to 1 1 1 1 1 1 1 1 1 10
    instead of 1 8 7 6 5 4 3 2 1 10.

11. 01:   B101   R1 <- 1
    02:   B300   R3 <- 0                R3 holds the sum
    03:   2421   R4 <- R2 - R1 = R2 - 1
    04:   6409   jump to 09 if R4 < 0   quit at the end of the list
    05:   9420   R4 <- M[R2]            load int in this node
    06:   1334   R3 <- R3 + R4          add it to the sum
    07:   9221   R2 <- M[R2+1]          advance to next node
    08:   5003   goto 3
    09:   ...

12. struct item *next;
    for ( ; list != NULL; list = next) {
       next = list->link;
       free(list);
    }

13. int treecount(struct node *tree) {
       if (tree != NULL)
          return treecount(tree->left) + treecount(tree->right) + 1;
       else
          return 0;
    }

    To solve this problem with a global variable, you need two functions:

    int count;

    void traverse(struct node *tree) {
       if (tree != NULL) {
          count++;
          traverse(tree->left); traverse(tree->right);
       }
    }

    int treecount(struct node *tree) {
       count = 0;
       traverse(tree);
       return count;
    }

14. char *concat(char *s1, char *s2) {
       return strcat(strcpy(emalloc(strlen(s1) + strlen(s2) + 1), s1), s2);
    }

    A more verbose, but perhaps more obvious, solution doesn't use the
    values returned by strcat and strcpy:

    char *concat(char *s1, char *s2) {
       char *s = emalloc(strlen(s1) + strlen(s2) + 1);

       strcpy(s, s1);
       strcat(s, s2);
       return s;
    }

15. char *itoa(int n, char *str) {
       char buf[25];

       sprintf(buf, "%d", n);
       if (str == NULL)
          str = emalloc(strlen(buf) + 1);
       return strcpy(str, buf);
    }