Hoja de ejercicios de Estructuras de datos con soluciones

Un grafo está formado por:

1. AVértices (nodos) conectados por aristas
2. BSolo claves y hashes
3. CFilas y columnas
4. DSolo una raíz y hojas

¿Qué estructura de datos se usa para hacer un recorrido por niveles de un árbol?

1. ACola
2. BCola de prioridad
3. CTabla hash
4. DPila

¿Cuál es el rasgo que define a un conjunto como tipo abstracto de datos?

1. ASolo permite el acceso por un extremo
2. BAlmacena elementos sin duplicados
3. CAlmacena elementos en orden
4. DAlmacena pares clave-valor

¿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. A1
2. Bn (se convierte en una lista enlazada)
3. C√n
4. Dlog₂ n

¿Cuánto se tarda en comprobar si existe la arista (u, v) con una matriz de adyacencia?

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

¿Cómo se encuentra la clave mínima en un árbol binario de búsqueda?

1. ASeguir los hijos derechos desde la raíz hasta que no haya hijo derecho
2. BSeguir los hijos izquierdos desde la raíz hasta que no haya hijo izquierdo
3. CVisitar todas las hojas y compararlas
4. DMirar solo la raíz

¿Por qué podría un servidor elegir su función hash al azar de entre una familia universal?

1. APara eliminar la necesidad de redimensionar la tabla
2. BPara garantizar que dos claves nunca puedan colisionar, sean cuales sean las claves que envíe un atacante
3. CPara que sea muy improbable que un atacante pueda elegir muchas claves que colisionen todas
4. DPara que la tabla hash quede ordenada

Un árbol de segmentos (segment tree) se usa normalmente para:

1. AOrdenar cadenas alfabéticamente almacenando cada prefijo en un nodo distinto del árbol
2. BImplementar una pila
3. CAlmacenar las aristas de un grafo
4. DResponder consultas por rangos (como sumas de rangos) y actualizaciones en O(log n)