Altillo.com > Exámenes > ORT > Programación II

Programación II

Examen Final

Diciembre de 1997 Altillo.com

1. Sea un ARBOL BINARIO DE BUSQUEDA cuyos nodos contienen números enteros NO duplicados y positivos.
Se desea realizar un proceso que emita por pantalla, ordenadas en forma ascendente, las claves de los nodos que sean submúltiplos de la clave contenida en el nodo raíz.
Ejemplo : 
Dado el ARBOL :
              (90)
              /     \
          (30) (100)
           /   \         \
       (15) (50) (180)
        /       /       /
    (07)  (45) (150)
Saldrá por pantalla:
15
30
45

SE PIDE :
a) Declarar la estructura en Pascal.
b) Codificar un procedimiento, con los parámetros adecuados, que resuelva lo pedido. (El procedimiento podrá tener procedimientos locales).
Al menos un procedimiento debe ser RECURSIVO
c) ¿ Cómo recorrió el árbol ?
d) ¿ Pudo utilizar otros recorridos para resolver el ejercicio ?
En caso afirmativo : ¿Cuáles? - Justificar.
En caso negativo : ¿Por qué?

2. Dado el siguiente procedimiento:
Procedure FDIC971 (var ARB: TyPtArb);
Begin
  if ARB <> NIL then
    begin
      if ES_HOJA(ARB^.IZQ) then
        begin
         ARB^.VAL := ARB^.VAL + ARB^.IZQ^.VAL;
         Dispose(ARB^.IZQ);
         ARB^.IZQ := NIL
        end;
      if ES_HOJA(ARB^.DER) then
        begin
         ARB^.VAL := ARB^.VAL + ARB^.DER^.VAL;
         Dispose(ARB^.DER);
         ARB^.DER := NIL
        end;
      FDIC971(ARB^.IZQ);
      FDIC971(ARB^.DER)
    end
End;
Suponer : Realizadas las declaraciones para un árbol binario cuyos nodos contienen un valor entero.
Definida la función ES_HOJA, booleana, que recibe un puntero a un nodo y devuelve TRUE si el nodo es una hoja y FALSE en cualquier otro caso.
<< SE PIDE >>:
a) Realizar el seguimiento del procedimiento FDIC971 cuando se lo llama con el puntero a la raíz del siguiente árbol binario:
            (1)
           /     \
       (2)      (3)
       /   \     /    \
    (4) (5) (6) (7)
               / 
            (8) 
IMPORTANTE : Mostrar gráficamente cómo se modifica el árbol y en qué momento se produce cada modificación.
Usar la notación FDIC971(^1) para indicar llamado al procedimiento con el puntero al nodo que contiene 1.
b) Sin realizar nuevamente el seguimiento, indicar cómo quedaría el siguiente árbol luego de ejecutar el procedimiento FDIC971 con el puntero a su raíz.
            (15)
           /       \
       (8)       (10)
      /    \      /     \
  (3)    (4)(2)    (5)
               / 
           (13)