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.
- El primer elemento en el recorrido preorden siempre es la raíz del árbol, por lo que sabemos que la raíz es 20.
- 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.
- El siguiente elemento en el preorden es 10, que es menor que 15, por lo que es el hijo izquierdo de 15.
- El siguiente elemento en el preorden es 5, que es menor que 10, por lo que es el hijo izquierdo de 10.
- 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.
- 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.
- El siguiente elemento en el preorden es 25, que es mayor que 20, por lo que es el hijo derecho de la raíz.
- 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: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.
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 lasTOficinas
que hay en el territorio nacional. De cadaTOficina
nos interesa saber: su identificador, su código postal y el número de trabajadores. Además, en cadaTOficina
se dispone de una serie de ventanillas que atienden a los clientes por orden de llegada. CadaTOficina
tendrá 5TVentanillas
. CadaTVentanilla
tendrá un responsable (string), un estado (abierto o cerrado) y un código único para todas las oficinas (integer). De losTCliente
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 unTCliente
a laTVentanilla
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ónLongitudVentanilla
, 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 unaTVentanilla
, y dado que es posible que hubiera algúnTCliente
en ella, es necesario repartir losTClientes
en espera, entre el resto deTVentanillas
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 laTVentanilla
a cerrar. Nota: losTClientes
son asignados por orden, se extrae el cliente que lleva más tiempo en la TVentanilla a cerrar y se le asigna a laTVentanilla
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 lasTVentanillas
menos una. LosTClientes
actualmente en espera cuyo servicio solicitado sea “votar”, serán añadidos a laTVentanilla
que permanecerá abierta, descartando al resto deTClientes
que tendrán que volver otro día. Se sigue un estricto orden a la hora de asígnar losTClientes
a laTVentanilla
única. Primero se asignan los primerosTClientes
de cada ventanilla: el primerTCliente
de la primeraTVentanilla
, el primerTCliente
de la segundaTVentanilla
, el primerTCliente
de la terceraTVentanilla
, etc. Cuando se han reasignado los primerosTClientes
de cadaTVentanilla
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 losTCliente
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;