Examen Final [solución]

      Duración: tres horas. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Cuentan las convenciones. Puede hacer el examen con lápiz. ¡No haga más de lo que se le pide! ¡Conteste TODAS las 4 preguntas!

1) [25 pts] Considere el objeto Arbol Binario Ordenado, que sirve para representar multi-conjuntos ordenados, esto esto es, conjuntos en que un mismo elemento aparece más de una vez. En el multi-conjunto [1, 1, 2, 3] el valor "1" está dos veces, y la cantidad de elementos almacenados es cuatro. Una forma de implementar el multi-conjunto es usar el tipo TOrdBinTree definido de la siguiente forma:

TYPE                            TYPE
  TNode = OBJECT                  TOrdBinTree = OBJECT
    _val   : LONGINT;               _root    : ^TNode; { raíz }
                                    ...
    _left,                          PROCEDURE Insert (l:LONGINT);
    _right : ^TNode;                PROCEDURE Print;
  END;                            END; { TOrdBinTree }

      Implemente el método TOrdBinTree.Insert() de forma que sea posible insertar valores repetidos en el árbol. Cuando un valor ya aparezca en el árbol, inserte el nuevo duplicado como hijo DERECHO del valor original; no lo inserte como hijo izquierdo.

[NOTA: La operación TOrdBinTree.Insert(l) es ESTABLE si siempre que un nodo es insertado en el árbol ANTES que otro, entonces siempre ocurrirá que su valor será impreso primero por TOrdBinTree.Print(). Recuerde que el método TOrdBinTree.Print() lo que hace es recorrer el árbol en IPD [PreOrden], para imprimir los valores del árbol en orden. Su método Insert() es estable.]

2) [25 pts] Existen mucho algoritmos que funcionan mejor si se aplican a matrices cuadradas que se tienen sus valores por bandas. Estas son algunas de esas matrices:

                1 2 3 0 0 0                 1 2 3 0 0
 1  2  0  0     0 2 3 0 0 0      1 0 0      2 1 2 3 0
-2  1  2  0     0 4 1 0 0 0      0 1 0      0 2 1 2 3
 0 -2  1  2     0 0 5 1 0 0      0 0 1      0 0 2 1 2
 0  0 -2  1     0 0 0 0 1 0                 0 0 0 2 1
                0 0 0 0 3 9

      La primera es una matriz 4x4 que tiene una banda de 2 sub-diagonales de ancho. La primera sub-diagonal es la diagonal de la matriz (que tiene valores "1"), y la segunda es la que está inmediatamente arriba de la diagonal (formada de los valores "2"). Como segunda sub-diagonal también se cuenta a la que está debajo de la diagonal principal (formada de los valores "-2").

      La cuarta matriz es una matriz de dimensión 5x5, y su caso es un poco diferente, pues es una matriz que tiene bandas de ancho 3. Aunque su última sub- diagonal hacia abajo es la formada por los doces ("2"), tiene una tercera sub-diagonal hacia arriba formada por los valores "3". Por eso su ancho de banda es "3" (y NO es "2").

      El ancho de banda de la matriz identidad es "1", porque sólo tiene valores diferentes de cero en la diagonal. Una matriz llena de ceros tendrá ancho de banda "0".

2.a) [5 pts] Escriba la definición de tipos para el objeto TMatriz, e incluya al método Ancho_Banda(): WORD. Haga las cosas de forma que la dimensión de su matriz puede variar en el rango [1..MxDim].

2.b) [5 pts] Especifique el método FUNCTION TMatriz.Ancho_Banda: WORD, que retorna el tamaño de la banda más ancha de la matriz. Note que en el caso peor Ancho_Banda() retornará "n", la dimensión de la matriz, que ocurre cuando la matriz no contiene un triángulo inferior y otro superior lleno de ceros ("0"). [Sugerencia: Calcule el tamaño del triángulo de ceros inferior y superior de la matriz].

2.c) [15 pts] Implemente TMatriz.Ancho_Banda().

3) [25 pts] 3)_[25_pts]_Programe la rutina que se especifica a continuación.

  PROCEDURE Reverse_Merge(
    {?} VAR A   : Integer_ARRAY; { Arreglo a mezclar }
    {+} l,mid,h : WORD;          { rangos dentro de A[] }
    {?} VAR tmp : Integer_ARRAY  { area temporal para mezclar }
  );
  { RESULTADO
    Intercala los dos sub-arreglos ordenados A[l..mid] y
    A[mid+1..h].
    - A[] queda ordenado descendentemente.
    - A[l..mid] está ordenado ascendentemente.
    - A[mid+1..h] está ordenado ascendentemente.
    - Para hacer la intercalación usa el arreglo temporal
      "tmp" como área de trabajo.
    - El esfuerzo usado es O(h-l). }

      NO implemente este proceso reordenando los números: haga la intercalación de los dos sub-arreglos. Note que al final los valores de A[] quedan ordenados DESCENDENTEMENTE.

4) [25 pts] Considere la siguiente función, que ha sido pasada por el Triturador Anti-Pascal:

                                 function 
    laca                         (loca: integer) 
                                 : longint;  const
    luca = ((234*322-976 div 12) * 8 - 34) * (15 - 14 - 2 + 1);
    leca = ((234*322-976 div 12) * 8 - 34) * luca;
    lica = ((234*322-976 div 12) * 8 - 34) * leca;
  begin if                       loca <= 
     lica                        then begin laca  
  := luca                        ;;;;;;;;;;;;;;;  ;;;;;;;;;;;;;;;
  ; end else                     begin laca := 
  laca                           (loca-1)+loca    ;;;;;;;;;;;;;;;
  ;end end;

4.a) [5 pts] Reescriba esta función de acuerdo a las Convenciones de Programación de Adolfo Di Mare.

4.b) [5 pts] Haga un ejemplo del resultado de ejecutar esta función con el valor 4.

4.c) [5 pts] Sugiera nombres mejores para cada una de los identificadores de la función.

4.d) [5 pts] Haga la especificación de esta función.

4.e) [5 pts] Implemente de nuevo esta función, pero use un algoritmo más simple.

{ SUMA.pas        adolfo@di-mare.com    (c) NOV-1996 }

PROGRAM Suma;

FUNCTION Sumadora(n: INTEGER) : LONGINT;
{ RESULTADO
  Calcula la sumatoria de los primeros "n"
  números.
  - Es una pregunta de examen, por lo que la
    sumatoria se calcula usando un algoritmo
    recursivo. }
BEGIN { Sumadora }
  IF n <= 0 THEN BEGIN
    Sumadora := 0;
  END
  ELSE BEGIN
    Sumadora := Sumadora(n-1)+n;
  END;
END;  { Sumadora }
                                 function
    laca                         (loca: integer)
                                 : longint;  const
    luca = ((234*322-976 div 12) * 8 - 34) * (15 - 14 - 2 + 1);
    leca = ((234*322-976 div 12) * 8 - 34) * luca;
    lica = ((234*322-976 div 12) * 8 - 34) * leca;
  begin if                       loca <=
     lica                        then begin laca
  := luca                        ;;;;;;;;;;;;;;;  ;;;;;;;;;;;;;;;
  ; end else                     begin laca :=
  laca                           (loca-1)+loca    ;;;;;;;;;;;;;;;
  ;end end;
                                 function
    trambalaca                   (tramblaca: integer)
                                 : longint;  const
    trambalacaca = ((234*322-976 div 12) * 8 - 34) * (15 - 14 - 2 + 1);
    trambelacaca = ((234*322-976 div 12) * 8 - 34) * trambalacaca;
    trambilacaca = ((234*322-976 div 12) * 8 - 34) * trambelacaca;
  begin if                       tramblaca <=
     trambilacaca                then begin trambalaca
  := trambalacaca
  ; end else                     begin trambalaca :=
  trambalaca                     (tramblaca-1)+tramblaca
  ;end end;

VAR
  i : WORD;
BEGIN { Suma }
  WriteLn; WriteLn;
  FOR i := 0 TO 20 DO BEGIN
    IF Sumadora(i) <> laca(i)THEN BEGIN
      WriteLn('****  ', i:1);
    END;
    WriteLn('  i = ', i:2, ' ==> ', Sumadora(i):4, ' = ', laca(i):4);
  END;
END.  { Suma }

{ SUMA.pas: EOF }

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1996
Derechos de autor reservados © 1996