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

Programación II

Examen Final

Marzo de 2000 Altillo.com

1. Dado un Árbol Binario de Búsqueda no vacío cuyos nodos contienen números enteros NO REPETIDOS y un valor que EXISTE en el árbol.
Se pide:
a) Definir la estructura en Pascal (parte declarativa: CONST, TYPE y VAR).
b) Desarrollar un procedimiento recursivo con los parámetros necesarios y suficientes, que devuelva el nivel del nodo del valor dado y un valor booleano en TRUE si posee un hijo izquierdo que coincide con su inmediato menor y FALSE en caso contrario.
c) Escribir las instrucciones necesarias para la llamada al procedimiento desarrollado en b), indicando claramente qué parámetros utiliza y sus valores.
Ejemplo:
                (80)
                /     \
           (50)     (100)
           /     \     /      \
      (20) (70) (90)  (200)
             /       /        /      \
        (60) (85)   (150) (300)
                                         \
                                        (400)

Si Valor dado = 80   ---> ANTERIOR = 70 Devuelve Nivel = 0 y FALSE
Si Valor dado = 70   ---> ANTERIOR = 60 Devuelve Nivel = 2 y TRUE
Si Valor dado = 200 ---> ANTERIOR = 150 Devuelve Nivel = 2 y TRUE
Si Valor dado = 85   ---> ANTERIOR = 80 Devuelve Nivel = 3 y FALSE
Si Valor dado = 100 ---> ANTERIOR = 90 Devuelve Nivel = 1 y TRUE

2. Dadas las siguientes declaraciones y el procedimiento Mzo2000:
Type
    TyInfo = integer;
    TyPunArb = ^TyNodoArb;
    TyNodoArb = record
                                INFO : TyInfo;
                                IZQ,DER : TyPunArb
                           end;
Var
    RAIZ : TyPunArb;
procedure Mzo2000 (var P : TyPunArb; M : integer);
    begin
        if P <> NIL then
            Begin
                if (P^.IZQ = P^.DER) and (P^.INFO mod M = 0) then
                    begin
                        dispose(P);
                        P := nil
                    end
                else
                    begin
                        Mzo2000 (P^.IZQ, M);
                        Mzo2000 (P^.DER, M)
                    end
            end;
end;

Se pide:
a) Realizar su seguimiento indicando claramente el contenido y actualización de las variables, graficando las modificaciones del árbol, cuando se realiza la siguiente secuencia de invocación : Mzo2000 (RAIZ, 2)
para el siguiente árbol:
RAIZ ---> (80)
                 /     \
           (50)      (100)
           /     \      /
     (20)   (75) (90)

b) Sin realizar otro seguimiento graficar cómo quedaría el árbol si se tomase el del ejemplo del punto 1, para la misma invocación al procedimiento.