Final Exam Solutions

 1. c
    132 = 64 + 32 + 32 + 4 = 0000 0000 0110 0100 + 0010 0000,
                           = 0000 0000 1000 0100,
                      -132 = 1111 1111 0111 1011 + 1
                           = 1111 1111 0111 1100 = FF7C (hex)
                           = 1 111 111 101 111 100
                           = 1   7   7   5   7   4 (octal)

 2. b
    10:     B110    R1 <- 10
    11:     8620    jump to 20 and link R6 <- 12
    20:     9160    R1 <- M[R6+00] = M[12] = 4602
    21:     4102    system call 2: print R1 = 4602
    4602
    22:     7600    jump indirect to R6 = 12
    12:     4602    system call 2: print R6 = 0012
    0012
    13:     0000    HALT

 3. d
    5 8 7 6 1 9 3 2 4
    5 4 7 6 1 9 3 2 8
    5 4 2 6 1 9 3 7 8
    5 4 2 3 1 9 6 7 8
    1 4 2 3 5 9 6 7 8

 4. a

 5. b (e is almost as good and is worth 3 points.)
    b[i] is the number of 1 bits in i, for i=0..7

 6. a
    quicksort could take N^2 and the loop could take N,
    which gives N^2 + N or about N^2

 7. d
    2^30/2^16 = 2^14 = 2^4 * 2^10 = 16KB

 8. b
    ptr[i] is a struct word, not a pointer, so free(ptr[i]) is invalid.
    This code won't even compile.

 9. a
    The initialization should be emalloc(200)

10. The answer is supposed to be e, but the code is incorrect.
    The correction is to change the if statement to

    if (len > 0 && (x >= y && x < y + len || y >= x && y < x + len)) {

    which tests if x and y overlap in any way. Evan Greenberg suggested
    a more compact test:

    if (len > 0 && abs(x - y) < len) {

11. b
    00:	B001	=MAIN			R0 <- 01		R0 holds 1
    01:	B10D	+starting address	R1 <- 0D		address of M
    02:	9210				R2 <- M[R1+0]		R2 <- M = i
    03:	9111				R1 <- M[R1+1]		R1 <- N
    04:	2112				R1 <- R1 - R2		R1 <- N-M = n
    05:	B300				R3 <- 00		R3 is the sum
    06:	610B	+starting address	jump to 0B if R1 < 0	if (n < 0) goto End
    07:	1332				R3 <- R3 + R2		sum += i
    08:	1220				R2 <- R2 + R0		i++
    09:	2110				R1 <- R1 - R0		n--
    0A:	5006	+starting address	jump to 06		goto Top
    0B:	4302				print R3		print sum
    0C:	0000				halt
    0D:	00	=M
    0E:	0A	=N

12. b

13. int *listtoarray(struct item *list, int last) {
       int n = 0, *array;
       struct item *p;
    
       for (p = list; p != NULL; p = p->link)
          n++;
       array = emalloc((n + 1)*sizeof (int));
       for (n = 0; list != NULL; list = list->link)
          array[n++] = list->info;
       array[n] = last;
       return array;
    }

14. void treefree(struct node *tree) {
       if (tree != NULL) {
          treefree(tree->left);
          treefree(tree->right);
          free(tree);
       }
    }

15. char *dup(int n, char *s) {
       char *str;
       int len = n*strlen(s);

       if (len <= 0)
          len = n = 0;
       str = emalloc(len + 1);
       str[0] = '\0';
       while (n-- > 0)
          strcat(str, s);
       return str;
    }

    A more efficient solution uses strcpy:

    char *dup(int n, char *s) {
       char *str;
       int i, slen = strlen(s), len = n*slen;

       if (len <= 0)
          len = 0;
       str = emalloc(len + 1);
       for (i = 0; i < len; i += slen)
          strcpy(str + i, s);
       str[i] = '\0';
       return str;
    }

16. char *itohex(int n) {
       int i = 2*sizeof (int);
       char *str = emalloc(i + 1);

       str[i] = '\0';
       for ( ; i > 0; n >>= 4)
          str[--i] = "0123456789ABCDEF"[n&0xF];
       return str;
    }

    Here's a simpler, but more obscure, solution:

    char *itohex(int n) {
       char *str = emalloc(2*(sizeof (int)) + 1);

       sprintf(str, "%0*X", 2*sizeof (int), n);
       return str;
    }