Hoja de ejercicios de Estructuras de datos con soluciones

En una tabla hash, ¿qué es una colisión?

1. AQue una clave no se pueda pasar por la función hash
2. BQue dos claves iguales se almacenen dos veces
3. CQue dos claves distintas se asignen al mismo índice
4. DQue la tabla se quede sin memoria

¿Qué estructura se utiliza normalmente para implementar una cola de prioridad?

1. AUna cadena de caracteres
2. BUna lista simplemente enlazada sin orden
3. CUn montículo (heap)
4. DUna pila (stack)

La altura de un árbol se define habitualmente como:

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

Un recorrido en orden (in-order) de un árbol binario de búsqueda visita las claves en:

1. AOrden ascendente
2. BOrden de inserción
3. COrden por niveles
4. DSiempre orden descendente

¿Cómo se encuentra la clave mínima en un árbol binario de búsqueda?

1. ASeguir los hijos derechos desde la raíz hasta que no haya hijo derecho
2. BVisitar todas las hojas y compararlas
3. CMirar solo la raíz
4. DSeguir los hijos izquierdos desde la raíz hasta que no haya hijo izquierdo

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. AUn único arreglo ordenado de vértices
2. BUn montículo binario de aristas
3. CMatriz de adyacencia
4. DLista de adyacencia

¿Qué propiedad debe cumplir un árbol rojo-negro?

1. ATodo camino desde un nodo hasta sus hojas descendientes tiene el mismo número de nodos negros
2. BTodos los nodos deben ser rojos
3. CLa raíz debe ser roja
4. DTodo nodo rojo debe tener hijos rojos, así que los nodos rojos forman siempre cadenas ininterrumpidas hasta las hojas

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

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