Ejercicios · Estructuras C25¶
El contenedor set y los montículos: las operaciones del set y sus bordes,
cuándo conviene frente a otros contenedores, y el montículo de máximos guardado
en un arreglo, con insertar subiendo, extraer bajando y lo que cuesta cada
operación. Cada enlace abre una actividad que se trabaja directo en el
navegador, en el mismo orden de los temas de la
sesión.
Los árboles, los arreglos y los programas no son los de la sesión: mismo tema,
ronda nueva.
Repaso: el árbol binario de búsqueda¶
forma¶
Las mismas claves insertadas en cuatro órdenes distintos: la altura de cada árbol y lo que cuesta armarlo cuando llegan en orden.
El contenedor set¶
operaciones¶
Los buses que pasan por un peaje: qué imprime un programa que cuenta repetidos
con count, avanza con ++it desde find y borra con erase.
bordes¶
Las salidas de un tren con lower_bound y upper_bound, la salida anterior a
un minuto, cuántas caen en un intervalo y lo que cuesta el lower_bound de
<algorithm> sobre un set.
elegir¶
Cinco situaciones para escoger entre set, map, unordered_map y un
vector ordenado una sola vez, con lo que falla en cada alternativa.
compuestas¶
UVa 10391 con un set<string>: qué palabras del diccionario salen, cuántos
cortes se prueban en cada una y en qué orden queda la salida.
Montículos¶
urgente¶
Una sala de urgencias que atiende por prioridad: qué se atiende, qué queda, cuántas comparaciones paga el arreglo sin orden y cuántas casillas corre el ordenado.
completo¶
Cuáles de cuatro árboles son completos, el padre y los hijos de una casilla con índices desde 0, y el paso del árbol al arreglo y del arreglo al árbol.
cuales¶
Cinco arreglos para decidir si son montículos de máximos, entre ellos uno con una clave menor que la raíz que igual rompe el orden, uno con claves iguales y un montículo de mínimos.
insertar¶
Tres claves que llegan a un montículo de once: el árbol y el arreglo en cada intercambio, la traza en una tabla y una clave igual a su padre.
extraer¶
Dos extracciones paso a paso, el empate entre dos hijos iguales y lo que deja
un bajar que solo mira el hijo izquierdo.
costos¶
La altura para 12, 200 y 70 000 claves, cuántos intercambios hacen insertar y extraer en un árbol lleno, y por qué el montículo cabe en un arreglo.
errores¶
Tres versiones con una línea cambiada: bajar con el primer hijo mayor, subir
con el padre en i / 2 y extraer subiendo hijos, con lo que deja cada una.