Download Examen de Programación 2

Instituto de Computación. Facultad de Ingeniería. Universidad de la República
Examen de Programación 2
03 de Agosto de 2006
Generalidades:
•
•
•
•
•
•
•
La prueba es individual y sin material.
La duración es 3 horas.
Sólo se contestan dudas acerca de la letra de los ejercicios.
Escriba las hojas de un sólo lado y con letra clara.
Comience la solución de cada ejercicio en una nueva hoja.
Numere cada hoja, indicando en la primera el total.
Coloque su número de cédula y nombre en cada hoja.
Ejercicio 1 (40 puntos: 25 parte (a) y 15 parte (b))
Considere la siguiente declaración, en Módula-2, del tipo de los árboles binarios de búsqueda de enteros que
almacenan en cada nodo la cantidad de elementos (nodos) en su subárbol izquierdo más 1, además del dato:
ABB = POINTER TO ABNode;
ABNode = RECORD
Dato : INTEGER;
CantSubIzq : CARDINAL;
Izq : ABB;
Der : ABB;
END;
Ejemplo:
Dato: 6, CantSubIzq: 5
6
Dato: 2, CantSubIzq: 3
2
-1
9
4
Dato: 9, CantSubIzq: 1
Dato: -1, CantSubIzq: 2
Dato: 4, CantSubIzq: 1
-7
Dato: -7, CantSubIzq: 1
Se pide, sin usar funciones o procedimientos auxiliares y accediendo directamente a la representación:
a) Escribir en Módula-2 una función recursiva de inserción de un entero en un árbol binario de búsqueda de tipo
ABB, de tal manera que cada nodo luego de la inserción guarde en el campo CantSubIzq la cantidad de elementos
en su subárbol izquierdo más 1. La función debe retornar TRUE si el entero se inserta en el árbol (no estaba
previamente) y FALSE en caso contrario. Asuma que en el árbol parámetro, el campo CantSubIzq guarda el valor
apropiado para cada nodo (esto es, la cantidad de elementos en su subárbol izquierdo más 1).
La función NO debe recorrer explícitamente más de un camino del árbol. En el árbol del ejemplo previo los
caminos (expresados como listas) son 3: [6,2,-1,-7], [6,2,4] y [6,9].
PROCEDURE Insertar(VAR t : ABB; e : INTEGER) : BOOLEAN;
b) Escribir en Módula-2 una función iterativa que dados un número natural k y un árbol binario de búsqueda de
tipo ABB, retorne un puntero al k-ésimo menor elemento del árbol. Si no hay al menos k elementos en el árbol o k es
cero, la función debe retornar el puntero NIL. Si k es 1, nos referimos al menor elemento del árbol, si k es 2 al
segundo elemento más pequeño del árbol y así sucesivamente. Asuma que en el árbol parámetro, el campo
CantSubIzq guarda el valor apropiado para cada nodo (esto es, la cantidad de elementos en su subárbol izquierdo
más 1).
La función no debe recorrer explícitamente más de un camino del árbol.
PROCEDURE kMenor(t : ABB; k : CARDINAL) : ABB;
Ejercicio 2 (60 puntos: 10 parte (a), 20 parte (b) y 30 parte (c))
Una coordenada es un tipo de datos de nombre Coord que contiene un par (X, Y) de elementos de tipo INTEGER.
El TAD Coord contiene las siguientes operaciones:
•
•
•
•
PROCEDURE CrearCoord (X, Y : INTEGER): Coord;
(* Crea una coordenada con el par (X, Y) *)
PROCEDURE CoordX (C : Coord): INTEGER;
(* Retorna el primer elemento de C. *)
PROCEDURE CoordY (C : Coord): INTEGER;
(* Retorna el último elemento de C. *)
PROCEDURE DestruirCoord (VAR C : Coord);
(* Destruye la coordenada C *)
a) Se debe especificar el TAD ConjCoord (Conjunto de coordenadas) con las operaciones usuales de conjuntos
más las siguientes operaciones:
•
Dado un entero X, y un conjunto de coordenadas A se debe retornar un conjunto de coordenadas con todas
las coordenadas de A que contienen a X como primer elemento del par.
•
Dado un entero Y, y un conjunto de coordenadas A se debe retornar un conjunto de coordenadas con todas
las coordenadas de A que contienen a Y como último elemento del par.
b) Suponga que el tipo de datos ConjCoord tiene la siguiente representación:
TYPE
ConjCoord = POINTER TO RECORD
c : Coord;
sig : ConjCoord
END;
Implemente la operación que retorna la diferencia entre dos conjuntos de coordenadas. Si usa funciones o
procedimientos auxiliares, deberá implementarlos.
c) Utilizando las operaciones del TAD ConjCoord implemente la operación:
PROCEDURE CoordenadasInternas(C1, C2 : Coord; Conj : ConjCoord): ConjCoord;
(* Retorna todas las coordenadas de Conj que se encuentran dentro del rectángulo formado por los puntos
(C1.X, C1.Y), (C2.X, C1.Y), (C2.X, C2.Y), (C1.X, C2.Y). Si hay elementos en el borde del cuadrado también
deben aparecer en el conjunto resultado. *)
La implementación NO deberá iterar explícitamente sobre todas las coordenadas del rectángulo determinado por
las coordenadas C1 y C2.
Por ejemplo:
Conj
[(1,2), (3,5), (1,1)]
[(1,-2), (3,-5), (-1,-1)]
[(1,-2), (3,-5), (-1,-1)]
C1
(0,0)
(0,0)
(1,0)
C2
(3,5)
(3,5)
(3,-2)
Resultado
[(1,2), (3,5), (1,1)]
[]
[(1,-2)]
SOLUCIONES
Ejercicio 1.a)
Considere la siguiente definición extendida de árbol binario de búsqueda de enteros:
TYPE
ABB = POINTER TO ABBNode;
ABBNode = RECORD
Dato : INTEGER;
CantSubIzq : CARDINAL;
Izq : ABB;
Der : ABB;
END;
La cual almacena en cada nodo la cantidad de hijos izquierdos + 1, se pide la implementación
de una función recursiva que inserte un elemento en dicho árbol manteniendo consistente la
estructura del mismo, y retornando TRUE si el elemento se insertó en el árbol y FALSE en caso
contrario:
(*
Función que inserta el elemento k en el ABB t, manteniendo consistente la información de la
cantidad de hijos izquierdos. Retorna TRUE si k efectivamente se insertó en el árbol (no
estaba previamente) y FALSE en caso contrario.
*)
PROCEDURE Insertar(VAR t : ABB; k : INTEGER): BOOLEAN;
BEGIN
IF (t = NIL) THEN
NEW(t);
t^.Dato := k;
t^.CantSubIzq := 1;
t^.Izq := NIL;
t^.Der := NIL;
RETURN TRUE
ELSE
IF (k < t^.Dato) THEN
IF (Insertar(t^.Izq, k))
t^.CantSubIzq := t^.CantSubIzq + 1 ;
RETURN TRUE
ELSE RETURN FALSE
END
ELSIF (k > t^.Dato) THEN
RETURN Insertar(t^.Der, k)
ELSE RETURN FALSE
END
END
END Insertar;
Ejercicio 1.b)
Usando la definición anterior de ABB, se pide la construcción de una función tal que dado un
árbol del tipo ABB y un natural k, retorne el k-ésimo elemento menor del árbol:
(*
Función que retorna el k ésimo elemento menor de t.
Asumimos que el árbol no tiene elementos repetidos.
*)
PROCEDURE KMenor(t : ABB; k : CARDINAL) : ABB;
BEGIN
IF (k = 0)
THEN
RETURN NIL
ELSE WHILE (t <> NIL) AND (k <> t^.CantSubIzq) DO
IF (k < t^.CantSubIzq) THEN
t := t^.Izq
ELSE
k := k - t^.CantSubIzq;
t := t^.Der
END
END;
RETURN t
END
END KMenor;
Ejercicio 2.a)
(*************** Constructoras ***************)
PROCEDURE Vacio () : ConjCoord;
(* retorna el conjunto vacío *)
PROCEDURE Insertar (C : Coord; A : ConjCoord) : ConjCoord;
(* retorna un nuevo conjunto que consta de todos las coordenadas de A más
la coordenada C, si es que C no era ya un elemento de A *)
(**************** Predicados ****************)
PROCEDURE EsVacio (A : ConjCoord) : BOOLEAN;
(* retorna TRUE si A es vacío *)
PROCEDURE Pertenece (C : Coord; A : ConjCoord) :BOOLEAN;
(* retorna TRUE si C es una coordenada de A *)
(**************** Auxiliares ****************)
PROCEDURE Union (A, B : ConjCoord) : ConjCoord;
(* retorna el conjunto de las coordenadas que pertenecen a A, o B o a ambos *)
PROCEDURE Intersec (A, B : ConjCoord) : ConjCoord;
(* retorna el conjunto de las coordenadas que pertenecen a A y a B *)
PROCEDURE Dif (A, B : ConjCoord) : ConjCoord;
(* retorna el conjunto de las coordenadas que pertenecen a A y no pertenecen a B *)
PROCEDURE SubconjX (X : INTEGER; A : ConjCoord) :ConjCoord;
(* retorna un conjunto de coordenadas con todas las coordenadas de A que contienen
a X como primer elemento del par *)
PROCEDURE SubconjY (Y : INTEGER; A : ConjCoord) :ConjCoord;
(* retorna un conjunto de coordenadas con todas las coordenadas de A que contienen
a Y como último elemento del par *)
(**************** Destructoras ****************)
PROCEDURE DestruirConjCoord (VAR A : ConjCoord);
(* Destruye el conjunto de coordenadas A *)
Ejercicio 2.b)
PROCEDURE Vacio () : ConjCoord;
BEGIN
RETURN NIL;
END Vacio;
PROCEDURE EsVacio (A : ConjCoord) : BOOLEAN;
BEGIN
RETURN A = NIL;
END EsVacio;
PROCEDURE Pertenece (C : Coord; A : ConjCoord) :BOOLEAN;
VAR res: BOOLEAN;
BEGIN
IF EsVacio(A) THEN
res := FALSE;
ELSE
res := (CoordX(A^.c) = CoordX(C)) AND (CoordY(A^.c) = CoordY(C))
OR Pertenece(C, A^.sig);
END;
RETURN res;
END Pertenece;
PROCEDURE Insertar (C : Coord; A : ConjCoord) :ConjCoord;
VAR res: ConjCoord;
BEGIN
IF NOT Pertenece(C, A) THEN
NEW(res);
res^.c := C;
res^.sig := A
ELSE
res := A
END;
RETURN res;
END Insertar;
PROCEDURE Dif (A, B : ConjCoord) : ConjCoord;
VAR
res, iterador: ConjCoord;
BEGIN
res := Vacio();
iterador := A;
WHILE NOT EsVacio(iterador) DO
IF NOT Pertenece(iterador^.c, B) THEN
res := Insertar(iterador^.c, res);
END;
Iterador := iterador^.sig;
END;
RETURN res;
END Dif;
Ejercicio 2.c)
PROCEDURE CoordenadasInternas(C1, C2 : Coord; Conj : ConjCoord): ConjCoord;
VAR
i, incremento: INTEGER;
res1, res2: ConjCoord;
BEGIN
(* Se calcula en res1 el conjunto de coordenadas con X dentro del rango *)
incremento := (CoordX(C2) - CoordX(C1)) / ABS(CoordX(C2) - CoordX(C1));
i := CoordX(C1)-incremento;
res1 := Vacio();
REPEAT
i := i + incremento;
res1 := Union(res1, SubconjX(i, Conj));
UNTIL i = CoordX(C2);
(* Se calcula en res2 el subconjunto de res1 con Y dentro del rango *)
incremento := (CoordY(C2) - CoordY(C1)) / ABS(CoordY(C2) - CoordY(C1));
i := CoordY(C1)-incremento;
res2 := Vacio();
REPEAT
i := i + incremento;
res2 := Union(res2, SubconjY(i, res1));
UNTIL i = CoordY(C2);
RETURN res2;
END CoordenadasInternas;