Hoja de ejercicios de Estructuras de datos con soluciones

En un grafo no dirigido, ¿qué es el grado de un vértice?

1. AEl número de aristas conectadas a él
2. BLa longitud del camino más largo que parte de él
3. CEl número de vértices del grafo
4. DSu posición en la lista de adyacencia

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

1. An
2. Bn + 1
3. C2n
4. Dn − 1

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 camino más corto a todos los demás vértices
4. DEl número total de aristas del grafo

Un nodo de un árbol binario de búsqueda tiene subárbol derecho. ¿Dónde está su sucesor en orden?

1. ASiempre en su hijo derecho
2. BEn el nodo situado más a la izquierda de su subárbol derecho
3. CSiempre en su padre
4. DEn el nodo situado más a la derecha de su subárbol izquierdo

Una red de carreteras tiene 100,000 cruces, cada uno conectado con unos 4 más. ¿Qué representación es la más adecuada?

1. AUn único arreglo ordenado de vértices
2. BMatriz de adyacencia
3. CLista de adyacencia
4. DUn montículo binario de aristas

¿Para qué sirve un nodo centinela (ficticio) en una lista enlazada?

1. APara almacenar el número de elementos
2. BPara impedir que la lista crezca más allá de un número máximo fijo de nodos
3. CPara simplificar el código eliminando los casos especiales en la cabeza o en la cola
4. DPara mantener la lista ordenada

En un búfer circular, front == rear puede significar que está vacío o que está lleno. ¿Cuál es una forma habitual de distinguirlo?

1. AHacer que el tamaño del búfer sea una potencia de dos
2. BVaciar siempre el búfer cuando front es igual a rear, de modo que el estado sea vacío
3. CGuardar front y rear en la misma variable
4. DMantener un contador de elementos aparte, o dejar siempre una posición sin usar

Sin unión por rango ni compresión de caminos, ¿cuál es el coste en el peor caso de un solo find en una estructura union-find con n elementos?

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