FACULTAD DE INGENIERA Y CIENCIAS EXACTAS
DEPARTAMENTO DE TECNOLOGA INFORMTICA
Programacin II
Trabajo Prctico 1 TDAs: Conceptos Bsicos. Definicin, implementacin y
utilizacin. Clculo de Costos.
TDA Pila
1) Definir el TDA Pila, listando las operaciones asociadas y establecer sus precondiciones.
2) A partir del TDA Pila definido, escribir distintos mtodos que permitan
a)
Pasar una Pila a otra (dejndola en orden inverso)
b)
Copiar una Pila en otra (dejndola en el mismo orden que la original)
c)
Invertir el contenido de una Pila.
d)
Contar los elementos de una Pila
e)
Sumar los elementos de una Pila
f)
Calcular el promedio de los elementos de una Pila
TDA Cola
3) Definir el TDA Cola, listando las operaciones asociadas y establecer sus precondiciones.
4) A partir del TDA Cola definido, escribir distintos mtodos que permitan
a)
Pasar una Cola a otra
b)
Invertir el contenido de una Cola (pueden usarse Pilas auxiliares)
c)
Invertir el contenido de una Cola (NO pueden usarse Pilas auxiliares)
d)
Determinar si el final de la Cola C1 coincide o no con la Cola C2.
e)
Determinar si una Cola es capica o no. Para ser capica debe cumplir
que el primer elemento es igual al ltimo, el segundo igual al penltimo, etc.
f)
Determinar si la Cola C1 es la inversa de la Cola C2. Dos Colas sern
inversas, si tienen los mismos elementos pero en orden inverso.
TDA Cola con Prioridades
5) Definir el TDA Cola con prioridades, listando las operaciones asociadas y establecer sus
precondiciones.
6) A partir del TDA Cola con prioridades definido, escribir un mtodo que permita
a)
Combinar dos colas con prioridades CP1 y CP2, generando una nueva
cola con prioridades. Considerar que a igual prioridad, los elementos de la CP1
son ms prioritarios que los de la CP2.
b)
Determinar si dos Colas con prioridad son idnticas.
Implementaciones y Costos
7) Escribir al menos dos implementaciones distintas (basadas en arreglos) del TDA Pila
definido en 1). Comparar los costos de cada una de las operaciones.
8) Escribir al menos dos implementaciones distintas (basadas en arreglos) del TDA Cola
definido en 3). Comparar los costos de cada una de las operaciones.
9) Escribir al menos dos implementaciones distintas (basadas en arreglos) del TDA Cola con
prioridades definido en 5). Comparar los costos de cada una de las operaciones.
Trabajo Prctico 2 TDAs: Implementacin utilizando estructuras dinmicas. Costos.
TDA Conjunto. TDA Diccionario.
TDA Pila, TDA Cola y TDA Cola con Prioridades
1) Implementar los TDA Pila, TDA Cola y TDA Cola con Prioridades definidos en los ejercicios
nmero 1), 3) y 5) del TP1 (respectivamente) con listas dinmicas.
2) Calcular y comparar los costos de las operaciones tpicas de cada uno de los TDAs
anteriores para las implementaciones basadas en arreglos del TP1 y la propuesta en el
ejercicio anterior.
TDA Conjunto
3) Definir el TDA Conjunto, listando las operaciones asociadas.
4) Implementar el TDA Conjunto con las siguientes restricciones
a) Tamao mximo acotado
b) Tamao mximo no acotado
c) Universo acotado. Considerar por ejemplo el Universo de los nmeros enteros
entre 0 y N.
En todos los casos, dar al menos dos implementaciones utilizando arreglos y con listas
dinmicas.
5) Comparar los costos de las operaciones definidas en el TDA Conjunto segn las
implementaciones del ejercicio anterior.
6) Escribir los mtodos externos al TDA que implementan las operaciones interseccin, unin y
diferencia.
TDA Diccionario
7) Definir el TDA Diccionario, listando las operaciones asociadas. Considerar los dos casos
vistos en clase: a) cada clave est asociada a un nico valor, y b) cada clave est asociada
a un conjunto de valores.
8) Implementar el TDA Diccionario, considerando las dos alternativas del ejercicio anterior
a) cada clave est asociada a un nico valor
b) cada clave est asociada a un conjunto de valores.
En ambos casos, dar al menos una implementacin utilizando arreglos y una con listas
dinmicas.
9) Comparar los costos de las operaciones definidas en el TDA Diccionario segn las
implementaciones del ejercicio anterior.
Trabajo Prctico 3 Utilizacin de TDAs.
(En todos los ejercicios siguientes calcular el costo espacial y temporal de los mtodos escritos)
1) A partir del TDA Pila, escribir distintos mtodos externos que permitan:
a) Comprobar si una Pila P es capica (el elemento del tope es igual al de la base,
el segundo igual al anteltimo, etc.)
b) Eliminar de una Pila P las repeticiones de elementos, dejando un representante
de cada uno de los elementos presentes originalmente. Se deber respetar el
orden original de los elementos, y en el caso de los repetidos se conservar el
primero que haya ingresado en P.
c) Repartir una Pila P en dos mitades M1 y M2 de elementos consecutivos,
respetando el orden. Asumir que la Pila P contiene un nmero par de elementos.
d) Generar el conjunto de elementos que se repiten en una Pila.
2) A partir del TDA Cola, escribir distintos mtodos externos que permitan
a) Eliminar de una Cola C las repeticiones de elementos, dejando un representante
de cada uno de los elementos presentes originalmente. Se deber respetar el
orden original de los elementos, y en el caso de los repetidos se conservar el
primero que haya ingresado en C.
b) Repartir una Cola C en dos mitades M1 y M2 de elementos consecutivos,
respetando el orden. Asumir que la cantidad de elementos de C es par.
c) Generar el conjunto de elementos que se repiten en una Cola,
3) A partir del TDA Conjunto, escribir distintos mtodos externos que permitan
a) Calcular la diferencia simtrica entre dos conjuntos A y B (definido en clase).
b) Sin utilizar las operaciones unin, interseccin y diferencia.
c) Utilizando las operaciones unin, interseccin y diferencia.
d) Determinar si dos conjuntos son iguales.
e) Calcular la cardinalidad (cantidad de elementos) de un conjunto.
f) Generar el conjunto de elementos que estn tanto en la Pila P y en la Cola C.
g) Determinar si los elementos de una Pila P son los mismos que los de una Cola
C. No interesa el orden ni si estn repetidos o no.
4) A partir del TDA ColaPrioridad
a) Escribir un mtodo externo que permita generar un Diccionario Mltiple que
permita, para cada valor presente en la ColaPrioridad C recuperar todas las
prioridades que tiene asociadas en C.
5) A partir del TDA Diccionario, escribir distintos mtodos externos que permitan
5.1) Dados dos DiccionarioMultipleTDA D1 y D2, generar un DiccionarioMultipleTDA que
contenga:
a) las claves presentes en D1 y D2, con todos los elementos asociados a cada clave.
b) las claves presentes en D1 y D2, con todos los elementos comunes a las claves
coincidentes en ambos.
c) las claves comunes de D1 y D2, con todos los elementos asociados a cada clave.
d) las claves comunes de D1 y D2, con todos los elementos comunes a las claves
coincidentes en ambos.
5.2) Dado un Diccionario Simple D, que representa el concepto clsico de diccionario: la
clave representa una palabra y el valor su significado. Generar un Diccionario Mltiple DS
que a partir de un significado s, vincule todas las palabras que tienen dicho significado, es
decir que son sinnimos. Cada clave s ser un significado y los valores asociados
(sinnimos) aquellas claves de D que tenan asociado el valor s.
Trabajo Prctico 4 TDA rbol Binario de Bsqueda (ABB). Uso de la Recursin.
(En todos los ejercicios siguientes calcular el costo espacial y temporal de los mtodos escritos)
TDA ABB
1) Definir el TDA ABB, con las siguientes operaciones asociadas (segn lo visto en clase):
a)
Raiz
b)
HijoIzq
c)
HijoDer
d)
ArbolVacio
e)
InicializarArbol
f)
AgregarElem
g)
EliminarElem
2) Implementar el TDA ABB definido en el ejercicio anterior, utilizando estructuras dinmicas.
Utilizacin del TDA ABB / Uso de la Recursin.
3) A partir del TDA ABB, escribir mtodos externos que resuelvan los siguientes problemas.
En caso de ser posible, escribir la versin iterativa y la versin recursiva de los mtodos.
a)
Dado un elemento, determinar si est o no en un ABB.
b)
Dado un elemento, determinar si es una hoja de un ABB.
c)
Dado un elemento, calcular su profundidad en el ABB.
d)
Obtener el valor del menor elemento de un ABB.
e)
Calcular la cantidad de elementos que contiene un ABB.
f)
Calcular la suma de los elementos que contiene un ABB.
g)
Calcular el cantidad de hojas de un ABB
h)
Calcular la altura de un ABB.
i)
Comprobar si dos ABBs tienen la misma forma.
j)
Comprobar si dos ABBs son iguales.
k)
Contar la cantidad de elementos que estn en un cierto nivel N.
l)
Mostrar por pantalla todos los elementos que contiene un ABB
[Link]-orden
[Link]-orden
[Link]-orden
m)
Dado un valor k, arme un conjunto con todos los elementos del ABB que son
mayores que k.
n)
Dado un elemento de valor v (que est presente en el ABB), obtener el elemento
del rbol que es inmediatamente anterior (en valor).
Trabajo Prctico 5 rbol Binario de Bsqueda Balanceado (AVL) y rbol B.
(En todos los ejercicios siguientes calcular el costo espacial y temporal de los mtodos escritos)
rbol AVL
1) Indicar si los siguientes rboles binarios de bsqueda cumplen con la propiedad de AVL y
justificar la respuesta. En caso negativo, indicar si se puede balancear con rotaciones a
izquierda o derecha, simples o dobles. En aquellos que sea posible el balanceo llevar a cabo el
mismo mostrando la secuencia de pasos correspondientes:
a)
41
32
70
25
45
38
16
78
27
55
26
82
48
52
53
49
41
b)
32
25
16
45
38
27
26
70
43
78
55
48
82
2) Dados los siguientes rboles AVL, insertar los valores que se indican. En caso de que el
rbol no cumpla la propiedad de AVL, mostrar la secuencia de pasos que se deberan llevar
a cabo para que el rbol vuelva a ser un AVL.
a)
Insertar el valor 28.
41
32
70
38
25
45
78
34
16
43
30
29
55
82
48
b)
Al rbol resultante de la insercin anterior, agregar el valor 47.
c)
Insertar el valor 84
41
32
70
38
25
45
78
34
16
43
55
82
48
rbol B
3) Dados los siguientes rboles, indicar si los mismos son rboles B, y en caso negativo indicar
por qu.
a)
10
12
14
17
21
51
22
26
27
30
b)
13
10
11
14
21
45
17
22
24
27
46
48
54
55
58
22
24
27
30
48
50
55
58
c)
12
10
14
21
45
17
4) Dado el siguiente rbol B, insertar el valor 67 en primer lugar. Al rbol resultante insertar el
valor 32. En caso de requerir reestructuracin del rbol, mostrar la secuencia de la misma.
13
10
14
21
45
17
22
24
27
30
49
52
57
5) Dado el siguiente rbol B, eliminar el valor 45 en primer lugar.
13
14
17
21
45
26
29
49
60
60
Trabajo Prctico 6 Grafos
(En todos los ejercicios siguientes calcular el costo espacial y temporal de los mtodos escritos)
TDA Grafo
1) Definir la interface del TDA Grafo, con las operaciones asociadas (segn lo visto en clase):
2) Implementar el TDA Grafo definido en el ejercicio anterior, utilizando matriz de adyacencia.
3) Implementar el TDA Grafo definido en el ejercicio anterior, utilizando listas de adyacencia.
Utilizacin del TDA Grafo
4) Dado un Grafo G y un vrtice v, calcular el conjunto de vrtices AdyacentesDobles de v.
Se define que un vrtice w es adyacente doble de un vrtice v, si existe otro vrtice x y hay
una arista que comienza en v y termina en x y otra que comienza en x y termina en w.
5) Dado un vrtice v de un grafo, calcular el mayor de los costos de las aristas salientes.
6) Dado un Grafo G y un vrtice v, escribir un mtodo que permita obtener el conjunto de los
Predecesores del vrtice v en G.
Se define que un vrtice o es predecesor de otro vrtice d, si hay una arista que comienza
en o y termina en d.
7) Dado un Grafo G escribir un mtodo que permita obtener el conjunto de los vrtices aislados
en G.
Se define que un vrtice v es aislado si v no tiene aristas entrantes ni salientes.
8) Dado un Grafo G y dos vrtices v1 y v2, escribir un mtodo que permita obtener el conjunto
de todos los vrtices puente entre v1 y v2.
Se define que un vrtice p es puente entre dos vrtices o y d, si hay una arista que
comienza en o y termina en p y otra que comienza en p y termina en d.
9) Dado un Grafo G y un vrtice v, calcular el grado de v.
Se define el grado de un vrtice v como el entero que es igual a la resta entre la cantidad de
aristas que salen de v menos la cantidad de aristas que llegan a v.