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

Lista enlazada dinámica. Ficheros binarios. Régistros. Punteros. Variables dinámicas. Pascal. Vectores. Algoritmos. Arrays

  • Enviado por: Alejandro
  • Idioma: castellano
  • País: España España
  • 9 páginas
publicidad
publicidad

Ejercicio 1

Ejercicio 2

Ejercicio 3

Ejercicio 4

TOTAL

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

  • tienen componentes que se almacenan en la representación interna de la máquina

  • están divididos en líneas, separadas por símbolos de “fin de línea” (EOLn)

  • (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

  • Cada nodo, salvo el primero, puede tener varios antecesores..

  • 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

  • es lineal

  • 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:

  • v = (8 6 5 3 1)

  • v = (1 3 5 6 8)

  • v = (8 1 5 3 6)

  • 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

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

    APELLIDOS: NOMBRE:

    ESPECIALIDAD: TURNO:

    Duración: 1 h. 30 m.