Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
|
|
CI-1101 Programación I
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:]](../../../img/mailbox.gif)
Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1996
Derechos de autor reservados © 1996
![[<=]](../../../img/back.gif)
![[home]](../../../img/home.gif)
![[<>]](../../../img/index.gif)
![[\/]](../../../img/bottom.gif)
![[=>]](../../../img/next.gif)
![[/\]](../../../img/top.gif)