Hoja de ejercicios de Estructuras de datos con soluciones

¿Qué es un grafo ponderado?

1. AUn grafo en el que algunos vértices pesan más que otros porque tienen más aristas
2. BUn grafo en el que cada arista tiene un valor numérico, como un coste o una distancia
3. CUn grafo que se almacena en disco
4. DUn grafo con más aristas que vértices

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

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

En un árbol, ¿qué es una hoja?

1. AUn nodo sin hijos
2. BEl nodo con el valor más grande
3. CUn nodo con exactamente un hijo
4. DUn nodo sin padre

¿Cuánto tarda la búsqueda de una palabra de longitud L en un trie con un alfabeto fijo?

1. AO(n), donde n es el número de palabras
2. BO(L × n)
3. CO(log n), donde n es el número de palabras
4. DO(L), independientemente de cuántas palabras haya almacenadas

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

En un min-heap binario almacenado en un arreglo (con índices desde 0), los hijos del nodo en el índice i están en:

1. A2i + 1 y 2i + 2
2. B2i y 2i + 1
3. Ci + 1 e i + 2
4. Di/2 e i/2 + 1

Debes conservar los k valores más pequeños de un flujo de n números usando O(k) de memoria. ¿Qué enfoque funciona en un tiempo O(n log k)?

1. AUn arreglo ordenado con los n valores
2. BUn max-heap de tamaño k, sustituyendo su raíz cuando llega un valor menor
3. CUn min-heap que contiene los n valores, del que se extraen al final los k menores
4. DUna cola FIFO con los últimos k valores

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. CReconstruyendo desde cero el subárbol que hay debajo y reinsertando todas las claves que contenía
4. DEliminando todo el subárbol