Examen Mayo 2022

Examen Mayo 2022.pdf

💡

La siguiente función esta permitida para su uso durante la prueba

FUNCTION CompareText(const S1: string; const S2: string) : Integer;

Esta función devuelve 0 si las dos cadenas son iguales, devuelve un valor menor que 0 si la cadena S1 es menor (más cercano a la ‘a’) que S2 y devuelve un número mayor que cero si S1 es mayor que S2. En este contexto, es menor y es mayor hace referencia al orden alfabético.

Pregunta 1

(Prueba escrita práctica, 1,5 puntos)
Dado un árbol que representa un torneo donde los equipos se identifican por un nombre y se guardan los puntos del encuentro. Devolver los equipos participantes ordenados alfabéticamente.

// Devolver lista de participantes
PROCEDURE listaHojas(var l:TLista, a:TArbol); 
var r:Telemento;
		nombre:string;
		eStr:TElementoStr;
		i,d:TArbol;
begin
		if not esArbolVacio(a) then begin
				if esHoja(a) then begin
						getRaiz(r, a);  // Obtiene el TElemnto de la raiz de un arbol
						getNombre(nombre, r);  // Obtiene el nombre del TElemento
						crearElementoLista(eStr, nombre);
						construirOrdenado(l, eStr);  // Añadir a la lista
				end 
				else 
						getHijoI(i, a);  // Obtiene el subarbol del hijo izq
						getHijoD(d, a);  // Obtiene el subarbol del hijo dch
						listaHojas(l, i);  // Paso recusivo
						listaHojas(l, d);  // Paso recusivo
		end;
end;

PROCEDURE construirOrdenado(var l:TLista; eStr:TElementoStr); 
var auxE:TElementoStr;  // Elemento iterador
begin
		getElemento(auxE, l);
		while (not esListaVacia(l)) and (esElementoMenor(eStr, auxE)) do begin
			l := l^.sig;
			getElemento(auxE, l);			
		end;
		construir(l, eStr)
end;

FUNCTION esElementoMenor(e1, e2:TElementoStr):boolean; begin
		if CompareText(e1, e2) < 0 then esElementoMenor := True
		else esElementoMenor := False;
end;

Pregunta 2

Una empresa desea guardar la información de sus almacenes y pedidos. Cada almacén puede estar equipado para distintos tipos de mercancías:
⚠️
Los nombres de los tipos mencionados en el enunciado no tienen relación con su prioridad en la cola (podían haberse llamado: manzanas, naranjas, tomates, …), solo nos importa el hecho de que hay 10 tipos de mercancía y cada tipo recibe un número del 1 al 10
En total hay 10 tipos de mercancías distintas que puede guardar un almacén. Por supuesto, un almacén puede guardar uno o varios de esos tipos a la vez. Un almacén también guardará una lista de los pedidos que almacena. Debido a que existen pedidos más importantes que otros, estos artículos estarán guardados en función de su prioridad. En caso de que dos pedidos tengan la misma prioridad, estará primero el que primero llego. Cuando un almacén está a punto de llenarse, se hace uso de los almacenes cercanos, es por esto por lo que se guardará la información de que almacenes son vecinos entre sí y la distancia que los separa. Además, un almacén ha de guardar información de su capacidad máxima y actual.

(0,5 puntos) a)

Se pide definir las estructuras de datos necesarias separándolas en sus correspondientes unidades sabiendo que: TAlmacenes es la estructura principal en la que se guardarán los almacenes de tipo TAlmacen. Un TAlmacen guardará la información relativa a un almacén como son: un String con el nombre, su capacidad máxima y actual (enteros). Un almacén también guarda qué tipos de artículos puede almacenar y los pedidos que tiene almacenados. El tipo de artículos que componen un pedido o que puede guardar un almacén deberá usarse una estructura eficiente para la consulta. Un TPedido guardará información sobre el tipo de artículos que lo componen (2: pequeño y 5: urgente, por ejemplo), la cantidad o volumen que ocupa el pedido y la prioridad (entero).

unit uGrafo;

interface
		uses uAlmacen;
		type
				TAlmacenes = ^TNodoAlmacen;  // Grafo
				TNodoAlmacen = RECORD  // Nodo grafo
						info:TVertice;
						sig:^TNodoAlmacen;
				END;

implementation

end.

unit uVertice;

interface
			uses uAlmacen, uArista;
		type
				TVertice = RECORD  // Vertice del grafo
						almacen:TAlmacen;  // Elemento del vertice
						aristas:TListaAristas;  // Lista de aristas del vertice
				END;
				TListaAristas = ^TNodoArista;
				TNodoArista = RECORD
						info:TArista;
						sig:^TNodoArista;
				END;
implementation

end.

unit uAlmacen;

interface
		uses uConjuntoTipos, uColaPrioridad;
		type
				TAlmacen = RECORD  // Elemento del vertice 
						nombre:string;
						cap,max:integer;
						tipos:TConjuntoTipos;  // Conjunto
						pedidos:TColaPrioridad; // Cola de prioridad
				END;
				TAlmacenID = string;  // Coincidente con nombre de TAlmacen
implementation

end.

unit uArista;

interface
		uses uArista;
		type
				TArista = RECORD
						id:TAlamcenID;
						peso:integer;
				END;
implementation

end.

Estructuras de datos

unit uColaPrioridad;

interface
		uses uPedido;
		type
				TColaPrioridad = ^TNodoCola;
				TNodoCola = RECORD
						info:TPedido;
						sig:^TNodoCola
				END;
implementation

end.

unit uPedido;

interface
		type
				TPedido = RECORD
						tipos:TConjuntoTipos;
						volumen, prioridad:integer;
				END;
implementation

end.

unit uCojuntoTipos;

interface
		const  // Deberian estar en otra unidad
				INI = 1;
				FIN = 10;
		type
				TElementoTipos = INI..FIN;  // Deberia estar en otra unidad
				TConjuntoTipos = array[TElementoTipos] of boolean;
implementation

end.

(1 punto) b)

Se pide implementar las operaciones necesarias para añadir un nuevo almacén vecino de otro. Ambos almacenes ya están insertados, solo es necesario añadirlo como vecino dada la distancia.

// Añadir arista
PROCEDURE anadirVecino(var verticeSrc, verticeDst:TVertice; distancia:integer); 
var id:TAlmacenID  // TElementoID
		almacen:TAlmacen; // TElemento
		arista:TArista;  // TAdy
begin
		// Obtener el ID del vertice destino (trivial)
		getAlmacen(almacen, verticeDst);
		getAlmacenID(id, almacen);
		//
		crearArista(arista, id, distancia);  // Crear TArista a partir de un

PROCEDURE construirArista(var vertice:TVertice; arista:TArista); 
var aux:TNodoArista;
begin
		new(aux);
		copiarArista(aux.info, arista);  // asignar/copiarElemento() (

(1 punto) c)

Se pide devolver una lista con los nombres de los almacenes que puedan guardar productos de los tipos especificados (pequeños y refrigerados o voluminosos, urgente y peligrosos, entre otras combinaciones)
PROCEDURE AlmacenesAptos(a: TAlmacenes; t: TConjuntoTipos; l: TLista);

PROCEDURE AlmacenesAptos(a: TAlmacenes; t: TConjuntoTipos; var l: TLista); 
var alamcen:TAlmacen;
		nombre:string;
		tiposAlmacen: TConjuntoTipos;
		aux:TElementoLista;  // Elemento de la lista de nombres
begin
		while not esListaAlmacenesVacia(a) do begin
				getAlmacen(almacen, a^.info); 
				getTipos(tiposAlmacen, almacen);
				if esSubconjunto(tiposAlmacen, t) then begin  // Si el almacen es apto
						getNombre(nombre, almacen);
						crearElementoLista(aux, nombre);  // Elemento de la lista generica pasada por parametros
						construir(l, aux);  // Añadir elemento a dicha lista
				end;			
				a := a^.sig;
		end;
end;

FUNCTION esSubconjunto(sub, padre:TConjuntoTipos):boolean; 
var i:TElementoConjunto
begin
		esSubconjunto := True;
		for i:=INI to FIN do 
				if (padre[i]) and (not sub[i]) then esSubconjunto := False;
end;

(1,5 puntos) d)

Implementar las operaciones necesarias para liberar los almacenes de una región. Dado un almacén, si su capacidad supera el 75%, liberará los pedidos almacenados hasta quedarse por debajo. Esta operación se repite con sus almacenes vecinos (solo los vecinos del almacén dado).
PROCEDURE LiberarAlmacenes(a: TAlmacenes; alm_principal: string);

PROCEDURE LiberarAlmacenes(a: TAlmacenes; alm_principal: string); 
var almacen:TAlmacen;
		listaVecinos:TListaAristas;
		arista:TArista;
		id:TAlmacenID;
		nombre:string;
begin
		buscarAlmacen(almacen, a, alm_principal);  // Busca un almacen por nombre y lo devuelve a `almacen`
		getListaAristas(listaAristas, a^info);  // Desencapsula el TListaAristas de un TVertice
		getNombre(nombre, alamacen); // Desencapsula el

PROCEDURE liberarAlmacen(var almacen:TAlmacen); 
var cap,max:integer;
		pedidos:TListaPedidos;
		pedido:TPedido;
begin
		getListaPedidos(pedidos, almacen);
		getCap(cap, almacen);  // Desencapsula el

PROCEDURE buscarAlmacen(var almacen:TAlmacen; a:TAlmacenes, nombre:string); 
begin
		getAlmacen(almacen, a^.info);
		while not (esListaAlmacenesVacia(a)) and (not esAlmacenID(almacen, nombre)) do begin
				a := a^.sig;
				getAlmacen(almacen, a^.info);
		end;
end;

PROCEDURE siguiente(var l:TLista); begin
		if not esListaVacia(l) then l := l^.sig;
end;

FUNCTION esAlmacenID(alamacen:TAlmacen; id:string):boolean; begin
		esAlmacenID := almacen.nombre = id;
end;