Examen Mayo 2019


Pregunta 1

(Prueba escrita teoría, 1.5 punto)
Represente gráficamente el árbol AVL cuyos recorridos preorden y postorden son [20, 15, 10, 5, 17, 19, 25, 30] y
[5, 10, 19, 17, 15, 30, 25, 20] respectivamente. A continuación, describir el proceso de inserción del nodo con clave 27, mostrando todos los pasos intermedios.
  1. El primer elemento en el recorrido preorden siempre es la raíz del árbol, por lo que sabemos que la raíz es 20.
  1. El segundo elemento en el recorrido preorden es 15, que es menor que 20, por lo que es el hijo izquierdo de la raíz.
  1. El siguiente elemento en el preorden es 10, que es menor que 15, por lo que es el hijo izquierdo de 15.
  1. El siguiente elemento en el preorden es 5, que es menor que 10, por lo que es el hijo izquierdo de 10.
  1. El siguiente elemento en el preorden es 17, que es mayor que 15 y menor que 20, por lo que es el hijo derecho de 15.
  1. El siguiente elemento en el preorden es 19, que es mayor que 17 y menor que 20, por lo que es el hijo derecho de 17.
  1. El siguiente elemento en el preorden es 25, que es mayor que 20, por lo que es el hijo derecho de la raíz.
  1. El último elemento en el preorden es 30, que es mayor que 25, por lo que es el hijo derecho de 25.
        20
       /  \
     15    25
    /  \     \
   10  17    30
  /      \
 5       19
Para añadir el elemento 27 al AVL comparamos recursivamente su valor con el resto de nodos hasta llegar a una hoja
        20
       /  \
     15    25
    /  \     \
   10  17    30
  /      \   /
 5       19  27

Pregunta 2

(Prueba escrita práctica, 0.5 puntos)
Dada la implementación estática de TBolsa, se pide implementar la operación Diferencia que dadas dos TBolsas, devuelve en la primera TBolsa la Diferencia entre las dos TBolsas. Si la primera bolsa tiene 3 bolas blancas y la segunda 2, la diferencia dejara 1 única bola blanca en la primera bolsa. Se consideran que las dos bolsas tienen tamaño N. La interfaz de la operación Diferencia es: PROCEDURE Diferencia(VAR b1 : TBolsa; b2 : TBolsa);
PROCEDURE diferencia(var b1: TBolsa; b2:TBolsa); 
var i:TElemento;  // Elemento abstracto de la bolsa
begin
	for i:=INI to FIN do  // Recorrer la bolsa
		b1[i] := (b1[i] - b2[i]);  // Al estar en la unidad no rompemos la encapsulacion
end;

Pregunta 3

(Prueba escrita teoría, 1 punto).
Dado el siguiente grafo, se pide:
notion image
Recorrer en profundidad el grafo, aplicando el algoritmo visto en clase, empezando por el nodo A. Es necesario mostrar el estado, paso a paso, de las estructuras de datos auxiliares utilizadas. Los adyacentes a un nodo se devuelven en orden alfabético.
notion image
 

Pregunta 4

(Prueba escrita práctica, 1,5 puntos)
Sobre árboles binarios: Implemente en una unidad la definición de tipos de un árbol binario en memoria dinámica que guarde elementos de tipo TElemento definido en la unidad uElemento. A continuación implemente las operaciones necesarias para implementar el procedimiento TioSinHijos. Este procedimiento nos devuelve una lista con todos los nodos que sean tios de un nodo, pero que a su vez no tengan hijos. Un nodo es tio si su hermano tiene hijos.
//
PROCEDURE crearArbolVacio(var a:TArbol); begin
		a := NIL;
end;

//
PROCEDURE construirNodo(var nodo:TArbol; r:TElemento; i, d:TArbol); 
var aux:TArbol;
begin
		new(aux);
		copiarElemento(aux^.raiz, r);
		aux^.hijoI := i;
		aux^.hijoD := d;
end;

//
PROCEDURE getRaiz(var r:TElemento; a:TArbol); begin
		copiarElemento(r, a^.raiz);
end;

//
PROCEDURE getHijoI(var h:TArbol; a:TArbol); begin
		if not esArbolVacio(a) then h := a^.hijoI;
end;

//
PROCEDURE getHijoD(var h:TArbol; a:TArbol); begin
		if not esArbolVacio(a) then h := a^.hijoD;
end;

//
FUNCTION esArbolVacio(a:TArbol):integer; begin
		esArbolVacio := a = NIL;
end;
//
PROCEDURE TioSinHijos(var lista:TLista; a:TArbol); 
var i, d:TArbol;
		r:TElemento;
begin
		if not esArbolVacio(a) then begin
				getHijoI(i, a);
				getHijoD(d, a);
				// hijoI es tio sin hijos
				if (not esHoja(a)) and (esTioSinHijos(i, d)) then begin
						getRaiz(r, i);
						construir(lista, r);
				end;
				// hijoD es tio sin hijos
				if (not esHoja(a)) and (esTioSinHijos(d, i)) and esTioSinHijos(d, i) then begin
						getRaiz(r, d);
						construir(lista, r);
				end;
				// Recursividad
				TioSinHijos(lista, i);
				TioSinHijos(lista, d);
		end;
end;

//
FUNCTION esTioSinHijos(tio, hermano:TArbol):boolean; begin
		if (esHoja(tio)) and (not esHoja(hermano)) then esTioSinHijos := True
		else esTioSinHijos := False; 
end;

//
FUNCTION esHoja(a:TArbol):boolean; 
var i,d:TArbol;
begin
		getHijoI(i, a);
		getHijoI(d, a);
		if (not esArbolVacio(a)) and (esArbolVacio(i)) and (esArbolVacio(d)) then esHoja := True
		else esHoja := False;
end;

Pregunta 5

(Prueba escrita práctica, 4 puntos)
Con motivo de la celebración de elecciones, la empresa pública Mails quiere digitalizar el funcionamiento en sus oficinas ya que, año tras año, el número de oficinas crece y esto dificulta su gestión. En cada oficina, solo nos interesa el funcionamiento de cómo se atiende a los clientes. Cada oficina tiene tres tipos de servicio: envío, recepción y votar por correo, y cada uno de estos tipos de servicio se atiende por estricto orden de llegada del cliente.
Por otro lado, al cliente se le pide que lleve el DNI en la mano, para evitar demoras, y que saque ticket en función del servicio que ha solicitado, el cuál asignará al cliente a la ventanilla menos saturada. Cada ventanilla puede tener clientes con diferentes servicios.
(0,5 puntos) a)
Se pide diseñar las estructuras de datos necesarias para poder gestionar las oficinas de Mails. El tipo de dato principal se llamará TMails y contendrá un listado con las TOficinas que hay en el territorio nacional. De cada TOficina nos interesa saber: su identificador, su código postal y el número de trabajadores. Además, en cada TOficina se dispone de una serie de ventanillas que atienden a los clientes por orden de llegada. Cada TOficina tendrá 5 TVentanillas. Cada TVentanilla tendrá un responsable (string), un estado (abierto o cerrado) y un código único para todas las oficinas (integer). De los TCliente que llegan a las ventanillas, nos interesa saber su DNI, y el servicio que ha solicitado.
unit uMails

interface
		type
				TNodoOficina = RECORD
						info: TElementoOficina;
						sig: ^TNodoOficina;
				END;
				TMails= ^TNodoOficina;

implementation

end.
unit uOficina

interface
		uses uVentanilla;
		type
				TElementoOficina = RECORD
						id, codPostal, numTrabajadores:integer;
						ventanillas:TListaVentanillas;
				END;
				TListaVentanillas = array[1..5] of TVentanilla;

implementation

end.
unit uVentanilla

interface
		uses uCola, uCliente;
		type
				TVentanilla = RECORD
						responsable:string;
						estado:boolean;  // True = Abierto
						cod:integer;
						cola:TCola;  // Cola de TCliente(s)
				END;
				
implementation

end.
unit uCola

interface
		uses uCliente;
		type
				TNodo = RECORD
						info:TElementoCliente;
						sig: ^TNodo;  // Siguiente (hacia el ultimo)
				END;
				TCola = RECORD
						primero:^TNodo;
						ultimo:^TNodo;
				END;
implementation

end.
unit uCliente

interface
		type
				TElementoCliente = RECORD
						dni:string;
						servicio:integer;
				END;

implementation

end.
(1 punto) b)
Crear los procedimientos adecuados para añadir un TCliente a la TVentanilla abierta, menos saturada. Para ello se dispone del DNI del cliente, el tipo de servicio que desea recibir y el identificador de la oficina en la que está solicitando el servicio. Para determinar la ventanilla idonea, se puede usar la función LongitudVentanilla, que devuelve el número de clientes en espera en dicha ventanilla, su prototipo es:
FUNCTION LongitudVentanilla(cod: integer) : integer; 
{PRE: “cod” es el código único de la TVentanilla. La función devuelve el número de clientes en espera.}
PROCEDURE nuevoClinteOficina(lista:TMails; dni:string; servicio:integer; id:integer); 
var aux_ofi: TElementoOficina;
		aux_int:integer;
		aux_lv:TListaVentanillas;
begin
		getOficina(aux_ofi, lista);  // Retorna el campo .info del TNodoLista (trivial)
		getOficinaId(aux_int, aux_ofi);  // Retorna el campo .id del TElementoOficina (trivial)
		while (not esListaVacia(lista)) and (not esOficina(aux_ofi, aux_id)) do begin
				resto(lista);  // Saca el primer elemento de la lista (trivial)
				getOficina(aux_ofi, lista);
				getOficinaId(aux_int, aux_ofi);
		end;

		if esOficina(aux, aux_int) then begin
				getListaVentanillas(aux_lv, aux_ofi);  // Obtener el campo .ventanillas del TElementoOficina (trivial)
				nuevoCliente(aux_lv, dni, servicio); 
		end;

end;

PROCEDURE nuevoCliente(var listaVentanillas:TListaVentanillas; dni:string; servicio:integer); 
var i, aux, min, ventanilla:integer;
		e:TElementoCliente;
begin
		// Asumimos ventanilla 1 como la menos concurrida
		min := LogitudVentanilla(listaVentanillas[1].cod);  // Minimo provisional
		venanilla := 1;  // Ventanilla provisional
		for i:=2 to 5 do begin
				aux := LogitudVentanilla(listaVentanillas[i].cod);  // Num de personas en la cola `i`
				if (aux < min) and (listaVentanillas[i].estado = True) then begin  // Comparamos cola en las ventanillas abiertas
						ventanilla := i;  // Actualizamos numero de ventanilla
						min := aux;  // Actualizamos num de personas en la cola mas corta
				end;
		end;

		// Encolar cliente en la ventanilla adecuada
		crearElementoCliente(e, dni, servicio)  // Asigna los datos a sus respectivos campos del tipo TCliente (trivial)
		encolar(listaVentanillas[ventanilla].cola, e);  // Añade un elemento a la cola (trivial, definido igualmente en uCliente)
end;
		PROCEDURE encolar(var c:TColaCliente, e:TElementoCliente); 
		var aux:^TNodoCliente;
		begin
				new(aux);  // Creamos nuevo nodo
				copiarElementoCliente(aux^.info, e)  // Copiamos uno a uno los campos del elemento cliente (trivial)
				aux^.sig := NIL;
				if not esColaVacia(c) then c.ultimo^.sig := aux;  // Si la cola no es vacia, le decimos al ultimo que tiene uno detrás
				c.ultimo := aux;  // Asignamos `aux` como el nuevo últimos de la cola
		end;
(1 punto) c)
En determinadas circunstancias, es necesario cerrar una TVentanilla, y dado que es posible que hubiera algún TCliente en ella, es necesario repartir los TClientes en espera, entre el resto de TVentanillas que estén abiertas. Implementar todos los procedimientos necesarios para realizar la operación anterior, sabiendo que se nos pasa el código único de la TVentanilla a cerrar. Nota: los TClientes son asignados por orden, se extrae el cliente que lleva más tiempo en la TVentanilla a cerrar y se le asigna a la TVentanilla abierta y menos saturada como último cliente. Se repite la operación hasta que la TVentanilla a cerrar esté vacía
PROCEDURE cerrarVentanilla(var listaVentanillas:TListaVentanillas; cod:integer); 
var i, servicio:integer;
		dni:string;
		e:TElementoCliente;
begin
		for i:=1 to 5 do begin
				if (listaVentanillas[i].cod = cod) then begin
						listaVentanillas[i].estado := False;  // Cerramos la ventanilla
						while not esColaVacia(listaventanillas[i].cola) do begin  // Movemos a los cliente a otras colas
								desencolar(listaventanillas[i].cola, e)  // Sacar elemento TCliente de la cola
								getDNI(dni, e);  // Extraer los datos del TCliente (trivial)
								getServicio(servicio, e);  // Extraer los datos del TCliente (trivial)
								nuevoCliente(listaVentanillas, dni, servicio);  // Definido por el apartado B)
						end; // while
				end; // if cod=cod
		end; // for
end;
PROCEDURE desencolar(var c:TColaCliente, e:TElementoCliente); 
var aux:^TNodoCliente;
begin
		if not esColaVacia(c) then begin
				copiarElementoCliente(c.primero^.info, e)  // Copiamos uno a uno los campos del elemento cliente (trivial)
				dispose(c.primero)  // Liberar la memoria del primero
				c.primero := c.primero^.sig;  // Avanzar la cola
		end;
end;
(1,5 puntos) d)
En época de elecciones, cuando llega la hora habitual de cierre de una oficina y para evitar saturaciones, se cierran todas las TVentanillas menos una. Los TClientes actualmente en espera cuyo servicio solicitado sea “votar”, serán añadidos a la TVentanilla que permanecerá abierta, descartando al resto de TClientes que tendrán que volver otro día. Se sigue un estricto orden a la hora de asígnar los TClientes a la TVentanilla única. Primero se asignan los primeros TClientes de cada ventanilla: el primer TCliente de la primera TVentanilla, el primer TCliente de la segunda TVentanilla, el primer TCliente de la tercera TVentanilla, etc. Cuando se han reasignado los primeros TClientes de cada TVentanilla pasa a asignarse los segundos (que ahora serán los primeros) y así hasta que solo queden TClientes en la TVentanilla única. Se pide implementar los procedimientos adecuados para cerrar todas las ventanillas menos una, permitiendo a los TCliente cuyo servicio solicitado haya sido “votar”, en el orden descrito anteriormente
// Cierra todas menos la 1
PROCEDURE ultimaHora(var listaVentanillas:TListaVEntanillas);
var i, servicio:integer;
		e:TElementoCliente;
begin
		// Cerrar todas las ventanillas
		listaVentanillas[2].estado := False;
		listaVentanillas[3].estado := False;
		listaVentanillas[4].estado := False;
		listaVentanillas[5].estado := False;

		// Comprobar que todas la colas estan vacias
		while (not esColaVacia(listaVentanillas[2].cola)) and
					(not esColaVacia(listaVentanillas[3].cola)) and
					(not esColaVacia(listaVentanillas[4].cola)) and
					(not esColaVacia(listaVentanillas[4].cola)) and do 
		begin
				// Recorrer las colas abiertas
				for i:=2 to 5 do begin
						// Si la cola tiene gente todavía, mueve el primero a la cola `1`
						if not esColaVacia(listaVentanillas[i]) then begin
								desencolar(listaVentanilla[i], e);  // Sacar primero de la cola `i`
								getServicio(servicio, e);
								// Asumiendo que 'votar' es el servicio `3` porque me apetece
								if servicio = 3 then encolar(listaVentanilla[1], e);  // Meterlo en la cola `1` 
			
						end; // if
				end; // for
		end; // while
end;