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

1. Dado un Árbol Binario de Búsqueda no vacío cuyos nodos contienen los nombres de los Sectores de una empresa, los punteros izquierdo y derecho a sus sucesores y dos punteros a su lista de Empleados, uno al primero en orden alfabético y el otro al empleado Jefe del Sector.
Cada lista de empleados está ordenada alfabéticamente y sus nodos contienen: Apellido y nombre del empleado y un puntero a su siguiente nodo de empleado.

TYPE
    Ty_Punt = ^Ty_Nodo ;
    Ty_Nodo = Record
                            ApeyNom : string[40]
                            Sig : Ty_Punt
                       End;
    Ty_PunArb = ^Ty_NodArb ;
    Ty_NodArb = Record
                                Sector : string[20];
                                Izq, Der : Ty_PunArb;
                                . . . : . . . 
                                . . . : . . . 
                            End;
Var
    Empre : Ty_PunArb;

Se pide:
a) Completar la declaración de la estructura en Pascal (parte declarativa: CONST, TYPE y VAR).
b) Desarrollar un procedimiento recursivo con los parámetros necesarios y suficientes, que dada la estructura, genere otro árbol binario de búsqueda donde cada nodo contenga:
· NomSector : string[20] Nombre del sector
· ApeyNomJefe : string[40] Nombre del jefe del sector
· CantEmpleSector : Integer Cantidad de empleados del sector
· Puntero izquierdo y derecho del árbol
c) Escribir las instrucciones necesarias para la llamada al procedimiento desarrollado en b), indicando claramente qué parámetros utiliza y sus valores. 
NOTA: Los procedimientos o funciones auxiliares que se utilicen podrán desarrollarse en forma recursiva o iterativa a criterio del alumno.

Ejemplo:
Dado

Podría generar un árbol como el siguiente:

2. Dadas las siguientes declaraciones y el procedimiento ASEGUIR:
type
    TyPunArb = ^TyNodoArb;
    TyNodoArb = record
                                INFO : integer;
                                IZQ,DER : TyPunArb
                           end;
var
    R : TyPunArb; (* Puntero al nodo Raiz *)
    VALOR : integer;
    CONT : integer;
    SISI : boolean;

procedure ASEGUIR( P:TyPunArb; DATO:integer; var ES:boolean; var NN:integer) ;

procedure RECUB (P:TyPunArb; DATO:integer; var ES:boolean; var QQ:integer);
Begin (* RECUB *)
    if DATO < P^.INFO then
        Begin
            QQ := QQ + 1 ;
            RECUB(P^.IZQ, DATO, ES, QQ)
        End
    else
        if DATO > P^.INFO then
            Begin
                QQ := QQ + 1 ;
                RECUB(P^.DER, DATO, ES, QQ)
            End
        else
            if P^.DER = NIL then
                ES := False
            else
                if P^.DER^.IZQ = NIL then
                    ES := True
                else
                    ES := False
End; (* RECUB *)

Begin (* ASEGUIR *)
    NN := 0;
    RECUB(P, DATO, ES, NN);
    writeln( ES, ' ', NN)
END; (* ASEGUIR *)

Y considerando el árbol :
            (80)
           /      \
     (50)        (100)
    /      \        /      \
(20) (70) (90) (200)
       /        /     /        \
   (60)  (85) (150)  (300)
                                    \
                                    (400)
Se pide:
a) Realizar su seguimiento indicando claramente el contenido y actualización de las variables y qué se emite por pantalla, cuando se realiza la siguiente secuencia de invocación:
VALOR := 200;
SISI := FALSE;
CONT := 88;
ASEGUIR( RAIZ, VALOR, SISI, CONT) ;
b) Sin realizar otro seguimiento indicar qué se emite por pantalla, cuando se realiza la siguiente secuencia de invocación:
VALOR := 70;
SISI := TRUE;
CONT := 88;
ASEGUIR( RAIZ, VALOR, SISI, CONT) ;

3. Sean los siguientes recorridos de un Árbol Binario:
PREORDEN : 33 22 11 44 55 66
INORDEN :    11 22 33 44 55 66
Se pide:
a) Dibujar el árbol
b) Decir si es Árbol Binario de Búsqueda. JUSTIFICAR.