Introducción a la Programación

Introducción a la Programación

Final de práctica

Todo el curso, con énfasis en las semanas 9–15. Dos horas.

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

Temas: todo el curso, con énfasis en las semanas 9 a 15 · Este examen de práctica está pensado para unas 2 horas

Este es un examen de práctica con el formato del final. 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 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 ordenar por mezcla, flood fill o el análisis léxico en detalle.

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, un árbol 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 y un puntero ocupa 8 bytes. Las direcciones de memoria no importan: dibújenlas como flechas.
  • El pseudocódigo va en el formato del curso: ←, mientras, si, para, devolver.
  • Si les piden una función, no hace falta escribir los #include. Pueden usar string.h.
Parte Preguntas Minutos sugeridos
A. Repaso de las semanas 1 a 7 1–2 18
B. Recursión 3–5 25
C. Backtracking 6–7 22
D. Funciones como valores 8 12
E. Datos recursivos 9 20
F. El intérprete 10–11 18
Total 115

Parte A — Repaso de las semanas 1 a 7

Pregunta 1 — Leer un archivo

El archivo ventas.txt tiene estas líneas:

cancha 350
choclo x
chicha 400 extra
emoliente 150
anticucho 1200
mazamorra 300
#include <stdio.h>

#define LINE_SIZE 32
#define MAX_SALES 3

struct sale {
    char item[16];
    int cents;
};

int read_sales(FILE *file, struct sale *sales, int max, int *bad) {
    char line[LINE_SIZE];
    int count = 0;
    *bad = 0;
    while (count < max && fgets(line, LINE_SIZE, file) != NULL) {
        char extra[2];
        int fields = sscanf(line, "%15s %d %1s", sales[count].item, &sales[count].cents, extra);
        if (fields == 2) {
            count++;
        } else {
            (*bad)++;
        }
    }
    return count;
}

int main(void) {
    FILE *file = fopen("ventas.txt", "r");
    if (file == NULL) {
        perror("ventas.txt");
        return 1;
    }
    struct sale sales[MAX_SALES];
    int bad;
    int count = read_sales(file, sales, MAX_SALES, &bad);
    fclose(file);

    int total = 0;
    int best = 0;
    for (int i = 0; i < count; i++) {
        total += sales[i].cents;
        if (sales[i].cents > sales[best].cents) {
            best = i;
        }
    }
    printf("%d %d\n", count, bad);
    printf("S/ %d.%02d\n", total / 100, total % 100);
    printf("%s\n", sales[best].item);
    return 0;
}

a) ¿Qué escribe? Digan qué devuelve sscanf con cada línea que se llega a leer. ¿Cuál línea no se lee?

b) Si la condición del while se escribe al revés, fgets(line, LINE_SIZE, file) != NULL && count < max, ¿cambia lo que escribe este programa? ¿Qué cambia para quien quisiera seguir leyendo el archivo después de read_sales?

c) Si ventas.txt está vacío, ¿hay algún problema en este programa? ¿En cuál línea? ¿Lo encontraría ASan? Corríjanlo.

Pregunta 2 — Dos niveles de punteros

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

char *copy_text(const char *text) {
    char *copy = malloc(strlen(text) + 1);
    if (copy != NULL) {
        strcpy(copy, text);
    }
    return copy;
}

int main(void) {
    int n = 3;
    char **names = malloc(n * sizeof *names);
    if (names == NULL) {
        return 1;
    }
    names[0] = copy_text("Ana");
    names[1] = copy_text("Beto");
    names[2] = names[0];
    if (names[0] == NULL || names[1] == NULL) {
        free(names[0]);
        free(names[1]);
        free(names);
        return 1;
    }
    names[2][0] = 'E';
    char *second = names[1];
    second++;
    // AQUÍ
    printf("%s %s %s %s\n", names[0], names[1], names[2], second);
    free(names[0]);
    free(names[1]);
    free(names);
    return 0;
}

a) Dibujen la pila y el heap en el punto AQUÍ.

b) ¿Qué escribe?

c) Alguien cambia las tres llamadas finales a free por este código, “para no repetir”. ¿Qué dice ASan, y por qué? ¿Qué regla de ownership rompió el programa desde names[2] = names[0];?

for (int i = 0; i < n; i++) {
    free(names[i]);
}
free(names);

Parte B — Recursión

Pregunta 3 — Antes y después de la llamada

void weave(const char *s, int depth) {
    if (*s == '\0') {
        printf("|");
        return;
    }
    if (depth % 2 == 0) {
        putchar(*s);
    }
    weave(s + 1, depth + 1);
    if (depth % 2 == 1) {
        putchar(*s);
    }
}

a) ¿Qué escriben weave("tacna", 0) y weave("", 0)?

b) Dibujen los marcos de weave durante weave("ica", 0), en la llamada que llega al caso base. Para cada marco, digan qué vale depth y a qué cadena apunta s. ¿Cuántos marcos de weave hay?

c) Alguien cambia la llamada por weave(s + 1, depth++);. Compila sin advertencias. ¿Qué escribe ahora weave("ica", 0)? ¿Por qué?

Pregunta 4 — Subir gradas

En una escalera de piedra se puede subir de 1 en 1 o de 3 en 3 gradas. Esta función cuenta de cuántas formas se suben n gradas:

long ways(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return 1;
    }
    return ways(n - 1) + ways(n - 3);
}

a) Dibujen el árbol de llamadas de ways(4), incluyendo las llamadas con n negativo. ¿Qué devuelve? ¿Cuántas llamadas hay en total? ¿Cuántos marcos de ways, como máximo, existen a la vez? ¿Cuántas veces aparece ways(1)?

b) Escriban long ways_memo(int n, long *memo). memo tiene n + 1 elementos al empezar, todos en -1, y quien llama es su owner. ¿Por qué esta función sí se puede memoizar?

c) Con n igual a 30, la versión sin memoria hace 250981 llamadas, y la versión con memoria hace 61. Expliquen por qué la segunda no pasa de unas 2 llamadas por cada valor de n. ¿Dónde hay que revisar que n no sea negativo, antes o después de leer memo[n]? ¿Por qué?

Pregunta 5 — Una recursión que no termina

Tiene un error a propósito. low y high son los dos extremos incluidos, y a está ordenado.

int find(const int *a, int low, int high, int target) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (a[mid] == target) {
        return mid;
    }
    if (a[mid] < target) {
        return find(a, mid, high, target);
    }
    return find(a, low, mid - 1, target);
}

a) Con int a[] = {2, 5, 8, 11};, sigan find(a, 0, 3, 8), find(a, 0, 3, 1) y find(a, 0, 3, 11). ¿Qué devuelve cada una? Una no termina: ¿qué dice ASan?

b) ¿Por qué no alcanza con que find tenga un caso base?

c) Corrijan la función. ¿Qué cantidad baja en cada llamada? Muéstrenlo para las dos llamadas recursivas.

Parte C — Backtracking

Pregunta 6 — Pagar con monedas

void pay(const int *coins, int n, int start, int left, int *chosen, int count, int *nodes) {
    (*nodes)++;
    if (left == 0) {
        for (int i = 0; i < count; i++) {
            printf("%d ", chosen[i]);
        }
        printf("\n");
        return;
    }
    for (int i = start; i < n; i++) {
        if (coins[i] > left) {
            break;
        }
        chosen[count] = coins[i];
        pay(coins, n, i, left - coins[i], chosen, count + 1, nodes);
    }
}

main la llama así:

int coins[] = {1, 2, 5};
int chosen[5];
int nodes = 0;
pay(coins, 3, 0, 5, chosen, 0, &nodes);
printf("nodos: %d\n", nodes);

a) ¿Qué escribe? Dibujen el árbol: cada nodo con su left.

b) Aquí nadie deshace nada después de la llamada. ¿Por qué no hace falta?

c) Con {5, 1, 2} y un monto de 4, ¿qué escribe? ¿Se perdieron soluciones? ¿Qué suponía el break, y qué dos formas hay de arreglarlo?

Pregunta 7 — Sentar a los invitados

Hay n invitados, numerados desde 0, para sentar en una fila. Algunos pares no quieren estar uno al lado del otro: conflict[a][b] vale 1 si a y b no pueden sentarse juntos, y 0 si pueden. La matriz es simétrica. MAX_GUESTS es una constante, al menos tan grande como n. Queremos encontrar un orden válido.

a) ¿Qué se decide en cada nivel del árbol? ¿Qué profundidad tiene? ¿Cuántas hojas tiene el árbol completo con 4 invitados, sin revisar los choques, y sin repetir a nadie? ¿Qué rama se puede podar, y por qué esa poda no pierde soluciones?

b) Escriban esta función, recursiva, que se detiene en la primera solución:

int seat_guests(int n, const int conflict[][MAX_GUESTS], int pos, int *row, int *used) {

row[i] es el invitado del lugar i, y ya están elegidos los lugares antes de pos. used[g] vale 1 si el invitado g ya está sentado. Devuelve 1 si se puede completar la fila, y la deja en row. Si devuelve 0, used queda como estaba. Prueben a los invitados en orden, desde el 0.

c) Con 4 invitados, donde solo chocan los pares 0-1, 1-2 y 2-3, sigan su función desde pos 0, con used en cero. Anoten cada invitado que se sienta y cada vez que se deshace. ¿Cómo queda row?

Parte D — Funciones como valores

Pregunta 8 — Corredores y reglas

typedef struct {
    char name[16];
    char city[16];
    int seconds;
} Runner;

a) Escriban int compare_runners(const void *first, const void *second), para qsort: primero el que hizo menos segundos y, si empatan, por nombre. Escriban también la llamada a qsort para un arreglo runners de 5 elementos. ¿Por qué no conviene return a->seconds - b->seconds; en un comparador?

b) Con este tipo y este contexto:

typedef int (*RunnerTest)(const Runner *r, void *context);
typedef struct {
    const char *city;
    int limit;
} CityLimit;

Escriban const Runner *first_where(const Runner *runners, int n, RunnerTest test, void *context), que devuelve el primero que pasa la prueba, o NULL. Escriban también el callback from_city_under, que acepta a un corredor de la ciudad city que hizo menos de limit segundos. Escriban la llamada para Puno y 3000 segundos.

c) ¿Qué escribe este programa?

#include <stdio.h>

typedef int (*Rule)(int value);

int plus_three(int value) {
    return value + 3;
}

int half(int value) {
    return value / 2;
}

int square(int value) {
    return value * value;
}

int run_rules(int value, const Rule *rules, int n) {
    if (n == 0) {
        return value;
    }
    return run_rules(rules[0](value), rules + 1, n - 1);
}

int main(void) {
    const Rule rules[] = {plus_three, half, square};
    printf("%d\n", run_rules(5, rules, 3));
    printf("%d\n", run_rules(5, rules + 1, 2));
    printf("%d\n", run_rules(5, rules, 0));
    printf("%d\n", rules[2](rules[0](1)));
    return 0;
}

Parte E — Datos recursivos

Pregunta 9 — Planes de viaje

Un plan de viaje es un tramo con su costo, una secuencia de dos planes (se hacen los dos) o una elección entre dos planes (se hace uno, y conviene el más barato).

typedef enum { PLAN_LEG, PLAN_SEQ, PLAN_CHOICE } PlanKind;

typedef struct Plan {
    PlanKind kind;
    union {
        int cost;  // PLAN_LEG: céntimos
        struct {
            struct Plan *first;   // lo posee este nodo
            struct Plan *second;  // lo posee este nodo
        } pair;    // PLAN_SEQ y PLAN_CHOICE
    } as;
} Plan;

// Los constructores se quedan con sus hijos, también si fallan, y aceptan hijos NULL.
Plan *plan_leg(int cost);
Plan *plan_seq(Plan *first, Plan *second);
Plan *plan_choice(Plan *first, Plan *second);

a) Dibujen el árbol de este plan. ¿Cuántos nodos tiene, y cuántos malloc exitosos hace construirlo? ¿Cuánto cuesta? Si el malloc del plan_leg(4500) falla, ¿hay fugas? ¿Quién libera lo que ya estaba?

Plan *trip = plan_seq(plan_leg(6000),
                      plan_choice(plan_leg(12000),
                                  plan_seq(plan_leg(3000), plan_leg(4500))));

b) Escriban int plan_cost(const Plan *p), recursiva, con un switch sin default.

c) Escriban void plan_free(Plan *p). Debe aceptar NULL. ¿Por qué tiene que aceptarlo? ¿En qué orden se libera, y por qué?

d) Escriban Plan *plan_copy(const Plan *p), que devuelve un árbol nuevo, o NULL si no hay memoria y sin fugas. Si usan bien los constructores, esto se escribe en pocas líneas.

e) Esta función tiene dos errores a propósito. Encuéntrenlos, digan qué informe da ASan para cada uno, con un plan pequeño que lo muestre, y corríjanlos.

// Se queda con p. Devuelve el plan sin elecciones: de cada PLAN_CHOICE deja la rama más barata.
Plan *plan_cheapest(Plan *p) {
    if (p->kind == PLAN_LEG) {
        return p;
    }
    Plan *first = plan_cheapest(p->as.pair.first);
    Plan *second = plan_cheapest(p->as.pair.second);
    if (p->kind == PLAN_SEQ) {
        p->as.pair.first = first;
        p->as.pair.second = second;
        return p;
    }
    if (plan_cost(first) <= plan_cost(second)) {
        free(p);
        return first;
    }
    plan_free(p);
    return second;
}

Parte F — El intérprete

Pregunta 10 — Una gramática nueva

Un lenguaje de fórmulas tiene números enteros y tres operaciones: a - b es la resta, a | b es el menor de los dos, y a ^ b es la potencia.

expr  → least ("-" least)*
least → power ("|" power)*
power → atom [ "^" power ]
atom  → NUMBER | "(" expr ")"

a) ¿Cuántos tokens tiene 12-(3^2)|1? Escríbanlos.

b) Dibujen el árbol de 9 - 2 ^ 3 | 5 - 1. ¿Cuántos nodos tiene? ¿Cuánto vale?

c) ¿Cuánto vale 2 ^ 3 ^ 2? ¿Y 8 - 3 - 1? ¿Qué parte de cada regla decide con qué lado se agrupa?

d) Escriban en pseudocódigo la función del parser para la regla least. Supongan que ya existen analizar_power(), siguiente_es(token), avanzar() y nodo(op, izquierda, derecha). No hace falta tratar los errores. ¿Por qué no se puede escribir la regla como least → least "|" power?

e) Con (4 - 1, ¿en qué columna se detecta el error, si la primera es la 1, y qué se esperaba? Justo en ese momento, ¿qué ya se había construido, y quién debe liberarlo?

Pregunta 11 — Seguir un programa de Mini

let k = 2
def twice(k) = k * 2 + base
def up(n) = if n > 6 then n else up(twice(n))
let base = 1
print up(k)
print k
let base = 0
print up(1)
print twice(z)
print 100

a) ¿Qué escribe? ¿En qué línea se detiene, y con qué error? ¿Por qué twice puede nombrar a base si base no existe todavía cuando corre el def?

b) Durante el primer print, ¿cuántos marcos de Mini existen, como máximo, a la vez, contando el global? Dibújenlos en un momento de mayor profundidad, con el valor de cada variable. ¿De qué marco cuelga el marco de twice, y por qué no del marco de up?

c) Dibujen el árbol de k * 2 + base. ¿Cuántos nodos tiene? Cuando twice se llama con 5 y base vale 1, ¿en qué orden terminan de evaluarse esos nodos?

Antes del final: lo que deberían poder hacer

Estos son los resultados de aprendizaje del programa del curso. Marquen cada uno cuando puedan hacerlo sin mirar los apuntes. Al lado están las semanas donde se trabaja y las preguntas de este examen que lo ejercitan.

  • Puedo explicar qué pasa en la memoria al ejecutar un programa, dibujando marcos de llamada, alcance y tiempo de vida. Semanas 3, 4, 5 y 9. Preguntas 2a, 3b y 11b.
  • Puedo usar punteros y memoria dinámica sin fugas ni accesos inválidos, y comprobarlo con ASan y valgrind. Semanas 4 y 5. Preguntas 2, 9c, 9d y 9e.
  • Puedo dividir un programa en módulos con una interfaz clara, ocultando la representación con tipos opacos. Semana 6. Este final no lo pregunta: practíquenlo con las preguntas 8 y 10 del parcial de práctica.
  • Puedo definir tipos adecuados al problema con typedef, enum, struct y uniones etiquetadas, y reconocer el comportamiento indefinido. Semana 7. Preguntas 2c, 9a y 9b.
  • Puedo resolver problemas con recursión, recursión en árbol y backtracking, y razonar por qué un programa recursivo es correcto y termina. Semanas 9, 10 y 11. Preguntas 3, 4, 5, 6 y 7.
  • Puedo pasar funciones como valores con punteros a función y un contexto void *. Semana 12. Pregunta 8.
  • Puedo escribir pruebas que se apoyen en la interfaz, y depurar con método usando gdb y las herramientas de diagnóstico. Semanas 1, 5 y 6, y todos los laboratorios. Preguntas 1c, 5 y 9e, que son de depurar. Escribir pruebas no entra en este final: se practica en los laboratorios y en la Práctica 1.
  • Puedo leer código ajeno, entenderlo y extenderlo sin romperlo. Semana 2. Preguntas 1a, 1b, 6, 8c y 11a.
  • Puedo construir un intérprete pequeño: análisis léxico, análisis sintáctico y evaluación recursiva. Semanas 13, 14 y 15. Preguntas 9, 10 y 11.