Final de práctica — Estructuras de Datos
Temas: todo el curso, con énfasis en las semanas 9 a 15 · Tiempo de trabajo estimado: 155 minutos
Este es un examen de práctica con el formato del final. Sirve para medir cuánto les toma cada tipo de pregunta: resuélvanlo en papel, con el reloj corriendo, y recién después comprueben sus respuestas con los programas de cada semana. Cada pregunta trae su tiempo estimado.
Indicaciones
- Muestren el procedimiento: el resultado solo no basta. Si arrastran un error de un inciso al siguiente, el siguiente se revisa con su número.
- Los errores menores de sintaxis en C++ no importan si la idea es correcta.
- Los árboles se pueden escribir en una línea, como en los programas del curso:
clave(izquierdo,derecho), con_si falta un hijo y con unardespués de la clave si el nodo es rojo. Por ejemplo,5(3r,_)es un 5 negro con un 3 rojo a su izquierda.
Convenciones del curso
- Altura: un nodo nulo tiene altura −1, y una hoja, altura 0. Balance: altura del subárbol izquierdo menos altura del derecho. Positivo: pesa más la izquierda.
- Borrar un nodo con dos hijos: se copia la clave del sucesor y se quita el nodo del sucesor del subárbol derecho.
- Árbol rojinegro: el clásico, sin inclinación. El nodo nuevo entra rojo.
- Min-heap: en un arreglo que empieza en 0. El padre de i es (i − 1) div 2, y los hijos, 2i + 1 y 2i + 2.
- Dijkstra: las entradas del heap son pares (distancia, nodo). A igual distancia sale primero el nodo menor. No se actualizan entradas: una entrada de un nodo ya sacado se ignora al salir.
- Grafos: los vecinos se recorren en el orden en que aparecen en la lista que da el enunciado.
| Parte | Preguntas | Minutos |
|---|---|---|
| A. Simular a mano | 1–6 | 80 |
| B. Analizar costos | 7 | 15 |
| C. Elegir una estructura | 8 | 10 |
| D. Encontrar el bug | 9 | 15 |
| E. Interpretar mediciones | 10 | 15 |
| F. Escribir código | 11 | 20 |
| Total | 155 |
Parte A — Simular a mano
Pregunta 1 — Direccionamiento abierto con tombstones
Tiempo estimado: 12 min
Una tabla de m = 13 casillas usa h(k) = k mod 13, linear probing y tombstones. No guarda claves repetidas: si se inserta una clave que ya está, solo se reemplaza su valor. Si se puede, una inserción reúsa un tombstone, con las reglas de la clase.
a) Inserten, en este orden, 18, 31, 44, 7, 20, 12 y 25. Dibujen la tabla.
b) Borren el 31 y el 7. Dibujen la tabla, con X en cada tombstone. Luego digan qué casillas revisa,
en orden, buscar el 20 y buscar el 57, y qué responde cada búsqueda.
c) A partir de la tabla de b), inserten 57, 20 y 38, en ese orden. Para cada una, digan qué casillas recorre y dónde queda la clave. Dibujen la tabla final.
d) En la tabla final, ¿cuánto vale n/m, y cuánto (n + t)/m, si t es la cantidad de tombstones? ¿Cuál de los dos decide el costo de una búsqueda sin éxito? Además, si la tabla de b) usara encadenamiento con las mismas 13 casillas y las mismas claves vivas, ¿cuántas claves compararía buscar el 57? ¿Necesitaría tombstones?
Pregunta 2 — AVL
Tiempo estimado: 15 min
a) Inserten 40, 20, 30, 60, 50, 10, 5 y 45 en un AVL vacío. Por cada inserción que necesite una reparación, digan en qué nodo se desbalanceó, con qué balance quedaron ese nodo y su hijo pesado, qué caso es y cómo queda el árbol.
b) Partan de este AVL, y borren el 25. Digan qué clave reemplaza al 25, qué nodos se reparan, en qué orden y con qué caso, y cómo queda el árbol.
40(25(20(10,_),30),55(50(45,_),70(65,75(_,95))))c) En el AVL 80(40(20(10,30),60(_,70)),90(_,95)), borren el 95. ¿Cuál es el balance del hijo pesado? ¿Qué
rotación corresponde, y cómo queda el árbol? ¿Qué nodo quedaría mal si se hiciera la otra rotación (doble en vez de
simple, o simple en vez de doble)?
Pregunta 3 — Árbol rojinegro
Tiempo estimado: 15 min
Inserten en un árbol rojinegro vacío las claves 30, 25, 10, 5, 75, 45, 60, 35, 95, 65, en ese orden.
a) Por cada inserción, digan qué se aplicó: nada, tío rojo, tío negro en línea, tío negro en zigzag o pintar la raíz de negro. Si una inserción aplica más de una cosa, digan cuáles y en qué nodo. Escriban el árbol después de la última inserción.
b) Escriban el árbol 2-3-4 que representa el árbol final. Digan en qué inserciones se dividió un nodo del árbol 2-3-4, y en cuál de ellas ganó un nivel.
c) ¿Cuánto miden la altura y la altura negra del árbol final, sin contar las hojas nulas? ¿Cuántas rotaciones y cuántas veces el caso del tío rojo hubo en total?
Pregunta 4 — Heap y Huffman
Tiempo estimado: 12 min
a) Construyan un min-heap de abajo hacia arriba a partir de este arreglo, y escriban el arreglo después de tratar cada índice. ¿Cuántos niveles bajaron en total? ¿Qué tiene que ver esa cuenta con que construir cueste Θ(n)?
14 9 12 3 7 5 11 2b) Sobre ese heap, saquen el mínimo, inserten 1 e inserten 6. Escriban el arreglo después de cada operación.
c) Construyan el árbol de Huffman de estas frecuencias:
a: 11 b: 6 c: 5 d: 3 e: 2 f: 2A igual peso sale primero el árbol creado antes, y las hojas se crean en orden alfabético. El primero que sale del heap es el hijo izquierdo, con bit 0. Escriban cada unión, los códigos y el total de bits. Comparen con un código de longitud fija. ¿Cambiaría el total de bits con otro desempate?
Pregunta 5 — Recorridos y union-find
Tiempo estimado: 14 min
Un grafo no dirigido de 8 nodos tiene estas listas de adyacencia:
0: 3 1
1: 0 4 2
2: 1 5
3: 0 6
4: 1 5
5: 4 2 7
6: 3 7
7: 6 5a) Corran BFS desde el 0. Escriban la cola en cada paso, el orden de visita, la distancia y el padre de cada nodo, y el camino al 7. ¿Cuántas veces entraría el 5 a la cola si, por error, se marcara un nodo al sacarlo de la cola en vez de al meterlo?
b) Corran DFS recursivo desde el 0 y escriban el orden de visita. ¿Cuántas aristas tiene el camino que siguió DFS desde el 0 hasta el 2? ¿Y el de BFS?
c) Ahora, sin relación con el grafo, un union-find de 8 elementos usa unión por rango y compresión de
caminos. Con rangos iguales, la raíz de b cuelga de la raíz de a en unite(a, b), y el rango de esa raíz sube en 1. El
find que hace cada unite también comprime. Hagan, en este orden:
unite(1, 2) unite(3, 4) unite(2, 4) unite(5, 6) unite(7, 5) unite(6, 4) unite(0, 3)Escriban los arreglos parent y rango al terminar. Luego hagan find(7): ¿cuántos saltos da por parent, y cómo
queda parent? Después hagan find(6). ¿Cuánto miden ahora la altura del árbol y el rango de su raíz? ¿Por qué no
coinciden? ¿Qué devuelve unite(2, 7)?
Pregunta 6 — Dijkstra
Tiempo estimado: 12 min
Un grafo no dirigido de 6 nodos tiene estas listas, con los pesos entre paréntesis:
0: 1(7) 2(2)
1: 0(7) 2(3) 3(1)
2: 0(2) 1(3) 3(8) 4(3)
3: 1(1) 2(8) 5(5)
4: 2(3) 5(9)
5: 3(5) 4(9)a) Corran Dijkstra desde el 0 hasta vaciar el heap. En cada fila escriban la entrada que sale, los vecinos cuya distancia mejora, el arreglo de distancias y el heap en orden de salida. Marquen las entradas viejas.
b) Escriban la ruta de Dijkstra al 5 y la de BFS al 5, con sus aristas y su peso. Para BFS, usen las mismas listas. ¿Qué responde cada una?
c) ¿Cuántas entradas entraron al heap, cuántas salieron como viejas, y cuántas entradas de listas se leyeron? ¿Cuál es el máximo de entradas que permite el análisis de la clase para este grafo?
d) Alguien detiene la búsqueda cuando el 5 entra al heap por primera vez. ¿Qué distancia responde? ¿Por qué hay que detenerse al sacar el destino?
Parte B — Analizar costos
Pregunta 7 — Costo amortizado y fragmentos de código
Tiempo estimado: 15 min
a) Un arreglo dinámico empieza vacío, con capacidad 0. push duplica la capacidad al llenarse (de 0 pasa a
- y traslada todos los elementos que tiene. Después de cada
pop, el arreglo encoge a la mitad de su capacidad si la capacidad es mayor que 4 y el tamaño llegó al límite de su regla. Al encoger traslada los elementos que quedan. Hay dos reglas: regla 1/2, encoger si tamaño ≤ capacidad/2, y regla 1/4, encoger si tamaño ≤ capacidad/4.
Para cada regla, hagan esta serie y digan cuántos traslados hace cada tramo, y cómo quedan el tamaño y la capacidad:
- 17
push. - 10 pares
pop,push. - Con la regla 1/4, además, 13
popmás.
Luego expliquen, en pocas líneas, por qué con la regla 1/4 el costo amortizado de cada operación es O(1), y qué costo total tiene una serie de n operaciones con la regla 1/2 en el peor caso.
b) Den el costo de cada fragmento en función de n (y de k en D), con Θ, y justifiquen en una o dos líneas.
a es un std::vector<int> de tamaño n.
// Fragmento A
for (int i = n; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
steps++;
}
}
// Fragmento B
std::vector<int> stack;
for (int value : a) {
while (!stack.empty() && stack.back() >= value) {
stack.pop_back();
}
stack.push_back(value);
}
// Fragmento C
std::vector<int> v;
for (int i = 0; i < n; i++) {
v.insert(v.begin(), i);
}
// Fragmento D, con k >= 1 y k <= n
std::priority_queue<int> heap;
for (int value : a) {
heap.push(value);
if (heap.size() > k) {
heap.pop();
}
}En B, ¿cuántas veces puede correr el while en un solo paso del for? ¿Contradice eso su respuesta?
Parte C — Elegir una estructura
Pregunta 8 — Qué estructura y por qué
Tiempo estimado: 10 min
Para cada problema, elijan una estructura del curso. Digan qué operación decide la elección, con su costo, y qué alternativa razonable descartan y por qué.
a) Un sistema de reservas de una sala guarda la hora de inicio de cada reserva. Se agregan y se cancelan reservas, y constantemente se pregunta cuál es la siguiente reserva después de una hora dada.
b) De un flujo de 500 millones de ventas se quieren los 100 montos mayores, con memoria para unos pocos miles de números.
c) Una red eléctrica va tendiendo cables entre subestaciones, y nunca los retira. Después de cada cable nuevo, se pregunta si dos subestaciones ya están conectadas.
d) Un sensor manda una lectura por segundo. Hay que conservar solo las últimas 1000 y calcular su promedio después de cada lectura.
e) Un corrector carga un diccionario fijo de 300 000 palabras y luego pregunta millones de veces si una palabra exacta está. Nunca necesita orden ni rangos.
f) Hay que calcular caminos mínimos desde un origen en un grafo de 2000 nodos donde casi todo par de nodos tiene una arista con peso no negativo. ¿Qué representación del grafo y qué versión de Dijkstra usarían?
Parte D — Encontrar el bug
Pregunta 9 — Cuatro programas con un error
Tiempo estimado: 15 min
Los programas compilan con g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined, sin advertencias. Para cada
uno, digan qué pasa al correrlo (qué reporta ASan o qué falla, y en qué momento), expliquen la causa y escriban el
arreglo más corto.
a)
class IntTree {
public:
IntTree() = default;
~IntTree() { destroy(root_); }
void insert(int key) { root_ = insert_at(root_, key); }
void print() const { print_at(root_); std::cout << "\n"; }
private:
struct Node {
int key;
Node* left = nullptr;
Node* right = nullptr;
};
static Node* insert_at(Node* node, int key) {
if (node == nullptr) {
return new Node{key};
}
if (key < node->key) {
node->left = insert_at(node->left, key);
} else if (node->key < key) {
node->right = insert_at(node->right, key);
}
return node;
}
static void print_at(const Node* node) {
if (node != nullptr) {
print_at(node->left);
std::cout << node->key << " ";
print_at(node->right);
}
}
static void destroy(Node* node) {
if (node != nullptr) {
destroy(node->left);
destroy(node->right);
delete node;
}
}
Node* root_ = nullptr;
};
void show(IntTree tree) {
tree.print();
}
int main() {
IntTree tree;
tree.insert(5);
tree.insert(3);
show(tree);
tree.insert(8);
return 0;
}b) current señala la canción que está sonando en una lista de reproducción. Además de lo pedido, digan si el
push_back invalida a current, y qué debe imprimir el programa arreglado.
int main() {
std::list<int> playlist = {11, 24, 30, 37};
auto current = playlist.begin();
++current;
playlist.push_back(42);
playlist.erase(current);
++current;
std::cout << *current << "\n";
return 0;
}c) Este sift_down es de un min-heap de enteros cuyos push, pop y top están bien. Den una serie corta
de operaciones que muestre el error, con lo que devuelve top y lo que debería devolver.
void sift_down(std::size_t i) {
while (true) {
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
std::size_t smallest = i;
if (left < items_.size()) {
if (items_[left] < items_[smallest]) {
smallest = left;
}
}
if (right < items_.size()) {
if (items_[right] < items_[i]) {
smallest = right;
}
}
if (smallest == i) {
return;
}
std::swap(items_[i], items_[smallest]);
i = smallest;
}
}d) Este es el borrado de un AVL recursivo, con rebalance como en la clase: actualiza la altura del nodo, lo
repara si hace falta y devuelve la raíz de su subárbol. check_invariants comprueba el orden, cada altura guardada y la
condición AVL. ¿Qué pasa al borrar el 40 de 40(20(10,30),50) y llamar a check_invariants? ¿Cómo debería quedar el
árbol?
Node* erase_at(Node* node, const K& key, bool& erased) {
if (node == nullptr) {
return nullptr;
}
if (key < node->key) {
node->left = erase_at(node->left, key, erased);
} else if (node->key < key) {
node->right = erase_at(node->right, key, erased);
} else {
erased = true;
if (node->left == nullptr || node->right == nullptr) {
Node* child = node->left != nullptr ? node->left : node->right;
delete node;
return child;
}
const Node* next = node->right;
while (next->left != nullptr) {
next = next->left;
}
node->key = next->key;
bool ignored = false;
node->right = erase_at(node->right, node->key, ignored);
return node;
}
return rebalance(node);
}Parte E — Interpretar mediciones
Pregunta 10 — Dos tablas
Tiempo estimado: 15 min
a) Este programa del curso usa una tabla de 1024 casillas con linear probing, y siempre 100 claves vivas. Un
cambio borra una clave e inserta otra. casillas es el promedio que revisa una búsqueda sin éxito. Todo es conteo: no
hay reloj.
Nunca se limpia y nunca se reúsa:
cambios tombstones casillas rebuilds
0 0 1.1 0
100 100 1.3 0
500 500 3.4 0
923 923 515.2 0
(solo queda una casilla vacía: sin reusar tombstones ya no se puede insertar)
Se reúsan tombstones al insertar:
cambios tombstones casillas rebuilds
0 0 1.1 0
100 96 1.3 0
500 388 1.9 0
1000 601 3.2 0
5000 921 185.9 0
50000 924 1024.0 0
Se reúsan y se reconstruye al pasar 0.7:
cambios tombstones casillas rebuilds
0 0 1.1 0
100 96 1.3 0
500 388 1.9 0
1000 601 3.2 0
5000 597 3.1 4
50000 612 3.3 48El promedio de casillas de una búsqueda sin éxito con linear probing es, según el análisis clásico, (1 + 1/(1 − α)²) / 2.
- En la fila de 500 cambios de la primera tabla, calculen la predicción con α = n/m y con α = (n + t)/m. ¿Cuál se acerca a lo medido, y qué significa eso?
- La segunda tabla tiene el mismo número de claves vivas que las otras. ¿Por qué su última fila revisa las 1024 casillas?
Si
tombstonesmás claves vivas ya da 1024, ¿qué tipo de casilla no queda? - En la tercera tabla, ¿cuántas claves se reinsertaron en total en las 48 reconstrucciones, y cuántas son por cambio? ¿Qué dice eso del costo amortizado de reconstruir?
b) Estos son tiempos en segundos de ordenar n números, en una laptop, con -O2. Son medianas de 5 corridas y
dependen de la máquina:
n heapsort std::sort stable_sort heap/sort
100000 0.0054 0.0056 0.0060 0.97
200000 0.0128 0.0115 0.0130 1.11
400000 0.0295 0.0246 0.0279 1.20
800000 0.0690 0.0525 0.0586 1.31
1600000 0.1555 0.1095 0.1239 1.42
3200000 0.3668 0.2280 0.2610 1.61Y este es un conteo, que no depende de la máquina: las lecturas y escrituras de un heapsort y de un mergesort escrito igual de simple, pasadas por un modelo de cache de 32 KB:
n algoritmo accesos fallos fallos/n
1000 heapsort 28314 63 0.06
1000 mergesort 28738 125 0.12
10000 heapsort 384749 2123 0.21
10000 mergesort 403636 17529 1.75
100000 heapsort 4843204 426879 4.27
100000 mergesort 4966873 276756 2.77
1000000 heapsort 58341042 8949218 8.95
1000000 mergesort 58715769 3469588 3.47
4000000 heapsort 257368630 46618943 11.65
4000000 mergesort 258862982 14982452 3.75- De n = 100 000 a n = 3 200 000, ¿por cuánto debería multiplicarse el tiempo si fuera proporcional a n log n? ¿Por cuánto se multiplicó en cada columna? Usen log₂ 100 000 ≈ 16.6 y log₂ 3 200 000 ≈ 21.6.
- Los tres algoritmos son O(n log n) en promedio. Entonces, ¿qué explica la columna
heap/sort? Usen las dos tablas, y digan por qué en la operación de bajar de heapsort las lecturas no van en secuencia. - ¿Qué pueden afirmar con estas dos tablas, y qué no? ¿Hay algún n donde heapsort falle menos que mergesort?
Parte F — Escribir código
Pregunta 11 — Dos operaciones
Tiempo estimado: 20 min
a) Dado un árbol binario de búsqueda sin claves repetidas, escriban esta función recursiva, que cuente las
claves k con low <= k y k < high, sin visitar los subárboles que no pueden tener ninguna. Digan su costo en función de la
altura h y de la cantidad de claves contadas c.
struct Node {
int key;
Node* left;
Node* right;
};
int count_range(const Node* node, int low, int high);b) Esta cola usa un buffer circular. Escriban grow, que duplica la capacidad y conserva todos los elementos
de la cola y su orden. No usen std::vector. Digan qué costo amortizado tiene enqueue y qué se rompería si grow copiara
cada casilla a la misma posición del bloque nuevo.
// Invariantes: 0 <= size_ <= capacity_, 0 <= front_ < capacity_, capacity_ >= 1.
// El elemento i de la cola está en slots_[(front_ + i) % capacity_].
class RingQueue {
public:
explicit RingQueue(std::size_t capacity) : slots_(new int[capacity]), capacity_(capacity) {}
~RingQueue() { delete[] slots_; }
RingQueue(const RingQueue&) = delete;
RingQueue& operator=(const RingQueue&) = delete;
void enqueue(int value) {
if (size_ == capacity_) {
grow();
}
slots_[(front_ + size_) % capacity_] = value;
size_++;
}
int dequeue() {
assert(size_ > 0);
int value = slots_[front_];
front_ = (front_ + 1) % capacity_;
size_--;
return value;
}
private:
void grow();
int* slots_;
std::size_t capacity_;
std::size_t front_ = 0;
std::size_t size_ = 0;
};Lista de comprobación: resultados de aprendizaje
Al corregir su práctica, marquen lo que ya pueden hacer. Cada línea es un resultado de aprendizaje del programa del curso, con las semanas donde se enseña y las preguntas de este final que lo ejercitan. Si algo queda sin marcar, vuelvan a esas semanas antes del final.
- Puedo escribir clases y templates en C++ que administran su memoria con RAII, sin fugas ni accesos inválidos. Semanas 1, 2, 4 y 5. Preguntas 9 a) y 11 b).
- Puedo distinguir un tipo abstracto de sus implementaciones, y elegir la adecuada según las operaciones que el problema necesita. Semanas 2, 4, 7, 10, 13 y 15. Pregunta 8.
- Puedo predecir el costo de un programa con análisis asintótico y costo amortizado, y contrastarlo con mediciones. Semanas 3, 4, 9 y 13. Preguntas 7 y 10.
- Puedo implementar y usar arreglos dinámicos, listas enlazadas, pilas, colas y deques. Semanas 2, 4 y 5. Preguntas 7 a), 9 b) y 11 b).
- Puedo implementar y comparar tablas hash con encadenamiento y con direccionamiento abierto. Semanas 7 y 9. Preguntas 1 y 10 a).
- Puedo implementar árboles binarios de búsqueda y mantenerlos balanceados con AVL y con árboles rojinegros. Semanas 10, 11 y 12. Preguntas 2, 3, 9 d) y 11 a).
- Puedo implementar heaps y colas de prioridad, y representar y recorrer grafos. Semanas 13, 14 y 15. Preguntas 4, 5, 6 y 9 c).
- Puedo declarar los invariantes de una estructura, comprobarlos en el código y probarla contra una implementación de referencia. Semanas 2, 10, 11, 12 y 14. Preguntas 9 c), 9 d) y 11 b).
- Puedo explicar cómo las bibliotecas y los lenguajes actuales aplican estas ideas, y por qué. Semanas 6, 9, 12 y 13. Preguntas 7 b) (fragmento D), 8 y 10 b).