Cuestionario: Estructuras de datos y algoritmos
¿Puedes hacer BS en un árbol binario?
¡Bienvenido a mi quiz de Estructuras de Datos y Algoritmos!
Este quiz evaluará tu dominio de las estructuras de datos (pilas, listas, árboles, etc.), los algoritmos y la complejidad temporal.
20 preguntas… ¡Comencemos!
¿Qué estructura de datos es la más adecuada para un patrón de acceso LIFO (Last In, First Out)?
Las pilas son las más adecuadas para patrones de acceso LIFO. Las colas son las más adecuadas para patrones de acceso FIFO (First In, First Out).
En LIFO, el último elemento que entra debe ser el primero en salir.
¿Cuál es la complejidad temporal de un algoritmo que siempre tarda la misma cantidad de tiempo en ejecutarse, sin importar el tamaño de la entrada?
O(1) representa complejidad temporal constante. Significa que el algoritmo siempre tarda la misma cantidad de tiempo en ejecutarse, sin importar el tamaño de la entrada.
Piensa en cómo crece el trabajo al aumentar la entrada, no en cuántos milisegundos dura una ejecución concreta.
Si una lista simplemente enlazada no almacena su longitud, ¿cuál es la complejidad temporal de calcularla recorriendo los nodos?
Para calcular la longitud de una lista enlazada simple, debes recorrer cada nodo desde la cabeza hasta el final, lo que resulta en una complejidad temporal O(n).
Sin un contador guardado, ¿puedes conocer la longitud sin visitar todos los nodos?
¿Cuál es la complejidad temporal promedio para buscar un elemento en un Árbol Binario de Búsqueda balanceado?
En un BST balanceado, la complejidad temporal promedio para la búsqueda es O(log n) porque cada nivel reduce a la mitad el espacio de búsqueda.
En un árbol equilibrado, cada decisión descarta aproximadamente la mitad del espacio de búsqueda.
¿Cuál es la complejidad temporal del algoritmo Merge Sort en el peor caso?
Merge Sort siempre opera con una complejidad de peor caso de O(n log n) ya que divide repetidamente el arreglo a la mitad y fusiona los subarreglos ordenados.
Cuenta los niveles de división y el trabajo total de fusionar elementos en cada nivel.
¿Qué estructura de datos se usa típicamente para implementar la búsqueda en anchura (BFS)?
BFS utiliza una Cola para explorar los nodos nivel por nivel, procesando los nodos de forma amplia (por “fila”).
Para recorrer por niveles, los primeros vecinos descubiertos deben procesarse antes que los siguientes.
¿Qué recorrido detecta ciclos en un grafo dirigido manteniendo una pila de recursión o marcas de nodos activos?
La búsqueda en profundidad (DFS) se usa típicamente para detectar ciclos en un grafo manteniendo una pila de recursión que rastrea los nodos visitados.
La pista es la pila de llamadas: volver a un nodo que sigue activo revela un ciclo.
¿Cuál es la complejidad temporal de Heap Sort en el peor caso?
Heap Sort mantiene una complejidad temporal de peor caso de O(n log n), ya que construye un heap y extrae repetidamente el elemento máximo.
Además de construir el montículo, hay que extraer repetidamente elementos y restaurar su propiedad.
¿Cuál es la complejidad de tiempo promedio para acceder a un elemento en una tabla hash?
Las tablas hash tienen una complejidad de tiempo promedio de O(1) para acceder a los elementos, asumiendo una buena función hash que minimice colisiones.
Una buena función hash distribuye las claves; piensa en el coste promedio, no en el peor caso de colisiones.
¿Qué conjunto contiene las operaciones típicas que se realizan en una pila?
Las operaciones principales de una pila son Push (añadir elemento), Pop (eliminar elemento) y Peek (ver el elemento superior sin eliminarlo).
Una pila añade, retira e inspecciona elementos por el mismo extremo.
¿Qué algoritmo encuentra caminos mínimos desde un origen eligiendo vorazmente el vértice no visitado con menor distancia, si las aristas tienen pesos no negativos?
El algoritmo de Dijkstra se usa frecuentemente para encontrar la ruta más corta en grafos con pesos de arista no negativos. Emplea una cola de prioridad para determinar la distancia mínima de manera eficiente.
Fíjate en la elección voraz del vértice con menor distancia pendiente y en la restricción de pesos no negativos.
¿Qué conjunto contiene ejemplos de estructuras de datos de árbol binario de búsqueda autobalanceado?
Los árboles AVL y los árboles Rojo‑Negro son tipos de árboles autobalanceados, que garantizan que el árbol permanezca equilibrado después de cada inserción o eliminación.
Busca árboles que ajustan su estructura tras insertar o eliminar, no solo una estructura con una raíz mínima.
¿Qué debe definirse en una función recursiva para evitar la recursión infinita?
Un caso base es necesario en una función recursiva para detener las llamadas recursivas cuando se cumple una condición específica, evitando la recursión infinita.
La recursión necesita una condición que devuelva un resultado sin volver a llamarse.
¿Cuáles son las dos operaciones principales de una cola?
Las dos operaciones principales en una cola son Enqueue (agregar un elemento al final) y Dequeue (eliminar un elemento del frente).
En una cola, se añade por un extremo y se retira por el otro.
¿Cuáles son las condiciones para realizar un ordenamiento topológico en un grafo?
El ordenamiento topológico se puede realizar en un grafo si es dirigido y acíclico (DAG). Este tipo de ordenación es útil en problemas de planificación de tareas.
Si hay un ciclo de dependencias, ningún elemento de ese ciclo puede colocarse antes de todos sus requisitos.
¿Cuál es la complejidad temporal de una implementación recursiva ingenua de la serie de Fibonacci?
La implementación recursiva ingenua de la serie de Fibonacci tiene una complejidad temporal de O(2^n) debido a los extensos cálculos repetidos para cada número de Fibonacci.
La versión ingenua vuelve a calcular los mismos términos en muchas ramas recursivas.
¿Qué estructura de datos se usa comúnmente para implementar una cola de prioridad?
Una cola de prioridad se implementa normalmente usando un montículo porque permite extraer de forma eficiente el elemento de mayor o menor prioridad.
¿Qué estructura permite obtener eficientemente el elemento de mayor o menor prioridad?
¿Qué conjunto enumera los órdenes de recorrido en profundidad comunes para un árbol binario?
En orden, preorden y postorden son los tres órdenes de recorrido en profundidad comunes para los árboles binarios, cada uno con un orden diferente de visita a los nodos. El recorrido en anchura también es común, pero pertenece a una categoría de recorrido distinta.
Compara cuándo se visita la raíz respecto de sus subárboles izquierdo y derecho.
¿Cuáles de las siguientes propiedades son verdaderas para un min‑heap?
En un min‑heap, la raíz siempre es el elemento más pequeño y la altura del árbol es O(log n), lo que hace que la inserción y la extracción sean eficientes.
En un montículo mínimo binario, cada padre es menor o igual que sus hijos y la forma del árbol es completa.
¿Es estable Bubble Sort cuando solo intercambia elementos adyacentes si el de la izquierda es estrictamente mayor que el de la derecha?
Con una comparación estricta, Bubble Sort no intercambia elementos iguales y preserva su orden relativo, por lo que es estable. Una variante que también intercambie valores iguales puede perder esa propiedad.
La comparación es estricta: dos elementos iguales no se intercambian entre sí.