Hoja de ejercicios de Estructuras de datos con soluciones

¿Dónde se encuentra el elemento más pequeño de un min-heap binario?

1. AEn la raíz
2. BEn cualquier hoja, que hay que buscar
3. CEn la hoja situada más a la izquierda
4. DEn la última posición del arreglo

En un árbol, ¿qué son los nodos hermanos?

1. ANodos a la misma profundidad en subárboles distintos
2. BNodos que tienen el mismo padre
3. CNodos que no tienen hijos
4. DUn nodo y su padre

¿Qué es la propiedad de max-heap?

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

Se implementa una cola con dos pilas: push en una pila «entrada» y pop de una pila «salida», que se rellena desde «entrada» cuando está vacía. ¿Cuál es el coste amortizado por operación?

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

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

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

¿Qué estructura de datos utiliza la búsqueda en profundidad (DFS) en su versión iterativa?

1. ASolo una tabla hash
2. BUn montículo
3. CUna cola
4. DUna pila

La estructura union-find (conjuntos disjuntos) con unión por rango y compresión de caminos tiene un coste amortizado por operación de:

1. AO(α(n)), la inversa de la función de Ackermann, que en la práctica es constante
2. BO(n²)
3. CO(n)
4. DExactamente O(log n)

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

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