Test 1: Questions

X1.1.

[10 pts] Below is the beginning of a program to fill an array with 100 numbers entered by the user. Complete the program so that it then displays the numbers, one per line, in reverse order from how the user entered them.

int main() {
    int num[100];
    int i;

    for (i = 0; i < 100; i++) {
        scanf("%d", &(num[i]));
    }
X1.2.

[6 pts] Given the function provided below, what is returned by mystery(a) if a is the array <2, 5, 8, 1, 4, 7, 3, 6>?

int mystery(int nums[]) {
    int result;
    int i;

    result = 0;
    for (i = 0; i < 7; i++) {
        result += (nums[i] < nums[i + 1]);
    }
    return result;
}
X1.3.

[8 pts] What does the below C program display?

#include <stdio.h>

int main() {
    int i;  int j;
    int *p; int *q; int *r;

    i = 5;
    j = 6;
    p = &i;
    q = &j;
    r = p;
    *r = 7;
    p = q;
    *q = 8;
    q = &i;
    printf("%d %d\n", i, j);
    printf("%d %d %d\n", *p, *q, *r);
}
X1.4.

[10 pts] In C, what is a function prototype, and why would you use one in a program?

X1.5.

[12 pts] Without using any built-in C functions, complete the below C function that returns 1 if the string s contains any repeated characters. For example, strrepeat("committee") and strrepeat("nearing") should both return 1, whereas strrepeat("adeiu") should return 0. Note that \emph{nearing} has a repeated character, even though there are no adjacent duplicates. (It's fine to use a nested loop. Efficiency is not a concern.)

int strrepeat(char *s) {
X1.6.

[8 pts] Ben Bitdiddle wrote the below simple program, expecting it to display “p points to 5”. But when he executed it, he was surprised to find it displaying “p points to 32610” instead. Why does it do this?

int* create_pointer(int value) {
    int k = value;
    return &k;
}

int main() {
    int *p;

    p = create_pointer(5);
    printf("p points to ");
    printf("%d\n", *p);
    return 0;
}
X1.7.

[8 pts] As we saw, a C program's memory is divided into two region: the stack and the heap. Explain how its treatment of these two regions of memory differs.

X1.8.

[14 pts] Assume the same struct definitions list and node we used for representing a singly linked list.

struct node {
    int data;
    struct node *next;
};

struct list {
    struct node *head;
};

Complete the function below so that it deletes and deallocates all nodes in the linked list, changing head to NULL.

void list_clear(struct list *lst) {
X1.9.

[8 pts] Perform each of the following conversions. Show your work.

a. 1011010(2) to decimal

b. 49(10) to binary

c. 10111101010011111101101(2) to hexadecimal

X1.10.

[8 pts] Answer the following based on an 8-bit two's-complement representation. Show your work.

a. How is 100 represented?

b. How is −100 represented?

c. What integer does 10111010 represent?

X1.11.

[8 pts] Explain why on many systems, each line break (usually corresponding to pressing just the Enter key) is represented using a sequence of two ASCII symbols, CR and LF.

Test 1: Solutions

X1.1.
int main() {
    int num[100];
    int i;

    for (i = 0; i < 100; i++) {
        scanf("%d", &(num[i]));
    }

    for (i = 99; i >= 0; i--) {
        printf("%d", num[i]);
    }
    return 0;
}
X1.2.

It returns 5.

X1.3.
7 8
8 7 7
X1.4.

A function prototype declares the function's name, the types of its parameters, and its return type, without providing the body of the function. It promises the compiler that the function will be defined, so that we can include code using the function before the function definition is itself encountered. One particularly important place where this is necessary is when the function is used in one C file (so the code in that file uses it without having a definition of how it works) but defined in another file.

X1.5.
int strrepeat(char *s) {
    int i;
    int j;

    for (i = 0; s[i] != '\0'; i++) {
        for (j = i + 1; s[j] != '\0'; j++) {
            if (s[i] == s[j]) {
                return 0;
            }
        }
    }
    return 1;
}
X1.6.

The create_pointer function returns a pointer to its local variable, so main's p variable ends up pointing to that local variable k. However, k is deallocated upon create_pointer's return, and that same memory can be used for other purposes. This is what Ben found; as it happens, that memory was used for another purpose, and the program happens to have placed the number 32,610 into that memory (which was done by printf, by the way). But p is still pointing to that memory location, so when we dereference p, it displays the value currently in that location.

X1.7.

Space for functions' local variables are allocated from the stack, and the space for each local variable is deallocated when the function owning the variable returns.

We allocate space on the heap only through the malloc function; space allocated in this way remains allocated until the program later calls free.

X1.8.
void list_clear(struct list *lst) {
    struct node *n;
    struct node *p;

    n = lst->head;
    lst->head = NULL;
    while (n != NULL) {
        p = n;
        n = n->next;
        free(p);
    }
}
X1.9.
a.1011010(2)= 90(10)
b.49(10)= 110001(2)
c.10111101010011111101101(2)= 5EA7ED(16)
X1.10.

a. 01100100

b. 10011100

c. −70(10)

X1.11.

This is an artifact of the teletypes (electrically controlled typewriters) in heavy use at the time that ASCII was developed. For a typewriter, there are two actions involved in going to the next line: moving the print carriage back to the beginning of line (CR, for Carriage Return) and scrolling the paper up one line (LF, for Line Feed. Many systems have preserved this until today.