Hoja de ejercicios de Estructuras de datos con soluciones

En una lista simplemente enlazada, ¿qué contiene el puntero al siguiente del último nodo?

1. ALa dirección del primer nodo
2. BNull (ningún nodo)
3. CLa dirección del nodo anterior
4. DEl número de nodos de la lista

¿Cuántas aristas tiene un árbol con n nodos?

1. An
2. Bn − 1
3. Cn + 1
4. D2n

¿Qué es una deque (cola doblemente terminada)?

1. AUna cola ordenada por prioridad
2. BUna cola que solo permite eliminar por el final
3. CUna estructura que permite insertar y eliminar por ambos extremos
4. DDos colas separadas que comparten un arreglo

Un árbol binario tiene la raíz 1 con hijo izquierdo 2 e hijo derecho 3; el nodo 2 tiene los hijos 4 (izquierdo) y 5 (derecho). ¿Cuál es el recorrido en preorden?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 3 4 5

¿Por qué recorrer un arreglo suele ser en la práctica mucho más rápido que recorrer una lista enlazada de la misma longitud?

1. ALos arreglos usan menos instrucciones para comparar valores
2. BLos elementos del arreglo son contiguos, así que aprovechan bien la caché de la CPU
3. CRecorrer un arreglo es O(1) en total, mientras que recorrer una lista enlazada es O(n)
4. DLas listas enlazadas siempre almacenan los elementos en disco

Una red de carreteras tiene 100,000 cruces, cada uno conectado con unos 4 más. ¿Qué representación es la más adecuada?

1. ALista de adyacencia
2. BUn montículo binario de aristas
3. CMatriz de adyacencia
4. DUn único arreglo ordenado de vértices

¿Qué problema del sondeo lineal reduce principalmente el doble hashing?

1. ALa necesidad de almacenar las claves en la tabla
2. BEl coste O(n) de leer el valor de una clave
3. CLa necesidad de una función hash
4. DEl agrupamiento primario, en el que se forman largas secuencias de posiciones ocupadas

En una tabla hash con direccionamiento abierto, ¿por qué la eliminación suele hacerse con un marcador «lápida» (tombstone)?

1. ALas claves eliminadas deben conservarse para siempre por seguridad, así que las posiciones nunca pueden reutilizarse
2. BLas lápidas aceleran el hashing
3. CVaciar la posición podría romper la secuencia de sondeo de otras claves
4. DHace que la tabla quede ordenada