Cuestiones Teóricas:

Ejercicio 1. [ Valoración 30 puntos. Respuesta Acertada = +3 Respuesta Incorrecta = -2]

Complete las siguientes frases con las alternativas especificadas. Si existen varias alternativas verdaderas, márquelas todas.

1.1 ¿Cuáles de las siguientes afirmaciones referentes a un registro son ciertas?

(a) Todos los campos de un registro deben ser del mismo tipo.

(b) Sus campos pueden ser de cualquiera tipo de datos, incluido el tipo registro.

(c) En registros variantes, el tipo de datos de la variable selectora ha de ser ordinal.

(d) Los registros variantes no pueden ser devueltos como resultado de una función.

1.2 Un array con dos dimensiones modela

(a) una matriz de longitud variable de elementos homogéneos.

(b) una matriz de longitud fija de elementos homogéneos.

(c) una matriz de longitud variable de elementos heterogéneos.

(d) una matriz de longitud fija de elementos heterogéneos

1.3 Los ficheros binarios

(c) no permiten utilizar con ellos los procedimientos ReadLn y WriteLn

(d) tienen que tener declarado su tamaño al definirlos

1.4 ¿Cuáles de las siguientes afirmaciones referentes a una lista enlazada dinámica son ciertas?

(a) Cada nodo contiene un puntero para poder referenciar a su sucesor

(b) Para añadir un nuevo nodo a la lista, ha de crearse mediante new.

(c) Cada nodo tiene un antecesor, pero puede tener varios sucesores

1.5 ¿Cuál de los siguientes órdenes es correcto (p > 1)?

(a) O(n) " O(n log n) " O(np) " O(en)

(b) O(n log n) " O(n) " O(np) " O(en)

(c) O(n) " O(n log n) " O(en) " O(np)

(d) O(n) " O(np) " O(n log n) " O(en)

1.6 La complejidad en tiempo de la búsqueda secuencial en el peor caso

(a) es cuadrática

(b) es del orden O(log n), siendo n la longitud del vector en el que hay que buscar

(c) no depende de la longitud del vector en el que hay que buscar

Ejercicio 2: 20 puntos

El siguiente programa de Pascal realiza una manipulación de punteros y variables dinámicas. ¿Cuál es el resultado de su ejecución (lo que aparecerá en pantalla)?.

PROGRAM Punteros (input, output);

TYPE

tPunteroNodo = ^tNodo;

tNodo = RECORD

contenido: integer;

izq: tPunteroNodo;

drcha: tPunteroNodo

END; {record}

VAR

uno, dos, tres : tPunteroNodo;

BEGIN

uno := Nil;

dos := Nil;

tres := Nil;

New (uno);

uno^.contenido := 6;

New (uno^.izq);

dos := uno^.izq;

dos^.contenido := uno^.contenido + 12;

New(tres);

uno^.drcha := tres;

dos^.drcha := uno^.drcha;

tres^.izq := dos;

tres^.contenido := uno^.izq^.contenido div 3;

WriteLn (dos^.contenido);

WriteLn (uno^.izq = uno^.drcha);

WriteLn (dos^.drcha^.contenido);

WriteLn (tres^.contenido = uno^.contenido);

WriteLn (dos = uno^.drcha^.izq);

END.

Razona tu respuesta dibujando un esquema.

Ejercicio 3 25 puntos

El siguiente procedimiento Pascal es una variación del algoritmo de inserción directa. Aprovecha el hecho de que dicho algoritmo construya un subvector inicial ordenado, y usa la búsqueda binaria para determinar el índice del vector, en el que hay que insertar un nuevo elemento:

CONST M=1000; {máximo valor clave}

N=5; {número de claves en la secuencia a ordenar}

TYPE tValor = 1..M;

tIndice = 1..N;

tVector = array[tIndice] of tValor;

PROCEDURE escribirVector(v:tVector);

VAR i:tIndice;

BEGIN

write('v = [');

FOR i:=1 TO N DO

write(v[i]:3);

writeln(' ]');

END; {escribir Vector}

PROCEDURE insercionBinaria(VAR v:tVector);

VAR extSup, {extremo superior}

extInf, {extremo inferior}

indMed, {índice medio}

i,j: integer;

aux: tValor;

BEGIN

FOR i:= 2 TO N DO BEGIN

{Invariante: v[1..i-1] está ordenado}

aux := v[i];

{usar busqueda binaria para encontrar la posición correcta}

{del elemento actual "aux" en v[1..i-1] }

extInf := 1;

extSup := i-1;

WHILE extInf <= extSup DO BEGIN

indMed := (ExtSup+ExtInf) div 2;

IF aux < v[indMed] THEN

extSup := indMed-1 {descartar parte drcha}

ELSE

extInf := indMed+1; {descartar parte izq.}

END; {WHILE}

{insertar el elemento actual "aux"}

FOR j:= i-1 DOWNTO extInf DO

v[j+1] := v[j];

v[extInf] := aux;

escribirVector(v);

END {FOR}

END; {insercionBinaria}

Suponga los valores que siguen del vector v:

4.1 ¿Cuál es el valor de v después de la llamada insercionBinaria(v) en los casos (a), (b), y (c)?

4.2 Para cada una de los casos (a), (b), y (c), ponga las líneas que escriba la llamada insercionBinaria(v) en pantalla.

4.3 ¿Cuál es la complejidad asintótica en espacio en el peor caso del algoritmo arriba mencionado? Justifique brevemente su resultado.

Ejercicio 4 25 puntos

Supóngase que disponemos de una serie de sensores (no se sabe de antemano cuántos), y que cada uno de dichos sensores proporciona una secuencia de M valores enteros entre 1 y 1000 (M es constante). Para cada sensor, estas mediciones se representan mediante un array de M componentes. Se utiliza una lista dinámica enlazada para almacenar los arrays de mediciones de cada uno de los sensores. En Pascal, la siguiente declaración de tipos expresa esta idea:

CONST M=5;

MaxValor = 1000;

MinValor = 1;

TYPE tValor = MinValor..MaxValor;

tNoSensor = 1..M;

tSensor = array[tNoSensor] of tValor;

tListaSensores = ^tNodo;

tNodo = record

sensor: tSensor;

siguiente: tListaSensores;

end; {record}

Escriba una función MaxiMinSensores que, a partir de un elemento del tipo tListaSensores devuelva el máximo de los valores mínimos de cada sensor. Con tal fin, se recomienda escribir una función auxiliar minSensor que devuelva el valor mínimo de un array del tipo tSensor.

Ejemplo para 3 sensores y M=5 mediciones por sensor:

Sensor 1: 8 7 2 6 5 Sensor 2: 5 4 5 7 1 Sensor 3: 9 6 11 1 4

MaxiMinSensores: 2

BORRADOR

Metodología y Tecnología de la Programación

Segundo parcial

9 de Septiembre de 1999

APELLIDOS: NOMBRE:

ESPECIALIDAD: TURNO:

Duración: 1 h. 30 m.