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á TMailsy 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 TVentanillaabierta, 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;