estructura de datos

ILI‑134 ESTRUCTURA DE DATOS

Segundo Certamen – Primer Semestre 2010
Martes 15-06-2010, 14 horas
Tiempo: 90 Minutos

PREGUNTA 1 (25 Puntos) Listas

Los nodos de una lista enlazada a travésde punteros tienen la siguiente estructura: struct nodo {int dato; struct nodo *next;}; Los nodos no están ordenados por el valor del campo dato y los valores se pueden repetir en la lista. Programeuna función en C/C++ que elimina de la lista todos los nodos que tienen en el campo dato un valor dado. Para eliminar nodos de la lista se deben usar las funciones que se vieron en clases voidlistaPrimeroRemover(nodo *&ptrCabecera) y void listaRemover(nodo* ptrPrevio) respectivamente.

PREGUNTA 2 (25 Puntos) Árbol Binario

a) ¿Cuál es la cantidad máxima de niveles de un árbol binario debúsqueda con 100 nodos?
b) ¿Cuál es la cantidad mínima de niveles de un árbol binario de búsqueda con 100 nodos?
c) ¿Cuál es la cantidad máxima de nodos de un árbol binario de N niveles? (OJO: La raízestá en el nivel 0)
d) Si usted desea recorrer un árbol binario de búsqueda escribiendo todos los elementos a un archivo y después reconstruir el árbol binario de búsqueda desde los elementos delarchivo, ¿sería el recorrido en orden simétrico el más adecuado? ¿Por qué si o por qué no?
e) 100 números enteros ordenados se ingresan a una lista enlazada a través de punteros y a un árbol binario debúsqueda. Describa la complejidad temporal en términos de Big-O para una función de búsqueda en la lista y en el árbol.

PREGUNTA 3 (25 Puntos) Grafos Dirigidos – Componentes Fuertemente ConexosDetermine los componentes fuertemente conexos del siguiente grafo dirigido anotando todos los pasos realizados:
1-2, 2-3, 2-4, 3-1, 4-5, 4-6, 5-2, 5-6

Inicie la determinación en el nodo 1 y avance encaso de alternativas en orden numérico.

PREGUNTA 4 (25 Puntos) Grafos Dirigidos – Algoritmo de Floyd

Calcule las longitudes de los caminos más cortos entre todos los pares de nodos del...