Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1101
I Semestre 1996
[<=] [home] [<>] [\/] [=>]
CI-1101 Programación I

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.  Conteste solo 4 de las preguntas  del 
examen. Puede hacer el examen con lápiz. ¡No haga más de lo que se le pide!

1)_[25_pts]_Considere la estructura de datos  compuesta de  objetos del  tipo 
TNode.
                          TYPE                      VAR
        +------+-----+      TNode = RECORD            p,q : ^TNode;
        | _val | _pN |        _val : STRING[3];
        +------+-----+        _pN  : ^TNode;
        | _qB |  _xP |        _qB  : ^TNode;
        +-----+------+        _xP  : ^TNode
                            END; { TNode }


1.a)_[10_pts]_Haga un diagrama que muestre el resultado de ejecutar cada  una 
de  las  siguentes  operaciones,  en  secuencia.   Como  hay  10 operaciones, 
numeradas desde {1} hasta {10}, usted  debe dibujar  diez diagramas.   En sus 
dibujos deje en blanco aquellos campos que todavía no están inicializados.

    {1}  NEW(p);                   {6}  p^._pN       :=  q^._pN;
    {2}  NEW(p^._pN);              {7}  p^._pN^._qB  :=  p;
    {3}  NEW(p^._pN^._pN);         {8}  q^._xP       :=  q^._pN^._qB;
    {4}  q      :=  p^._pN;        {9}  q^._xP^._qB^._val := 1;
    {5}  p^._qB := q;             {10}  p^._qB^._pN^._val := 2;

1.b)_[10_pts]_En el diagrama siguiente, suponga que  los punteros  "p" y  "q" 
apuntan a los nodos [B] y [C] respectivamente.  Escriba el código Pascal para 
eliminar al segundo nodo, pero corriga los punteros  que están  en los  otros 
nodos de forma que todos los campos "_qB" y "_xP" que apunten al segundo nodo 
pasen a apuntar al nodo [A], y que los punteros  "_pN" apunten  al nodo  [C].  
Como variables de trabajo sólo puede usar a "p" y "q".

          ┌────────────────────────────────────────────┐
          │  ┌────────────────────────────────────────┐│ ┌────┐ ┌────┐
          v  v                                        ││ │    v v    │
       ┌─────┬─┐        ┌─────┬─┐           ┌─────┬─┐ ││ │ ┌─────┬─┐ │
       │ [A] │├┼───────>│ [B] │├┼──────────>│ [C] │├┼─┘│ │ │ [D] │├┼─┘
    ┌─>├───┬─┴─┤     ┌─>├───┬─┴─┤           ├───┬─┴─┤  │ │ ├───┬─┴─┤
    │  │ ┬ │ ┬ │     │  │ ┬ │ ┬ │<─┐    ┌──>│ ┬ │ ┬ │  │ │ │ ┬ │NIL│
    │  └─┼─┴─┼─┘     │  └─┼─┴─┼─┘  │    │   └─┼─┴─┼─┘  │ │ └─┼─┴───┘
    │    │   └───────┘    │   │    └────┼─────┘   └────┘ └───┘   ^
    │    └────────────────┼───┼─────────┘                        │
    └─────────────────────┘   └──────────────────────────────────┘

1.c)_[5_pts]_Use sólo 4 instrucciones para destruir toda la  cadena de  nodos 
que se muestra en el diagrama del punto anterior.  Suponga que el puntero "p" 
apunta al nodo [C], y que "q" es NIL.


[Versión Java de la pregunta]

   +-------+------+       class TNode {
   | m_val | m_pN |           String m_val;
   +-------+------+           TNode  m_pN;
   | m_qB  | m_xP |           TNode  m_qB;
   +-------+------+           TNode  m_xP;
                          }
                          TNode p, q;

1.a)_[10_pts]_Haga un diagrama que muestre  el resultado de ejecutar cada  una 
de  las  siguentes  operaciones,  en  secuencia.   Como  hay  10  operaciones, 
numeradas  desde {1}  hasta {10}, usted  debe dibujar diez  diagramas.  En sus 
dibujos deje en blanco aquellos campos que todavía no están inicializados.

    {1}  p = new TNode();           {6}  p.m_pN      =  q.m_pN;
    {2}  p.m_pN = new TNode();      {7}  p.m_pN.m_qB =  p;
    {3}  p.m_pN.m_pN = new TNode(); {8}  q.m_xP      =  q.m_pN.m_qB;
    {4}  q      =  p.m_pN;          {9}  q.m_xP.m_qB.m_val = "1";
    {5}  p.m_qB = q;               {10}  p.m_qB.m_pN.m_val = "2";

1.b)_[10_pts]_En el  diagrama siguiente,  suponga que  los objetos  "p" y  "q" 
apuntan a los nodos [B] y [C] respectivamente.  Escriba el código Pascal  para 
eliminar al segundo nodo,  pero corriga  los objetos  que están  en los  otros 
nodos de forma que todos los campos "m_qB" y "m_xP" que referencien al segundo 
nodo pasen a referenciar al nodo [A], y que los objetos "m_pN" referencien  al 
nodo [C]. Como variables de trabajo sólo puede usar a "p" y "q".

          +--------------------------------------------+ +----+ +----+
          |  +----------------------------------------+| |    | |    |
          v  v                                        || |    v v    |
       +-------+        +-------+           +-------+ || | +-------+ |
       | [A] |*+------->| [B] |*+---------->| [C] |*+-+| | | [D] |*+-+
    +->|-----+-|     +->|-----+-|           |-----+-|  | | |-----+-|
    |  | * | * |     |  | * | * |<-+    +-->| * | * |  | | | * |NIL|
    |  +-|-+-|-+     |  +-|-+-|-+  |    |   +-|-+-|-+  | | +-|-+---+
    |    |   |       |    |   |    |    |     |   |    | |   |   ^
    |    |   |       |    |   |    +----+-----+   |    | |   |  /|\
    |    |   +-------+    |   |         |         +----+ +---+   |
    |    +----------------+---+---------+                        |
    |                     |   |                                  |
    +---------------------+   +----------------------------------+

1.c)_[5_pts]_Use sólo 4 instrucciones para destruir toda la  cadena de  nodos 
que se muestra en el diagrama del punto anterior.  Suponga que el objeto  "p" 
referencia el nodo [C], y que "q" es null.


2)_[25_pts]_Considere la siguiente estructura de datos, en la que "p"  apunta 
al nodo [A].
                          TYPE                      VAR
        +------+-----+      TNode = RECORD            p,q : ^TNode;
        | _val | _pN |        _val : STRING[3];
        +------+-----+        _pN  : ^TNode;
        | _qB |  _xP |        _qB  : ^TNode;
        +-----+------+        _xP  : ^TNode
                            END; { TNode }



          ┌────────────────────────────────────────────┐
          │  ┌────────────────────────────────────────┐│ ┌────┐ ┌────┐
          v  v                                        ││ │    v v    │
       ┌─────┬─┐        ┌─────┬─┐           ┌─────┬─┐ ││ │ ┌─────┬─┐ │
  p───>│ [A] │├┼───────>│ [B] │├┼──────────>│ [C] │├┼─┘│ │ │ [D] │├┼─┘
    ┌─>├───┬─┴─┤     ┌─>├───┬─┴─┤           ├───┬─┴─┤  │ │ ├───┬─┴─┤
    │  │ ┬ │ ┬ │     │  │ ┬ │ ┬ │<─┐    ┌──>│ ┬ │ ┬ │  │ │ │ ┬ │NIL│
    │  └─┼─┴─┼─┘     │  └─┼─┴─┼─┘  │    │   └─┼─┴─┼─┘  │ │ └─┼─┴───┘
    │    │   └───────┘    │   │    └────┼─────┘   └────┘ └───┘   ^
    │    └────────────────┼───┼─────────┘                        │
    └─────────────────────┘   └──────────────────────────────────┘

Ahora estudie la implementación de los procedimientos RWR(), RRW() y BOO().

PROCEDURE RWR(              PROCEDURE RRW(              PROCEDURE BOO(
  p : ^TNode                  p : ^TNode                  p : ^TNode
);                          );                          );
BEGIN                       BEGIN                       BEGIN
  IF p = NIL THEN BEGIN       IF p = NIL THEN BEGIN       IF p = NIL THEN
    EXIT;                       EXIT;                       EXIT;
  END;                        END;                        END;

  RWR(p^._xP);                RRW(p^._xP);                RWR(p^._pN);
  WriteLn(p^._val);           RRW(p^._pN);                RRW(p^._qB);
  RWR(p^._qB);                WriteLn(p^._val);           WriteLn(p^._val);
END;  { RWR }               END;  { RRW }               END;  { BOO }


2.a)_[5_pts]_Diga qué imprime la invocación RWR(p).  Explique este resultado. 
¿Es este programa correcto?

2.b)_[5_pts]_Diga qué imprime la invocación RRW(p).  Explique este resultado. 
¿Es este programa correcto?

2.c)_[5_pts]_Diga qué imprime la invocación BOO(p).  Explique este resultado. 
¿Es este programa correcto?

2.d)_[10_pts]_Implemente al procedimiento recursivo  Destruye(p,q:^TNode) que 
elimina a toda la cadena si se le invoca con un puntero al nodo [B], y con un 
valor de "q=NIL": Destruye(@B, NIL).





3)_[25_pts]_El tipo  TRebote ha  sido creado  para que  dentro de  una matriz 
rectangular [n*m] uno de sus elementos recorra en diagonal las entradas, pero 
rebotando cuando  se  alcanza  alguna  de  las  paredes,  como  se muestra  a 
continuación:

     +-------------+     TYPE
     |   /\      /\|       TMatriz = OBJECT
     |  /3 \    / /|         _val  : ARRAY[1..DIM, 1..DIM] OF CHAR;
     | /2   \  / / |         _n,_m : [1..DIM]; { dimensiones actuales }
     |/1     \/ /n |       END;
     +-------------+

     TYPE
       TRebote = OBJECT
         _x, _y : WORD;
         _dir   : (NO {'\}, SO {./}, NE {/'}, SE {\.});
         ...
         PROCEDURE Step( VAR M: TMatriz; VAR x,y: WORD; VAR ch: CHAR);
       END; { TRebote }

3.a)_[5_pts]_Explique para qué sirve cada uno de los campos de TRebote.

3.b)_[5_pts]_Haga la  especificación de  TRebote.Step(). Tome  en cuenta  que 
     antes de terminar TRebote.Step() siempre ejecuta la instrucción:
        M._val[x,y] := ch;
     Suponga que en cada invocación TRebote.Step() avanza un paso nada más.

3.c)_[15_pts]_Implemente TRebote.Step(). [Step(Inglés)=Paso(Español)]



4)_[25_pts]_La biblioteca estándar del lenguaje C  contiene varias  funciones 
para manipular hileras, y una muy utilizada es strtok().  Implemente usted la 
función StrTok() en Pascal.

    FUNCTION StrTok(
      {?} VAR s: STRING
    ) {>>>>>>>}: STRING;  { primera palabra de "s" }
    { RESULTADO
      Extrae la primera palabra de la hilera "s", y la retorna
      como valor de la función.
      - En "s" queda el resto de la hilera, después del último
        caracter de la palabra extraída.
      - Ignora los blancos al principio de "s".
      - Una palabra es una secuencia de uno o más caracteres
        consecutivos pero todos diferentes de blanco. }
    { EJEMPLO
      "s" Antes             Retorna      "s" Después
      -----------------     -------      -----------
      '  esta hilera. '     'esta'       ' hilera. '
      ' -   +  '            '-'          '   +  '
      '        '            ''           ''
      ' .!.    algo!!!'     '.!.'        '    algo!!!'  }


5)_[25_pts]_El  tipo  TVectorSube sirve  para manipular  vectores de  números 
reales de longitud variable. Por ejemplo, si el vector ya tiene 10 elementos, 
y se agrega mediante  TVectorSube.Put(v,15) al  elemento número  15, entonces 
automáticamente el vector cambia de tamaño  para acomodar  cinco valores  más 
(11,12,13,14 15). En este caso, el valor del campo "_n" pasa de 10 a 15, pues 
"_n" indica cuántos valores tiene el vector en cada momento.

CONST
  MxVec = 500;   { Capacidad máxima de un TVectorSube }
TYPE
  TVectorSube = OBJECT
    PRIVATE
      _v : ARRAY [1..MxVec] OF REAL;
      _n : WORD; { dimensión (o tamaño) actual del vector [0..MxVec] }

    PUBLIC
      PROCEDURE Init;                    { constructor }
      PROCEDURE Done;                    { destructor  }

      PROCEDURE SetDim(n: WORD);         { le cambia el tamaño al vector }
      FUNCTION  Val(i: WORD)  : REAL;    { retorna vec[i] }
      PROCEDURE Put(i: WORD; v: REAL);   { cambia  vec[i] := v }

      PROCEDURE Intercale(VAR V: TVectorSube); { intercala los valores de V }
  END; { TVectorSube }

5.a)_[7_pts]_Especifique TVectorSube.Intercale(V)  que toma  los valores  que 
están en orden ASCENDENTE en el vector "V" y los agrega a SELF, cuyos valores 
también están ordenados ASCENDENTEMENTE. Note que si no hay campo  para meter 
a todos los valores, quedan en SELF sólo  los más  pequeños, que  aparecen de 
primeros en SELF y V. Incluya en su especificación un ejemplo.

5.b)_[18_pts]_Implemente  TVectorSube.Intercale().    En  su   implementación 
asegúrese de no usar un vector adicional para almacenar valores.




6)_[25_pts]_Una chiquita recibe el encargo de  su maestra  de escribir  todos 
los números desde el 1 hasta el 1,000,000.   Ella, muy  hacendosa, empieza  a 
escribir uno por uno, pero cuando lleva escritos 630 dígitos se cansa y para.

6.a)_[7_pts]_Calcule el número en que la niña ha parado.

6.b)_[18_pts]_Escriba un programa que reciba como entrada un número "n" en el 
rango [0..9,999], y que como salida imprima el  número por  el que  la niñita 
iría si para a descansar después de escribir exactamente "n" dígitos.

 

Soluciones

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1996
Derechos de autor reservados © 1996
[home] <> [/\]