CI-1101 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1101
II Semestre 1997

$[\/]$

CI-1101 Programación I

Examen #2 [solución]

     Duración: dos horas. Lea bien el examen antes de hacerlo.  Puede hacer 
el examen con lápiz. El examen es a libro abierto.

1) [33 pts] Considere el tipo TMatriz, que sirve para  almacenar en  memora 
dinámica un matriz N*M:

     TYPE                    CONST
       TMatriz = OBJECT        MxSize = 2500;
         _v : PVector;
         _n : WORD;         TYPE
         _m : WORD;           TVector = ARRAY [0..MxSize-1] OF REAL;
         _FC: BOOLEAN;        PVector = ^TVector;
         ....
      END;

El campo _FC indica si la matriz está almacenada por filas o por columnas:
     /     \
     | 1 2 |  _v^[0.._n*_m-1] = [1 2 3 4 5 6 7 8] ==> Por filas
     | 3 4 |
     | 5 6 |
     | 7 8 |  _v^[0.._n*_m-1] = [1 3 5 7 2 4 6 8] ==> Por columnas
     \     /

1.a) [7 pts] Implemente el método  TMatriz.F() que  calcula posición  de la 
     entrada (i,j) en el vector "_v^[]"  si la  matriz está  almacenada por 
     filas.

1.b) [7 pts] Implemente el método TMatriz.C() que calcula la posición de la 
     entrada (i,j) en el vector "_v^[]"  si la  matriz está  almacenada por 
     columnas.

1.c) [14 pts] Implemente el método TMatriz.Vuelta(FC:BOOLEAN) que cambia la 
     forma de almacenamiento de la matriz de filas por columnas  a columnas 
     por filas, y viceversa.

1.d) [5  pts]  Implemente  el  método  TMatriz.Vuelta(FC:BOOLEAN),  pero no 
     utilice un arreglo adicional para cambiar  la forma  de almacenamiento 
     de filas por columnas a columnas por filas, y viceversa.


2)  [33  pts]  Escriba  las definición  de tipos  necesarias para  que este 
procedimiento pueda ser parte de la implementación del objeto TQueue.
- No defina ninguna variable global.

  PROCEDURE TQueue.EnQueue(
    {+} VAR e : REAL         { e se inserta al final }
  );
  VAR
    donde : INTEGER;
  BEGIN { EnQueue }
    IF disp = 0 THEN BEGIN
      WriteLn('Cola llena'); EXIT;
    END
    ELSE BEGIN
      donde  := disp;
      disp   := nodos[donde].next;

      nodos[donde].data := e;
      nodos[donde].next := atras;
      atras := donde;
    END;
  END; { EnQueue }


3) [33 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.

Soluciones

$[/\]$