Hoja de ejercicios de Estructuras de datos con soluciones

En la representación de un grafo mediante listas de adyacencia, ¿qué se almacena para cada vértice?

1. AUna fila de V valores booleanos
2. BUna lista de sus vértices vecinos
3. CEl número total de aristas del grafo
4. DEl camino más corto a todos los demás vértices

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

1. An + 1
2. B2n
3. Cn
4. Dn − 1

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

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

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

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

¿Cuál es la altura en el peor caso de un árbol binario de búsqueda con n nodos si las claves se insertan en orden?

1. An (se convierte en una lista enlazada)
2. B√n
3. C1
4. Dlog₂ n

Las claves 50, 30, 70, 20, 40 se insertan en este orden en un árbol binario de búsqueda vacío. ¿Cuál es el hijo izquierdo de 30?

1. A70
2. B50
3. C20
4. D40

¿Qué estructura de datos permite una caché LRU (least recently used) con get y put en O(1)?

1. ASolo una pila
2. BSolo un árbol binario de búsqueda
3. CUn mapa hash combinado con una lista doblemente enlazada
4. DUn único arreglo ordenado

Eliminar un nodo con dos hijos de un árbol binario de búsqueda se hace normalmente:

1. AReconstruyendo desde cero el subárbol que hay debajo y reinsertando todas las claves que contenía
2. BEliminando todo el subárbol
3. CIntercambiándolo con la raíz
4. DReemplazándolo por su sucesor en orden (o predecesor) y eliminando ese nodo