Centro Asociado de Asturias
CABUEÑES –GIJÓN
|
Centro Asociado de Asturias CABUEÑES –GIJÓN |
|
Febrero 1995 (2ª Semana) |
1.- El programa siguiente muestra el procedimiento en Modula-2 correspondiente a un método de clasificación directa de arreglos.
a) Deducir cuál de ellos es (inserción, selección o intercambio), explicando detalladamente el mecanismo. Utilizar para ello el siguiente arreglo inicial.
|
46 |
57 |
14 |
44 |
96 |
20 |
8 |
70 |
b) Realizar el análisis del programa, calculando el número de comparaciones y movimientos en el mejor y peor caso, así como el promedio.
PROCEDURE incógnita;
VAR I,j : INTEGER;
BEGIN
FOR i:=2 TO n DO
a[0]:=a[I];j:=I;
WHILE a[0]<a[j-1] DO a[j]:=a[j-1];j:=j-1;
END
a[j]:=a[0];
END;
END incognita.
Fórmulas: 
, 
2.- Explicar detalladamente el método de clasificación por montón describiendo la definición de montón de Williams, la manera de construir un monton “in situ” de Floyd y el algoritmo de clasificación. Usar para ello el siguiente arreglo inicial:
|
44 |
55 |
12 |
42 |
94 |
18 |
6 |
67 |
Completar el programa siguiente (en Modula-2) para que realice el desplazamiento de Floyd de un montón.
PROCEDURE sift(L,R : index);
VAR i,j : index;
x : item;
BEGIN
i:=L;j:=2*L;x:=a[L];
IF (j<R)& … THEN j:=j+1
END;
WHILE (j<=R)& … . DO
… ; I:=j ; …;
IF (j<R) & … THEN j:=j+1
END;
END;
END sift.
3.- Definir un árbol perfectamente balanceado. Programar un procedimiento en Modula-2 que construya un árbol perfectamente balanceado con n nodos y llave números enteros. Explicar detalladamente cómo se construye un árbol siguiendo las instrucciones del algoritmo. Ilustrarlo construyendo un árbol para la siguiente secuencia:
|
8 |
9 |
11 |
15 |
19 |
20 |
21 |
1 |
7 |
4.- Establecer las definiciones de las estructuras más adecuadas para implementar una secuencia FIFO mediante asignación dinámica. Implementar en Modula-2 los procedimientos meter( ) y sacar( ) que se definen sobre dicha estructura. Explicar claramente la utilización de los procedimientos Allocate y Deallocate en los procedimientos creados.
