Hoja de ejercicios de Estructuras de datos con soluciones

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

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

¿Qué es un grafo dirigido?

1. AUn grafo que no tiene ciclos
2. BUn grafo cuyas aristas tienen todas peso
3. CUn grafo cuyas aristas tienen un sentido de un vértice a otro
4. DUn grafo en el que cada par de vértices distintos está unido por una arista

¿Qué es la propiedad de max-heap?

1. ALa clave de cada padre es mayor o igual que las claves de sus hijos
2. BTodas las hojas contienen la clave máxima
3. CLa clave de cada hijo izquierdo es mayor o igual que la de su hermano derecho
4. DLas claves están ordenadas de izquierda a derecha

Una aplicación necesita búsquedas rápidas y además listar las claves en orden y responder consultas por rangos. ¿Qué estructura encaja mejor?

1. AUna pila
2. BUn árbol binario de búsqueda balanceado
3. CUna tabla hash
4. DUna lista enlazada sin ordenar

¿Qué estructura de datos se usa para comprobar si los paréntesis de "{[()]}" están equilibrados?

1. AUn árbol binario de búsqueda
2. BUna cola
3. CUna tabla hash
4. DUna pila

¿Cómo funciona extract-min en un min-heap binario?

1. ASe mueve el último elemento a la raíz y se hace bajar (sift-down)
2. BSe elimina el último elemento del arreglo
3. CSe buscan en todas las hojas el nuevo mínimo
4. DSe elimina la raíz y se desplazan todos los elementos una posición a la izquierda

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

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

¿Cuánto se tarda en buscar una clave arbitraria en un min-heap binario de n elementos?

1. AO(1)
2. BO(n)
3. CO(log log n)
4. DO(log n)