Hoja de ejercicios de Estructuras de datos con soluciones

La altura de un árbol se define habitualmente como:

1. AEl número de hojas del árbol
2. BEl número de hijos de la raíz
3. CEl número de aristas del camino más largo desde la raíz hasta una hoja
4. DEl número total de nodos del árbol, contando la raíz y todas las hojas

¿Qué hace la operación peek (o top) en una pila?

1. ADevuelve el elemento de la cima sin eliminarlo
2. BElimina todos los elementos de la pila
3. CDevuelve el elemento del fondo de la pila
4. DElimina el elemento de la cima y lo devuelve

En un árbol, ¿qué es una hoja?

1. AEl nodo con el valor más grande
2. BUn nodo sin hijos
3. CUn nodo sin padre
4. DUn nodo con exactamente un hijo

Un trie (árbol de prefijos) es especialmente eficiente para:

1. ABúsquedas por prefijo, como el autocompletado
2. BOrdenar números
3. CAlmacenar matrices
4. DEncontrar caminos más cortos

En un montículo binario almacenado en un arreglo que empieza en el índice 0, ¿dónde está el padre del nodo del índice i?

1. AEn el índice i − 1
2. BEn el índice ⌊i / 2⌋ + 1
3. CEn el índice ⌊(i − 1) / 2⌋
4. DEn el índice 2i + 1

Tienes una referencia a un nodo situado en medio de una lista. ¿En qué lista puedes eliminarlo en O(1)?

1. AUn arreglo ordenado
2. BUna lista doblemente enlazada
3. CUna lista simplemente enlazada
4. DUn arreglo dinámico

Un arreglo dinámico duplica su tamaño cuando está lleno. ¿Por qué muchas implementaciones solo lo reducen cuando está lleno en una cuarta parte, y no en la mitad?

1. APorque reducirlo a la mitad al llegar a la mitad perdería elementos
2. BPorque el asignador de memoria solo puede liberar memoria en cuartos de bloque
3. CPara evitar redimensionamientos repetidos cuando se alternan push y pop cerca del límite
4. DPara mantener el arreglo ordenado

¿Cómo se puede detectar si una lista simplemente enlazada contiene un ciclo usando O(1) de memoria adicional?

1. AOrdenar la lista y buscar duplicados
2. BMover un puntero de uno en uno y otro de dos en dos y comprobar si se encuentran
3. CContar los nodos hasta que la cuenta supere el campo de longitud de la lista
4. DGuardar cada nodo visitado en un conjunto hash