Introducción a la Programación

Introducción a la Programación

Parcial de práctica

Semanas 1–7, dos horas. Las soluciones las da el docente.

Parcial de práctica — Introducción a la Programación

Temas: semanas 1 a 7 · Este examen de práctica está pensado para unas 2 horas

Este es un examen de práctica con el formato del parcial. Sirve para medir cuánto tiempo les toma cada tipo de pregunta: resuélvanlo en papel, con el reloj corriendo y sin computadora, y recién después comprueben sus respuestas compilando en el entorno del curso. Las 2 horas son la extensión de esta práctica. Dos horas no alcanzan para todos los temas: el examen real puede preguntar lo que aquí no aparece, como gdb, Git o la lectura de un programa largo.

Indicaciones

  • Lo que importa es la idea: no se preocupen por errores menores de sintaxis.
  • En las preguntas de “qué escribe”, justifiquen con una tabla de variables o un dibujo: una salida sin justificación no muestra cómo llegaron a ella.
  • Todo el código compila sin advertencias con gcc -Wall -Wextra -std=c17, salvo donde la pregunta diga que tiene errores a propósito.
  • Supongan el entorno del curso: un int tiene 32 bits, un puntero ocupa 8 bytes y un size_t también. Las direcciones de memoria no importan: dibújenlas como flechas.
  • Los montos van en céntimos, como enteros.
  • Si les piden una función, no hace falta escribir los #include.
Parte Preguntas Minutos sugeridos
A. Seguir y leer programas 1–4 35
B. Dibujar la memoria 5 12
C. Encontrar el bug 6–7 19
D. Módulos y diseño 8–10 27
E. Escribir funciones 11–12 20
Total 113

Parte A — Seguir y leer programas

Pregunta 1 — Marcos, alcance y tiempo de vida

#include <stdio.h>

struct stand {
    int stock[2];
    int sold;
};

int next_turn(void) {
    static int turn = 40;
    turn += 5;
    return turn;
}

void sell(struct stand s, int prices[], int amount) {
    s.stock[0] -= amount;
    s.sold += amount;
    prices[1] = s.stock[0] * 2;
    amount = 0;
    // AQUÍ
}

struct stand restock(struct stand s, int amount) {
    int total = s.stock[0] + amount;
    {
        int total = next_turn();
        s.sold = total;
    }
    s.stock[1] = total;
    return s;
}

int main(void) {
    struct stand market = {{10, 4}, 0};
    int prices[2] = {3, 7};
    int amount = 6;

    sell(market, prices, amount);
    printf("%d %d %d %d\n", market.stock[0], market.sold, prices[1], amount);

    struct stand other = restock(market, amount);
    printf("%d %d %d\n", other.stock[1], other.sold, market.sold);
    printf("%d\n", next_turn());
    return 0;
}

a) ¿Qué escribe?

b) Dibujen los marcos en el punto AQUÍ, con el valor de cada variable.

c) sell cambia s.stock[0] y prices[1], y solo uno de los dos cambios se ve en main. ¿Por qué, si los dos son elementos de un arreglo?

d) Si se borra la palabra static, ¿qué escribe la última línea? ¿Cambia alguna otra línea? ¿Por qué?

Pregunta 2 — Punteros y arreglos

#include <stdio.h>

void rotate_left(int *a, int n, int *out) {
    *out = *a;
    for (int *p = a; p < a + n - 1; p++) {
        *p = *(p + 1);
    }
    a[n - 1] = *out + 1;
}

int *pick_larger(int *a, int *b) {
    if (*a >= *b) {
        return a;
    }
    return b;
}

int main(void) {
    int v[5] = {8, 3, 6, 1, 4};
    int *p = v + 1;
    int *q = &v[3];
    int extra = 0;

    printf("%d %d %td\n", *p, *q, q - p);
    *p += *q;
    p++;
    *p = p[1] * 10;
    printf("%d %d %d\n", v[1], v[2], *p);
    // AQUÍ
    rotate_left(p, 3, &extra);
    printf("%d %d %d %d %d %d\n", v[0], v[1], v[2], v[3], v[4], extra);
    *pick_larger(&v[0], &extra) = 0;
    printf("%d %d\n", v[0], extra);
    return 0;
}

a) ¿Qué escribe?

b) Dibujen v, p y q en el punto AQUÍ.

c) Si en el punto AQUÍ la llamada fuera rotate_left(p, 0, &extra), ¿cómo quedarían v y extra? ¿Lo avisaría ASan? ¿Y si a recibiera el inicio de un arreglo?

d) En *pick_larger(&v[0], &extra) = 0;, ¿qué variable recibe el 0? ¿Por qué se puede asignar algo al resultado de esa llamada?

Pregunta 3 — Tipos y conversiones

#include <stdio.h>
#include <string.h>

typedef enum { BOX_SMALL, BOX_MEDIUM = 5, BOX_LARGE } BoxKind;

typedef enum { FEE_FLAT, FEE_PER_KG, FEE_FREE } FeeKind;

typedef struct {
    FeeKind kind;
    union {
        int flat;       // FEE_FLAT: céntimos por envío
        double per_kg;  // FEE_PER_KG: soles por kilo
    } as;
} Fee;

int fee_cents(Fee f, int kg) {
    switch (f.kind) {
    case FEE_FLAT:
        return f.as.flat;
    case FEE_PER_KG:
        return f.as.per_kg * kg * 100;
    case FEE_FREE:
        return 0;
    }
    return -1;
}

int main(void) {
    Fee a;
    a.kind = FEE_FLAT;
    a.as.flat = 1200;
    Fee b;
    b.kind = FEE_PER_KG;
    b.as.per_kg = 1.25;

    printf("%d %d\n", BOX_MEDIUM, BOX_LARGE);
    printf("%d %d\n", fee_cents(a, 3), fee_cents(b, 3));

    size_t len = strlen("ica");
    if (len - 5 < 10) {
        puts("corto");
    } else {
        puts("largo");
    }
    printf("%d\n", (int) len - 5);
    printf("%.2f\n", (double) (7 / 2) + 7 / 2.0);
    return 0;
}

a) ¿Qué escribe? Expliquen la tercera línea de la salida y la última.

b) Se agrega al enum una variante FEE_ZONE, y nadie toca fee_cents. ¿Qué dice gcc -Wall? ¿Qué dejaría de decir si el switch tuviera un default? ¿Qué devolvería la función con esa variante, tal como está?

c) Alguien escribe esto, sin constructor. ¿Avisa gcc? ¿Avisan los sanitizers? ¿Qué representa cents?

Fee c;
c.kind = FEE_FLAT;
c.as.per_kg = 2.5;
int cents = c.as.flat;

Pregunta 4 — Leer una función sin comentarios

void mystery(char *s) {
    char *out = s;
    for (const char *in = s; *in != '\0'; in++) {
        if (out == s || *(out - 1) != *in) {
            *out = *in;
            out++;
        }
    }
    *out = '\0';
}

a) ¿Cómo queda cada cadena después de llamar a mystery? "cuuuscoo", "llama", "aAa" y "", cada una guardada en un arreglo char propio.

b) Digan en una frase qué hace la función, y propongan un nombre mejor. ¿Para qué sirve out == s? ¿Qué pasaría sin esa parte?

c) ¿Qué pasa con estas dos líneas? Compilan sin advertencias. ¿Cómo se corrige con un solo cambio?

char *word = "llama";
mystery(word);

Parte B — Dibujar la memoria

Pregunta 5 — Una lista y su copia

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct list {
    char *owner;
    int *prices;
    int n;
};

struct list *list_new(const char *owner, int n) {
    struct list *l = malloc(sizeof *l);
    if (l == NULL) {
        return NULL;
    }
    l->owner = malloc(strlen(owner) + 1);
    l->prices = malloc(n * sizeof *l->prices);
    if (l->owner == NULL || l->prices == NULL) {
        free(l->owner);
        free(l->prices);
        free(l);
        return NULL;
    }
    strcpy(l->owner, owner);
    for (int i = 0; i < n; i++) {
        l->prices[i] = 10 * (i + 1);
    }
    l->n = n;
    return l;
}

int main(void) {
    struct list *a = list_new("Rosa", 3);
    if (a == NULL) {
        return 1;
    }
    struct list b = *a;
    b.prices[0] = 99;
    b.n = 2;
    int *last = a->prices + b.n;
    *last = *last + 1;
    // AQUÍ
    printf("%s %d %d %d\n", a->owner, a->n, a->prices[0], a->prices[2]);
    printf("%s %d %d\n", b.owner, b.n, b.prices[1]);
    free(a->owner);
    free(a->prices);
    free(a);
    return 0;
}

a) Dibujen la pila y el heap en el punto AQUÍ. Cada bloque del heap con sus valores, y cada puntero como una flecha.

b) ¿Qué escribe?

c) ¿Cuántos bloques reserva este programa, y quién es el owner de cada uno? ¿Por qué free(a) tiene que ir al final de los tres? ¿Por qué el free(l->prices) de list_new no falla si fue l->prices el malloc que devolvió NULL?

d) Alguien agrega free(b.prices); después de free(a->prices);, porque “b también tiene sus precios”. ¿Qué dice ASan, y por qué? ¿Qué habría que hacer para que b sí fuera owner de sus propios bloques?

Parte C — Encontrar el bug

Pregunta 6 — Cacería

Los cuatro programas tienen errores de memoria a propósito, y todos revisan su malloc. Para cada uno, digan cuál es el error, qué tipo de informe da ASan al correrlo y cómo lo corregirían cambiando poco.

a)

char *full_name(const char *first, const char *last) {
    char *name = malloc(strlen(first) + strlen(last) + 1);
    if (name == NULL) {
        return NULL;
    }
    strcpy(name, first);
    strcat(name, " ");
    strcat(name, last);
    return name;
}

b)

int *grades = malloc(2 * sizeof *grades);
if (grades == NULL) {
    return 1;
}
grades[0] = 14;
grades[1] = 11;
int *first = grades;
int *grown = realloc(grades, 4 * sizeof *grades);
if (grown == NULL) {
    free(grades);
    return 1;
}
grades = grown;
grades[2] = 17;
printf("%d %d\n", *first, grades[2]);
free(grades);

c) main llama a code_number("CUZ-77") y después a code_number("LIM-204").

// Devuelve el número de un código como "LIM-204", o -1 si no tiene el formato.
int code_number(const char *code) {
    char *copy = malloc(strlen(code) + 1);
    if (copy == NULL) {
        return -1;
    }
    strcpy(copy, code);
    int number;
    if (sscanf(copy, "LIM-%d", &number) != 1) {
        return -1;
    }
    free(copy);
    return number;
}

d)

char *skip_spaces(char *text) {
    while (*text == ' ') {
        text++;
    }
    return text;
}
char *line = malloc(16);
if (line == NULL) {
    return 1;
}
strcpy(line, "   Puno");
line = skip_spaces(line);
printf("%s\n", line);
free(line);

e) Un compañero solo prueba code_number("LIM-204"), y ASan no dice nada. Otro compila el programa b) sin sanitizers, y le sale el número que esperaba. ¿Qué concluyen de cada caso? ¿Qué prueba con assert agregarían para c), y con qué herramienta correrían las pruebas?

Pregunta 7 — ¿Está definido?

Para cada fragmento, digan si tiene comportamiento indefinido. Si no lo tiene, digan qué escribe. Si lo tiene, digan qué herramienta lo encontraría al correr, y corríjanlo sin cambiar lo que se quería.

a)

int low = 2000000000;
int high = 2100000000;
int mid = (low + high) / 2;
printf("%d\n", mid);

b)

unsigned int balance = 3;
balance = balance - 5;
printf("%u\n", balance);

c)

int seats[4];
for (int i = 0; i <= 4; i++) {
    seats[i] = 0;
}

d)

double debt = -1.75;
int whole = debt;
printf("%d\n", whole);

Compilado sin sanitizers, el fragmento a) puede escribir un número y terminar con estado 0. ¿Eso mostraría que está bien? Respondan en una línea.

Parte D — Módulos y diseño

Pregunta 8 — Compilar por partes

Un programa tiene main.c, fare.c y ride.c, con fare.h y ride.h. main.c incluye los dos encabezados, ride.c también, y fare.c incluye solo fare.h. Este es su Makefile:

CC = gcc
CFLAGS = -Wall -Wextra -std=c17

fare_app: main.o fare.o ride.o
	$(CC) $(CFLAGS) main.o fare.o ride.o -o fare_app

main.o: main.c fare.h ride.h
	$(CC) $(CFLAGS) -c main.c

fare.o: fare.c fare.h
	$(CC) $(CFLAGS) -c fare.c

ride.o: ride.c ride.h fare.h
	$(CC) $(CFLAGS) -c ride.c

Y fare.c tiene esta función, además de fare_cents, que es la que declara fare.h:

static int round_up(int cents) {
    return (cents + 49) / 50 * 50;
}

a) Con todo ya compilado, ¿qué archivos .c recompila make, y hay que enlazar otra vez, en cada caso? Son tres casos separados: touch fare.h, touch ride.h y touch fare.c.

b) En main.c, alguien llama a round_up(90). ¿Qué error da, y en qué etapa? Luego agrega en main.c la línea int round_up(int cents);. ¿Qué error da ahora, y en qué etapa? ¿Por qué?

c) Alguien pone el cuerpo de fare_cents en fare.h, dentro de la guarda de inclusión. Cada .c compila. ¿Qué pasa al enlazar? ¿Por qué la guarda no lo evita?

Pregunta 9 — Diseñar un tipo

Una librería aplica a cada venta un descuento, que tiene una de cuatro formas:

  • Ninguno.
  • Un porcentaje, de 0 a 100. Se calcula con división entera: el descuento es cents * percent / 100.
  • Un monto fijo en céntimos.
  • Un vale, que tiene un código de texto de cualquier largo y siempre descuenta 500 céntimos.

El total de una venta nunca baja de 0.

a) Definan el tipo Discount, como una unión etiquetada, de modo que un descuento no pueda tener a la vez porcentaje y monto. Digan en un comentario quién es owner del código del vale.

b) Escriban Discount discount_voucher(const char *code). El Discount guarda su propia copia del código. Si no hay memoria, devuelve lo mismo que discount_none(), una función que ya existe y devuelve un Discount sin descuento.

c) Escriban int discount_apply(const Discount *d, int cents), que devuelve el total a pagar por una venta de cents céntimos. Usen un switch que deje a gcc avisar si mañana aparece otra variante. Con 15 % y 1990 céntimos debe dar 1692.

d) Escriban void discount_free(Discount *d), que libera lo que el descuento posee y lo deja como discount_none(). Luego: ¿qué pasa con este código? ¿Qué dice ASan?

Discount first = discount_voucher("FERIA-26");
Discount second = first;
discount_free(&first);
discount_free(&second);

Pregunta 10 — Diseñar una interfaz

Un consultorio necesita un módulo Waitlist: una lista de espera de nombres, donde quien llega primero se atiende primero. Quien usa el módulo debe poder crear una lista, liberarla, agregar un nombre al final, sacar el primer nombre y preguntar cuántos hay. No hay un máximo de nombres, y el módulo no debe depender de que el texto que le pasan siga existiendo.

a) Escriban waitlist.h completo, con su guarda, un tipo opaco y un comentario por función. Los comentarios deben decir qué pasa si no hay memoria, qué pasa si la lista está vacía y quién libera cada cosa.

b) En main.c, alguien escribe printf("%d\n", w->count);. ¿Qué pasa? ¿Qué gana quien escribió el módulo con que eso no se pueda?

Parte E — Escribir funciones

Pregunta 11 — Parámetros de salida y bloques nuevos

a) Escriban int longest_run(const int *a, int n, int *start, int *length), que busca el tramo más largo de elementos iguales seguidos. Si n es menor que 1, devuelve 0 sin tocar las salidas. Si no, devuelve 1 y deja en *start el índice donde empieza el tramo, y en *length cuántos elementos tiene. Si hay empate, gana el primero. Con {18, 21, 21, 21, 19, 19}, deja 1 y 3.

b) Escriban char *only_digits(const char *text), que devuelve en un bloque nuevo solo las cifras de text, en su orden, o NULL si no hay memoria. Con "987-654 321" da "987654321", y con "sin cifras" da una cadena vacía. El bloque debe tener el tamaño justo. Escriban el comentario que dice quién es el owner.

Pregunta 12 — Implementar el módulo

Vuelvan a Waitlist. Usen esta representación, y estas dos firmas aunque en la pregunta 10 hayan elegido otras:

struct entry {
    char *name;  // bloque propio; lo posee esta entrada
};

struct waitlist {
    struct entry *entries;
    int count;
    int capacity;
};

waitlist_new deja entries en NULL, y count y capacity en 0.

a) Escriban int waitlist_push(Waitlist *w, const char *name). Agrega una copia de name al final, y devuelve 1. Si no hay memoria, devuelve 0, y la lista queda igual y sin fugas. Cuando no hay espacio, la capacidad pasa de 0 a 2, y después se duplica.

b) Escriban char *waitlist_pop(Waitlist *w). Saca el primer nombre y lo devuelve, y quien llama pasa a ser su owner. Los demás avanzan un lugar. Si la lista está vacía, devuelve NULL.