Altillo.com > Exámenes > UBA - Ingeniería > Algoritmos y Programación II

Ejercicio 1. Escribir una función que recibe a un árbol binario T y dos nodos x e y del mismo tipo de los nodos de T y devuelve dos datos:
a) Un valor booleano indicando si x es descendiente de y o no.
b) La cantidad de descendentes propios (esto es distinto de y ), de y.

Ejercicio 2. Definir el T.D.A. árbol A.V.L. y dar un ejemplo (gráfico) de rotación hacia la izquierda y rotación hacia la derecha, respectivamente, para equilibrar el árbol.

Ejercicio 3. Escribir una función que recibe un grafo conexo, pesado, no dirigido y devuelve un árbol de extensión y su peso total (es decir, la suma de los pesos de las aristas del árbol).
Def. árbol de extensión de un grafo conexo, no dirigido es un árbol libre que contiene todos los vértices del grafo dado.
Def. Un árbol libre es un grafo conexo y sin ciclos.
Def. Ciclo (simple) de un grafo es un camino simple de longitud >=3, que conecta un vértice consigo mismo.

Ejercicio 4. Dado un gráfico dirigido y un elemento de dato del mismo tipo de identificadores de cada vértice, escribir una función que busque ese identificador entre los vértices del grafo, utilizando algún recorrido válido, determinando si está presente en el grafo o no. En caso de que no exista ese elemento de dato del grafo, devuelve, además, la dirección del nodo que lo contiene.

Definir todas las estructuras que se usan en cada ejercicio.