Saltar a contenido

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.