🌳 Estructuras de datos

1. ¿Qué política de acceso caracteriza el comportamiento de una pila (stack) como estructura de datos?

1. LIFO: el último elemento insertado es el primero en salir
2. FIFO: el primer elemento insertado es el primero en salir
3. Acceso aleatorio por índice, sin relación con el orden de inserción
4. Acceso ordenado según la prioridad numérica de cada elemento

La pila sigue la política LIFO (último en entrar, primero en salir); la política FIFO corresponde a la cola, no a la pila. (CLRS, 3ª ed., cap. 10 (Stacks and queues))

2. ¿Qué política de acceso caracteriza el comportamiento de una cola (queue) como estructura de datos?

1. LIFO: el último elemento insertado es el primero en salir
2. Acceso ordenado según la prioridad de cada elemento
3. FIFO: el primer elemento insertado es el primero en salir
4. Acceso directo mediante una clave calculada por una función hash

La cola sigue la política FIFO (primero en entrar, primero en salir); LIFO corresponde a la pila. (CLRS, 3ª ed., cap. 10 (Stacks and queues))

3. Un desarrollador implementa la función 'deshacer' (undo) de un editor de texto, donde la acción más reciente debe ser la primera en revertirse. ¿Qué estructura de datos es la más adecuada y cuál es el costo de sus operaciones básicas de inserción y eliminación?

1. Cola; las operaciones enqueue y dequeue se ejecutan en O(1)
2. Pila; las operaciones push y pop se ejecutan en O(1)
3. Lista enlazada simple; la inserción al inicio es O(1) y la búsqueda es O(n)
4. Árbol rojinegro; la inserción y la búsqueda se ejecutan en O(log n)

El comportamiento 'último en entrar, primero en salir' corresponde a una pila, cuyas operaciones push/pop son O(1); la cola aplicaría el orden inverso (FIFO). (CLRS, 3ª ed., cap. 10 (Stacks and queues))

4. Un sistema de impresión debe procesar los documentos exactamente en el mismo orden en que fueron enviados por los usuarios, sin alterar la secuencia de llegada. ¿Qué estructura de datos y política de acceso implementan correctamente este requisito?

1. Pila; política LIFO
2. Montículo mínimo; política de menor valor primero
3. Cola; política FIFO
4. Árbol binario de búsqueda; política de orden por clave

Procesar en el mismo orden de llegada corresponde a la política FIFO propia de la cola; la pila invertiría el orden de atención. (CLRS, 3ª ed., cap. 10 (Stacks and queues))

5. ¿Cuál es el costo temporal de las operaciones push y pop sobre una pila implementada con un arreglo o con una lista enlazada?

1. O(1) para ambas operaciones
2. O(n) para ambas operaciones, pues requieren recorrer la estructura completa
3. O(log n) para push y O(1) para pop
4. O(1) para push y O(n) para pop, pues se debe localizar el último elemento

Push y pop operan siempre sobre el tope de la pila, sin recorrer el resto de la estructura, por lo que su costo es constante. (CLRS, 3ª ed., cap. 10 (Stacks and queues))

6. ¿Cuál de las siguientes operaciones sobre una pila implementada con una lista enlazada NO tiene costo O(1)?

1. Insertar un nuevo elemento en el tope de la pila (push)
2. Buscar un elemento arbitrario dentro de la pila
3. Eliminar el elemento que se encuentra en el tope (pop)
4. Consultar el elemento del tope sin eliminarlo (peek)

Push, pop y peek actúan solo sobre el tope en tiempo constante; buscar un elemento arbitrario exige recorrer la pila en el peor caso, es decir O(n). (CLRS, 3ª ed., cap. 10 (Stacks and queues))

7. En una lista enlazada simple, ¿cuál es el costo de insertar un nuevo elemento al inicio de la lista?

1. O(n)
2. O(log n)
3. O(1)
4. O(n log n)

Insertar al inicio solo requiere actualizar el apuntador de cabeza, sin recorrer la lista, por lo que el costo es constante. (CLRS, 3ª ed., cap. 10 (Linked lists))

8. Una aplicación guarda su historial de eventos en una lista enlazada simple no ordenada. Cuando el sistema necesita verificar si un evento con una clave específica ya fue registrado, ¿cuál es el costo, en el peor caso, de dicha verificación?

1. O(1), porque el apuntador de cabeza permite acceso directo a cualquier elemento
2. O(n), porque en el peor caso debe recorrerse toda la lista
3. O(n log n), porque la lista debe ordenarse antes de realizar la búsqueda
4. O(log n), porque la búsqueda se realiza mediante bisección sobre la lista

Al no estar ordenada, la única forma de verificar la presencia de una clave es recorrer secuencialmente la lista hasta encontrarla o llegar al final, es decir O(n). (CLRS, 3ª ed., cap. 10 (Linked lists))

9. ¿Cuál es el costo de insertar un nuevo elemento en un montículo (heap) binario con n elementos?

1. O(log n)
2. O(n)
3. O(1)
4. O(n log n)

Insertar requiere colocar el elemento en la última posición y luego 'flotarlo' hasta restaurar la propiedad de montículo, un proceso proporcional a la altura del árbol, O(log n). (CLRS, 3ª ed., cap. 6 y 6.5 (Priority queues))

10. ¿Cuál es el costo de consultar, sin eliminarlo, el elemento de mayor prioridad almacenado en un montículo binario?

1. O(log n)
2. O(n)
3. O(n log n)
4. O(1)

El elemento de mayor prioridad siempre se encuentra en la raíz del montículo, por lo que consultarlo (sin eliminarlo) es de costo constante. (CLRS, 3ª ed., cap. 6.5 (Priority queues))

11. ¿Cuál es el costo de extraer el elemento de mayor prioridad (extract-max o extract-min) de un montículo binario con n elementos, considerando que después de la extracción debe restaurarse la propiedad de montículo?

1. O(n), porque se debe recorrer todo el arreglo para localizar el reemplazo de la raíz
2. O(1), porque solo se retira el nodo raíz sin reorganizar el resto del árbol
3. O(log n), porque el nuevo elemento raíz debe 'hundirse' hasta restaurar la propiedad de montículo
4. O(n log n), porque el montículo completo se reconstruye desde cero

Tras mover el último elemento a la raíz, este debe hundirse por la ruta adecuada hasta restaurar la propiedad de montículo, en tiempo proporcional a la altura, O(log n). (CLRS, 3ª ed., cap. 6 (Heapsort) y 6.5 (Priority queues))

12. ¿Cuál es el costo de construir un montículo binario a partir de un arreglo desordenado de n elementos mediante el procedimiento BUILD-HEAP, que aplica el proceso de restauración de la propiedad de montículo de abajo hacia arriba?

1. O(n log n), porque el proceso de restauración se aplica una vez a cada uno de los n elementos
2. O(n), porque la suma de los costos de restauración en todos los niveles converge a un valor lineal
3. O(log n), porque únicamente la raíz del arreglo requiere reordenarse
4. O(n²), porque cada elemento se compara con todos los demás elementos del arreglo

Aunque una cota ingenua sugiere O(n log n), el análisis muestra que la mayoría de los nodos están cerca de las hojas y requieren pocos intercambios, por lo que el costo total de BUILD-HEAP es O(n). (CLRS, 3ª ed., cap. 6 (Heapsort), análisis de BUILD-HEAP)

13. Un sistema de gestión hospitalaria debe atender primero al paciente cuya condición sea más crítica, sin importar el orden en que haya llegado. ¿Qué estructura de datos resulta más adecuada para implementar esta política de atención?

1. Cola de prioridad implementada mediante un montículo
2. Cola simple con política FIFO
3. Pila con política LIFO
4. Lista enlazada ordenada por orden de llegada

Cuando el criterio de atención es la prioridad (gravedad) y no el orden de llegada, la estructura adecuada es una cola de prioridad basada en un montículo. (CLRS, 3ª ed., cap. 6.5 (Priority queues))

14. Un programador necesita una estructura que permita extraer repetidamente el elemento mínimo en tiempo logarítmico y que se pueda construir a partir de un arreglo desordenado con menor costo, sin requerir que todos los elementos permanezcan totalmente ordenados en todo momento. ¿Qué estructura satisface mejor este requisito?

1. Árbol binario de búsqueda balanceado, pues mantiene todas las claves en orden estricto
2. Montículo mínimo, pues solo garantiza el orden parcial necesario para la extracción del mínimo
3. Lista enlazada ordenada, pues facilita la extracción del primer elemento
4. Arreglo ordenado mediante inserción, pues permite acceso directo al mínimo

El montículo mínimo mantiene solo la propiedad parcial de orden (padre menor o igual que hijos) y se construye en O(n) mediante BUILD-HEAP, mientras que un BST balanceado o estructuras totalmente ordenadas imponen un costo mayor. (CLRS, 3ª ed., cap. 6 (Heapsort) y cap. 13 (Red-black trees))

15. De las siguientes operaciones sobre un montículo binario, ¿cuál NO se ejecuta en tiempo O(log n)?

1. Insertar un nuevo elemento en el montículo
2. Extraer el elemento de mayor prioridad del montículo
3. Aumentar la prioridad de un elemento interno y reordenar el montículo
4. Consultar el elemento de mayor prioridad sin eliminarlo

Consultar la raíz del montículo es de costo constante O(1); insertar, extraer y reordenar tras un cambio de prioridad requieren recorrer la altura del árbol, O(log n). (CLRS, 3ª ed., cap. 6.5 (Priority queues))

16. ¿Qué propiedad debe cumplir un montículo máximo (max-heap) respecto a un nodo padre y sus hijos?

1. La clave del nodo padre es igual al promedio de las claves de sus hijos
2. La clave del nodo padre es mayor o igual que las claves de sus hijos
3. La clave del nodo padre no guarda relación de orden con sus hijos
4. La clave del nodo padre es menor o igual que las claves de sus hijos

En un montículo máximo, cada nodo padre debe tener una clave mayor o igual que la de cada uno de sus hijos, lo que garantiza que el máximo se ubique siempre en la raíz. (CLRS, 3ª ed., cap. 6 (Heapsort), propiedad de montículo)

17. ¿Cuál es la principal diferencia funcional entre una cola de prioridad implementada con un montículo y una cola simple de tipo FIFO?

1. La cola de prioridad extrae según la prioridad asignada, mientras que la cola FIFO extrae según el orden de llegada
2. La cola de prioridad extrae según el orden de llegada, mientras que la cola FIFO extrae según la prioridad asignada
3. Ambas extraen el elemento insertado más recientemente
4. Ambas requieren tiempo O(n) para insertar un nuevo elemento

La cola de prioridad selecciona el elemento con mayor (o menor) prioridad sin importar cuándo llegó, mientras que la cola FIFO respeta estrictamente el orden de llegada. (CLRS, 3ª ed., cap. 6.5 (Priority queues) y cap. 10 (Stacks and queues))

18. ¿En qué orden visita los nodos el recorrido inorden (in-order) de un árbol binario?

1. Raíz, subárbol izquierdo, subárbol derecho
2. Subárbol izquierdo, subárbol derecho, raíz
3. Subárbol izquierdo, raíz, subárbol derecho
4. Raíz, subárbol derecho, subárbol izquierdo

El recorrido inorden visita primero el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho; sobre un BST esto produce las claves en orden ascendente. (CLRS, 3ª ed., cap. 12, procedimiento INORDER-TREE-WALK)

19. ¿En qué orden visita los nodos el recorrido preorden (pre-order) de un árbol binario?

1. Subárbol izquierdo, raíz, subárbol derecho
2. Raíz, subárbol izquierdo, subárbol derecho
3. Subárbol izquierdo, subárbol derecho, raíz
4. Subárbol derecho, raíz, subárbol izquierdo

El recorrido preorden visita primero la raíz, después el subárbol izquierdo y por último el subárbol derecho. (CLRS, 3ª ed., cap. 12 (Binary search trees))

20. ¿En qué orden visita los nodos el recorrido postorden (post-order) de un árbol binario?

1. Raíz, subárbol izquierdo, subárbol derecho
2. Subárbol izquierdo, subárbol derecho, raíz
3. Raíz, subárbol derecho, subárbol izquierdo
4. Subárbol izquierdo, raíz, subárbol derecho

El recorrido postorden visita primero ambos subárboles y, al final, la raíz. (CLRS, 3ª ed., cap. 12 (Binary search trees))

21. Un analista de datos requiere obtener el listado de claves almacenadas en un árbol binario de búsqueda (BST) en orden ascendente, sin necesidad de ordenarlas después de extraerlas. ¿Qué recorrido debe aplicar sobre el árbol para lograrlo directamente?

1. Recorrido inorden
2. Recorrido preorden
3. Recorrido postorden
4. Recorrido por niveles (BFS)

En un BST, el recorrido inorden visita las claves en orden ascendente de manera natural, sin requerir un paso adicional de ordenamiento. (CLRS, 3ª ed., cap. 12, procedimiento INORDER-TREE-WALK)

22. Un ingeniero de software necesita explorar un grafo nivel por nivel, de manera que se visiten primero todos los vértices más cercanos al origen antes que los más lejanos. ¿Qué estructura de datos auxiliar debe emplear para lograr este comportamiento?

1. Una pila LIFO, como en el algoritmo DFS
2. Un montículo de prioridad ordenado por clave
3. Un árbol rojinegro auxiliar balanceado
4. Una cola FIFO, como en el algoritmo BFS

El recorrido por niveles característico de BFS se implementa con una cola FIFO, que garantiza procesar los vértices en el orden en que se descubren por distancia creciente. (CLRS, 3ª ed., cap. 22 (Breadth-first search))

23. Si un grafo con V vértices se representa mediante una MATRIZ de adyacencia en lugar de listas de adyacencia, ¿cuál es el costo temporal de un recorrido BFS o DFS completo sobre ese grafo?

1. O(E), porque solo se examinan las aristas existentes sin importar la representación
2. O(V + E), igual que con listas de adyacencia, porque la representación no afecta el costo del recorrido
3. O(V²), porque para cada vértice debe recorrerse toda su fila de la matriz para hallar a sus vecinos
4. O(V log V), porque la matriz permite ordenar los vértices antes de recorrerlos

Con matriz de adyacencia, determinar los vecinos de un vértice exige recorrer una fila completa de tamaño V, por lo que el recorrido completo cuesta O(V²), a diferencia del O(V+E) que se logra con listas de adyacencia. (CLRS, 3ª ed., cap. 22 (representación de grafos y recorridos))

24. Un ingeniero debe encontrar la ruta con el menor número de aristas entre dos vértices de un grafo no ponderado. ¿Qué algoritmo de recorrido debe utilizar para garantizar dicha propiedad?

1. DFS, porque explora primero la rama más profunda del grafo
2. Recorrido postorden, porque visita los hijos antes que la raíz
3. Recorrido inorden, porque produce un orden ascendente de claves
4. BFS, porque visita los vértices por niveles de distancia creciente desde el origen

BFS explora el grafo por niveles de distancia, por lo que la primera vez que alcanza un vértice lo hace mediante el camino con el menor número de aristas; DFS no garantiza esta propiedad. (CLRS, 3ª ed., cap. 22 (Breadth-first search, camino más corto no ponderado))

25. Durante la ejecución de DFS sobre un grafo dirigido representado con listas de adyacencia, el algoritmo alcanza un vértice que ya fue visitado y que todavía permanece activo en la pila de llamadas recursivas (es decir, es antecesor del vértice actual en el árbol de recorrido). ¿Qué tipo de arista se identifica en este caso?

1. Arista de retroceso (back edge)
2. Arista de árbol (tree edge)
3. Arista de avance (forward edge)
4. Arista cruzada (cross edge)

Una arista que conecta un vértice con un antecesor todavía activo en la recursión se clasifica como arista de retroceso; las de árbol, avance y cruce corresponden a otras relaciones entre vértices descubiertos. (CLRS, 3ª ed., cap. 22 (Depth-first search, clasificación de aristas))

26. Un grafo NO dirigido tiene 6 vértices y 9 aristas, y se representa mediante listas de adyacencia. ¿Cuál es la suma total del número de elementos (vecinos) que aparecen a lo largo de las listas de adyacencia de todos los vértices?

1. 9, porque la suma equivale directamente al número de aristas del grafo
2. 24, porque se duplican las aristas y además se suman los 6 vértices
3. 15, porque se suman los vértices y las aristas del grafo (6 + 9)
4. 18, porque la suma de longitudes de las listas de adyacencia es el doble de las aristas

En un grafo no dirigido, cada arista aparece en las listas de adyacencia de sus dos extremos, por lo que la suma total de longitudes es 2|E| = 2 × 9 = 18. (CLRS, 3ª ed., cap. 22 (representación mediante listas de adyacencia))

27. En una lista enlazada simple, cada nodo mantiene un único apuntador que hace referencia exclusivamente a...

1. el nodo anterior dentro de la lista
2. el nodo siguiente dentro de la lista
3. la cabecera de la lista completa
4. ambos nodos vecinos, el anterior y el siguiente

Por definición, en una lista simplemente enlazada cada nodo solo almacena la dirección del nodo siguiente; acceder al anterior exigiría un apuntador adicional, propio de la lista doble. (Weiss, 'Data Structures and Algorithm Analysis', cap. 3 (Lists, Stacks, and Queues); CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10)

28. En una lista enlazada simple no ordenada, insertar un nuevo nodo justo después de la cabecera (es decir, al inicio de la lista) tiene un costo de tiempo de...

1. O(1)
2. O(n)
3. O(log n)
4. O(n²)

Insertar al inicio solo exige reasignar dos apuntadores, sin importar el tamaño de la lista, por lo que el costo es constante. (CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10 (Linked lists))

29. ¿Cuál es el costo, en el peor de los casos, de buscar un valor específico dentro de una lista enlazada simple con n nodos?

1. O(1)
2. O(log n)
3. O(n log n)
4. O(n)

Sin apuntadores adicionales ni orden que permita saltos, la búsqueda debe recorrer, en el peor caso, los n nodos uno por uno. (CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10 (Linked lists))

30. Un desarrollador cuenta únicamente con un apuntador al nodo que desea eliminar de una lista SIMPLEMENTE enlazada; no tiene el apuntador al nodo anterior ni a la cabecera. Si solo puede reasignar apuntadores para desenlazar ese nodo (sin copiar datos de otro nodo), ¿cuál es la razón por la que no logra completar la eliminación en tiempo constante?

1. El apuntador del nodo actual hacia el siguiente nodo no puede reasignarse sin conocer primero la cabecera de la lista.
2. Toda eliminación en una lista enlazada obliga a recorrer la lista completa para reacomodar los índices de los nodos restantes.
3. El apuntador del nodo predecesor, que debe reasignarse para saltar al nodo eliminado, no es accesible desde el nodo actual.
4. El nodo actual carece de un apuntador propio y depende del recolector de basura para liberarse.

En una lista simple, únicamente el nodo anterior conoce la referencia que debe modificarse para saltar al nodo eliminado; sin ese apuntador hay que recorrer la lista desde la cabecera, lo que hace el costo lineal, no constante. (CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10 (limitación estructural de la lista simple frente a la doble))

31. En una lista doblemente enlazada, cada nodo mantiene, además del apuntador al nodo siguiente, un apuntador adicional que hace referencia a...

1. la cabecera que encabeza toda la lista
2. el nodo inmediatamente anterior dentro de la lista
3. un nodo cualquiera, elegido de forma aleatoria
4. el último nodo situado al final de la lista

La característica que define a la lista doble es el segundo apuntador hacia el nodo previo, lo que habilita el recorrido en ambos sentidos. (Weiss, 'Data Structures and Algorithm Analysis', cap. 3; CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10)

32. ¿Cuál es la ventaja principal de una lista doblemente enlazada frente a una lista simplemente enlazada al recorrer o modificar sus elementos?

1. Reduce el costo de búsqueda de un elemento a O(log n) gracias al apuntador adicional.
2. Elimina por completo la necesidad de mantener un apuntador a la cabecera de la lista.
3. Garantiza que la inserción sea O(1) en cualquier posición, aunque no se conozca un apuntador cercano.
4. Permite recorrer la lista en ambos sentidos y eliminar un nodo dado su apuntador sin buscar al predecesor.

El apuntador al nodo anterior permite recorrer en reversa y acceder al predecesor directamente; la búsqueda sigue siendo O(n) en ambas variantes, por lo que no se reduce a O(log n). (Weiss, 'Data Structures and Algorithm Analysis', cap. 3; CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10)

33. En una lista circular simplemente enlazada, el apuntador 'siguiente' del último nodo hace referencia a...

1. el primer nodo de la lista, en lugar de un valor nulo
2. un valor nulo, igual que en una lista simple no circular
3. el nodo situado justo antes de la cabecera de la lista
4. ningún nodo en particular, pues queda indefinido

Lo que distingue a la lista circular es que el último nodo cierra el ciclo apuntando de vuelta al primero, sin que exista ningún apuntador nulo dentro de la estructura. (Weiss, 'Data Structures and Algorithm Analysis', cap. 3 (Circular linked lists))

34. En una lista circular doblemente enlazada se mantiene un único apuntador externo que referencia al nodo 'cola' (tail). Gracias a esa única referencia, ¿qué operaciones pueden realizarse en tiempo constante?

1. Insertar únicamente al final de la lista, sin poder eliminar en ningún extremo.
2. Acceder al nodo cabecera, sin permitir ninguna operación sobre el nodo final.
3. Insertar y eliminar nodos tanto al inicio como al final de la lista.
4. Recorrer la lista en sentido inverso, pero sin poder insertar en ningún extremo.

Como la lista es circular, tail->next apunta a la cabeza y tail->prev al penúltimo nodo, de modo que un solo apuntador basta para insertar o eliminar en O(1) tanto al inicio como al final. (CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10 (ejercicios sobre listas circulares); Weiss cap. 3)

35. ¿Cuál de las siguientes afirmaciones sobre una lista circular simplemente enlazada NO es correcta?

1. La búsqueda de un elemento específico tiene un costo de O(log n), menor que en una lista simple no circular.
2. Un recorrido iniciado en cualquier nodo puede regresar al punto de partida sin encontrar jamás un apuntador nulo.
3. La lista carece de un nodo final marcado con apuntador nulo, a diferencia de una lista simple no circular.
4. Insertar un nuevo nodo inmediatamente después de un apuntador dado tiene un costo de O(1), igual que en una lista simple.

La circularidad cambia la forma de recorrer la lista, pero no acelera la búsqueda: esta sigue siendo O(n) en el peor caso, igual que en una lista simple, pues no existe ningún mecanismo de orden o salto. (Weiss, 'Data Structures and Algorithm Analysis', cap. 3; CLRS, 'Introduction to Algorithms', 3ª ed., cap. 10)