Hoja de ejercicios de Estructuras de datos con soluciones

Una tabla hash almacena los datos como:

1. AUn árbol con claves ordenadas
2. BUna lista ordenada únicamente
3. CPares clave–valor localizados mediante una función hash
4. DUna cadena de longitud fija

¿Cómo se llama la operación de una pila que añade un elemento en la cima?

1. AEnqueue
2. BPeek
3. CPop
4. DPush

¿Cómo se almacenan en memoria los elementos de un arreglo?

1. ADispersos y enlazados mediante punteros
2. BEn posiciones aleatorias elegidas por un hash
3. CEn un árbol de páginas de memoria
4. DEn un bloque contiguo, uno tras otro

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 postorden?

1. A4 5 2 3 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D5 4 3 2 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

¿Cuál es el coste de insertar un elemento en medio de un arreglo de n elementos?

1. AO(n), porque los elementos posteriores deben desplazarse
2. BO(1), porque se conoce el índice
3. CO(log n), por la búsqueda binaria
4. DO(n²), porque cada elemento se mueve n veces

¿Qué hace un splay tree después de cada acceso?

1. AReconstruye todo el árbol en forma balanceada
2. BSube mediante rotaciones el nodo accedido hasta la raíz
3. CMueve el nodo accedido a una hoja
4. DRecolorea los nodos del camino de búsqueda

¿Cuál es el tiempo de ejecución de la búsqueda en anchura en un grafo con V vértices almacenado como matriz de adyacencia?

1. AO(V)
2. BO(V + E)
3. CO(E log V)
4. DO(V²)