Hoja de ejercicios de Estructuras de datos con soluciones

Una tabla hash almacena los datos como:

1. AUna lista ordenada únicamente
2. BPares clave–valor localizados mediante una función hash
3. CUna cadena de longitud fija
4. DUn árbol con claves ordenadas

En un grafo, ¿qué es un ciclo?

1. AUn vértice sin aristas
2. BUn camino que visita todos los vértices
3. CUna arista con peso cero
4. DUn camino que empieza y termina en el mismo vértice

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

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

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

1. ABúsquedas por prefijo, como el autocompletado
2. BAlmacenar matrices
3. CEncontrar caminos más cortos
4. DOrdenar números

¿Qué tipo abstracto de datos usa el algoritmo de Dijkstra para elegir el siguiente vértice que procesar?

1. AUna cola FIFO
2. BUna cola de prioridad de mínimos
3. CUna pila
4. DUn conjunto sin orden

¿Cómo se inserta un elemento nuevo en un montículo binario?

1. ASe inserta en su posición ordenada desplazando una posición a la derecha todos los elementos mayores
2. BSe reconstruye todo el montículo desde cero
3. CSe coloca al final del arreglo y se hace subir (sift-up) mientras viole la propiedad de montículo
4. DSe coloca en la raíz y se hace bajar (sift-down)

Un árbol de Fenwick (binary indexed tree) sobre un arreglo de n números permite, ¿qué operaciones en O(log n)?

1. AOrdenar el arreglo y la búsqueda binaria
2. BEncontrar la mediana en O(1)
3. CConsultas de sumas de prefijos y actualizaciones de un solo elemento
4. DInsertar elementos en cualquier posición

En el algoritmo de Kruskal para el árbol de expansión mínima, ¿para qué se usa la estructura union-find?

1. APara elegir el vértice inicial
2. BPara almacenar la distancia actual de cada vértice al origen durante la búsqueda
3. CPara ordenar las aristas por peso
4. DPara comprobar si los dos extremos de una arista ya están conectados