WorksheetsEDB: Estructuras No Lineales
Total questions: 20
Worksheet time: 12mins
¿Cuál es la definición correcta de recursividad?
Estructura que repite un bloque con un contador.
Técnica en la que una función se llama a sí misma hasta alcanzar un caso base.
Uso de varias funciones en paralelo.
Ejecución de un bucle while o for.
En una función recursiva bien construida, ¿Qué garantiza la terminación?
El caso base y el progreso hacia él en cada llamada.
Un contador global inicializado a cero.
Una variable estática que limite las llamadas.
Imprimir el resultado en cada llamada recursiva.
Selecciona tipos válidos de recursión:
Recursión directa (la función se llama a sí misma)
Recursión indirecta (dos o más funciones se llaman mutuamente)
Recursión de cola (tail recursion)
Recursión buffer.
Recursión vs. iteración — marca las correctas:
La recursión usa la pila de llamadas del sistema.
La iteración siempre consume más memoria que la recursión.
Algunos problemas (árboles, backtracking) se expresan con mayor claridad recursiva.
La recursión puede tener sobrecosto y riesgo de stack overflow.
¿Cuál es una ventaja típica de la recursión?
Siempre es más eficiente que la iteración.
Facilita divide-y-vencerás y recorridos de estructuras jerárquicas.
Evita por completo la pila de llamadas.
No requiere caso base.
¿Cuál es una desventaja típica de la recursión?
Disminuye el uso de memoria frente a cualquier alternativa.
Puede implicar sobrecosto en tiempo/espacio y riesgo de desbordar la pila.
No permite resolver problemas sobre árboles.
Impide la memoización.
Selecciona problemas que se modelan bien con recursión:
Torres de Hanói.
Recorrido en profundidad de un árbol.
Cálculo académico de Fibonacci.
Ordenamiento por burbuja (típico).
La “recursión de cola” (tail recursion) se caracteriza por:
La llamada recursiva es la última operación de la función.
No requiere caso base.
Usa dos llamadas recursivas en cada paso.
Siempre es más lenta que la recursión no terminal.
¿Qué describe mejor a un árbol (en Estructuras de Datos)?
Grafo con ciclos.
Conjunto de nodos conectados de forma jerárquica sin ciclos, con un nodo raíz.
Lista lineal con punteros a anterior y siguiente.
Pila con dos topos.
Árbol general vs árbol binario (marca las correctas):
En el árbol general, un nodo puede tener cualquier número de hijos.
En el árbol binario, cada nodo tiene a lo sumo dos hijos.
En el árbol binario, todo nodo debe tener exactamente dos hijos.
En el árbol general no existe el concepto de raíz.
Un árbol binario “completo” se define como:
Todos los niveles están llenos excepto quizá el último, que se llena de izquierda a derecha.
Todos los nodos internos tienen exactamente dos hijos.
Tiene el mismo número de hojas que de nodos internos.
No admite nodos hoja en el último nivel.
En un BST (árbol binario de búsqueda), ¿qué recorrido produce claves en orden ascendente?
Preorden
Inorden
Postorden
Por niveles (BFS)
¿Para qué se usa principalmente un heap binario?
Implementar colas de prioridad
Ordenar por burbuja
Recorrer grafos en anchura
Buscar por clave exacta en O(1)
Aplicaciones típicas de árboles (marca las correctas):
Sistemas de archivos (directorios).
Índices B/B+-tree en bases de datos.
Tablas hash cerradas.
Árboles de decisión en IA.
¿Qué es un grafo?
Estructura lineal ordenada por índices.
Conjunto de vértices y aristas que relacionan pares de vértices.
Árbol binario balanceado.
Una cola circular con prioridades.
Clasificación de grafos (marca las correctas):
Dirigido / no dirigido.
Ponderado / no ponderado.
Simple / multigrafo.
Árbol binario / arreglo.
En un grafo disperso (pocas aristas), ¿qué representación suele usar menos memoria?
Matriz de adyacencia
Lista de adyacencia
Matriz de incidencia
Ninguna, ambas ocupan lo mismo
¿Cuál es la regla básica de un árbol binario de búsqueda (BST)?
Todos los nodos tienen exactamente dos hijos.
Los valores menores que un nodo van en su subárbol izquierdo y los mayores en el derecho.
Todos los nodos de la izquierda son hojas.
Las claves se almacenan en orden aleatorio.
Recorridos en grafos (marca las correctas):
BFS usa una cola.
DFS usa una pila (o recursión).
En grafos no ponderados, BFS halla caminos mínimos en número de aristas.
DFS siempre encuentra el camino más corto.
La longitud de un camino en un grafo se define como:
El número de aristas que lo componen.
El número de vértices visitados.
El grado promedio de los vértices visitados.
La suma de pesos dividida entre V.
