Mayo 2021

---

Ejercicio 1

Dados los siguientes supuestos prácticos decidir: (1) cuál es la MEJOR estructura de datos, y (2) su MEJOR implementación para resolver el problema (para ser considerada correcta, AMBAS respuestas deberán estar justificadas): (1,5 pts.)

CD KOMICS se dispone a sacar a la venta una serie superlimitada de 500 figuras de acción del superhéroe Faneca Man, y se quieren gestionar los pedidos que lleguen a la editorial. Las peticiones de compra se tramitarán conforme vayan llegando, si bien tendrán preferencia los clientes suscritos a su cómic, seguidos por los clientes suscritos a otros cómics de la editorial y, finalmente, el resto de clientes. ¿Cómo debemos almacenar los pedidos?

En este caso utilizaremos una cola con prioridad, implementada con una lista estática de prioridades (3), y de cada nodo colgará una cola dinámica, pues desconocemos la cantidad de pedidos que llegarán. Elegimos una cola dinámica para cada categoría, porque aunque conozcamos la cantidad máxima de figuritas que se pueden ofrecer, desconocemos cuantas serán destinadas a cada una de las prioridades; existe el caso, pues, de que 500 clientes suscritos al cómic sean atendidos por orden de llegada antes de avanzar a la siguiente prioridad.

La Oficina de Turismo de Villaconejos de Arriba está desarrollando una app que nos permitirá consultar las atracciones turísticas de los alrededores según dos criterios: duración aproximada de la visita y precio. ¿Cuál será el modo adecuado de almacenar los datos de dichas atracciones de forma que se puedan generar los dos listados de forma eficiente? La Oficina de Turismo también nos ha informado que se están realizando inversiones y se espera que la oferta de atracciones vaya aumentando en los próximos años.

En este caso se empleará una lista dinámica multiordenada con dos factores de ordenación; es decir, cada nodo almacenará la información específica de la atracción y dos punteros: uno que apuntará a la siguiente atracción según el factor precio, y otra según el factor tiempo.

R0B0T-1J0 es un androide extraterrestre que acaba de llegar a nuestro planeta. Como tiene muchas cosas que explorar y es un poco antisocial, no puede permitirse tener mas de 10 amigos. Si ya tiene el cupo lleno, pero conoce a alguien nuevo e interesante, tendrá que sustituir a alguno de sus amigos actuales por esa persona. Como es un robot muy objetivo, ha decidido que lo que hará será reemplazar a aquella persona que menos tiempo lleve siendo su amiga. ¿Cómo deberá almacenar su lista de amigos en su cerebro digital?

En este caso se utilizará una pila estática de tamaño 10, pues conocemos la cantidad máxima de elementos que se van a almacenar. Una pila sigue el principio LIFO (Last in first out), gracias a esta lógica, siempre que se elimine un amigo de la lista, éste será el último en haber sido añadido.

---

Ejercicio 2

Verdadero/Falso: (1 pto.)

Dado un puntero p y la variable a la que apunta, no basta con hacer p=NULL para liberar la memoria de la variable. También tenemos que hacer free(p) a continuación.

Falso. Si bien es cierto que es necesario llamar a free, el orden de ejecución es incorrecto. En clase se indicó que primero se debe liberar explícitamente esa memoria (usando free()), y después se debe asignar el puntero a null para evitar accesos posteriores a memoria liberada.

Una vez seleccionada la implementación a emplear para un TAD, ya no será posible en un futuro cambiar dicha implementación sin tener que realizar también modificaciones importantes en los programas que empleen ese TAD.

Falso. La forma de interactuar con un TAD es mediante una interfaz pública –las funciones contenidas en la especificación–. Siempre que la especificación se mantenga igual, la forma en la que se haya implementado es irrelevante para el correcto funcionamiento del programa.

Si se trata de un programa que haya almacenado información en memoria que se reutiliza entre sesiones, cambiar la forma en la que el TAD accede a la información internamente si que llevaría a una posible pérdida de datos por incompatibilidad.

El TAD Pila puede implementarse a partir del TAD Lista

Verdadero. El TAD Pila puede implementarse utilizando el TAD Lista como base, ya que solo sería necesario modificar ligeramente las implementaciones de la lista al extremo superior, pues la pila solo permite inserción acceso o modificación en esa posición.

Dados dos árboles binarios que contengan el mismo número de nodos, uno ABB y otro AVL, por lo general el AVL tendrá mayor altura.

Falso. Un AVL garantiza un factor de equilibrio $\in [-1,1]$, mientras que un ABB mantiene el orden de inserción. Esto quire decir que si se inserta una cantidad de datos ascendientes n, un ABB tendrá una altura n, mientras que un AVL habrá realizado rotaciones que garantizan que el árbol sea más equilibrado.

---

Ejercicio 3

En el siguiente código hay tres errores. Identifica cada uno de ellos, indica por qué se trata de un error y propón el correspondiente código corregido (basta con reescribir la parte del código afectada). (0,75 pts.)

#include <stdio.h>
#include <stdlib.h>
 
typedef int* tPIntegrer;
typedef int tIntegrer;
 
tIntegrer addValues(tPIntegrer m, tPIntegrer n) {
	tPIntegrer temp;
 
	temp = malloc(sizeof(int));
	*temp = m + *n;
	return(temp)	
}
 
int main() {
	tPIntegrer p, q;
	p = malloc(sizeof(int));
	scanf("%d", p);
	q = malloc(sizeof(int));
	*q = 6;
	*q = addValues(p,q);
	free(q);
	printf("%d %d", *p,*q);
}

1. Suma incorrecta de punteros. m y n son ambos dos punteros, no es posible sumar un puntero m a un int *n. La solución es cambiar la línea 11 por:

//...
*temp = *m + *n;
//...

2. Uso incorrecto de punteros: La función addValues debe devolver un valor de tipo tIntegrer (es decir, un entero), pero actualmente está devolviendo un puntero. Esto ya es un error de tipo, aunque podría corregirse simplemente cambiando return(temp) por return(*temp). Sin embargo, el uso de memoria dinámica dentro de esta función no tiene sentido, ya que solo se necesita calcular y devolver la suma de dos enteros, sin conservar ese valor en memoria tras finalizar la función. Además, al reservar memoria con malloc dentro de la función y no liberarla posteriormente, se produce una fuga de memoria. Por tanto, lo más apropiado es evitar el uso de punteros aquí y trabajar directamente con variables de tipo entero.

tIntegrer addValues(tPIntegrer m, tPIntegrer n) {
	tIntegrer temp;
 
	temp = *m + *n;
	return(temp);
}

3. Fuga de memoria y acceso ilegal. en la línea 18 se libera el puntero q y, posteriormente, en la línea 19 se accede al contenido almacenado en q; esto puede provocar comportamientos inesperados. Además, el puntero p nunca se libera. Por lo tanto hay que modificar el código para liberar ambos tras la impresión.

	//...
	printf(...)
	free(q);
	free(p);
}

---

Ejercicio 4

El tipo abstracto de datos (TAD) tBinTree sirve para representar árboles binarios de búsqueda de enteros positivos y para manipularlo solamente disponemos de la siguiente interfaz: (1,25 pts.)

#define TNULL ...
typedef unsigned int tItemT;
typedef ... tBinTree;
 
void createEmptyTree(tBinTree *T);
bool buildTree(tBinTree LTree, tItemT d, tBinTree RTree, tBinTree *T);
tBinTree leftChild(tBinTree T);
tBinTree rightChild(tBinTree T);
tBinTree root(tBinTree T);
bool isEmptyTree(tBinTree T);

Precondición común a leftChild, rightChild y root: árbol no vacío

A) (0,75 pts.)

Se pide codificar la siguiente operación:

addLeaves(tBinTree T) -> int, que suma los valores almacenados en las hojas del árbol T.

int addLeaves(tBinTree T) {
    if (isEmptyTree(T)) {
        return 0;
    }
    // Si no tiene hijos, es una hoja
    if (isEmptyTree(leftChild(T)) && isEmptyTree(rightChild(T))) {
        return root(T);
    }
 
    // Recursivamente suma las hojas del subárbol izquierdo y derecho
    return addLeaves(leftChild(T)) + addLeaves(rightChild(T));
}

B) (0,5 pts.)

Figura:

                      50(-1)
                    /       \
                 30(1)       70
                /  \        /  \
              [A]  40(-1)  60   80
                  /   \           \
                [B]   [C]          90

Dado el árbol AVL de la figura:

• Identifica que tipo de recorrido muestra las claves en el siguiente orden: claves subárbol A - claves subárbol B - Claves subárbol C - 40 - 30 - 60 - 90 - 80 - 70 - 50.
• ¿Cuál es la altura de los subárboles A, B y C? Justifique la respuesta.
• Tras eliminar la clave 90, muestre el árbol resultado identificando cualquier transformación necesaria y explicándola paso a paso.

El recorrido que se describe es el posorden.

Para determinar las alturas de A, B y C usaremos la fórmula del factor de equilibrio, y estos datos que extraemos de la figura:

$$\begin{array}{rl}\text{FE}(50)& =-1\\ \text{FE}(30)& =1\\ \text{FE}(40)& =-1\\ h(70)& =2\text{(subaˊrbol derecho de 50)}\end{array}$$

• Nodo 50:

Si $\text{FE}(50)=-1$ y $h(70)=2$:

$$h(30)=h(70)-\text{FE}(50)=2-(-1)=3$$

• Nodo 30:

Ya tenemos $h(30)=3$ y $\text{FE}(30)=1$. Eso significa:

$$h(40)-h(A)=1\Rightarrow h(40)=h(A)+1$$

Por definición de altura:

$$h(30)=1+\max (h(A),h(40))=3$$

Sustituimos $h(40)=h(A)+1$:

$$3=1+\max (h(A),h(A)+1)\Rightarrow \max =h(A)+1\Rightarrow 3=1+h(A)+1\Rightarrow h(A)=1$$

Entonces:

$$h(40)=h(A)+1=2$$

• Nodo 40:

Tenemos $\text{FE}(40)=-1$:

$$h(C)-h(B)=-1\Rightarrow h(C)=h(B)-1$$

Y también:

$$h(40)=1+\max (h(B),h(C))=2\Rightarrow \max (h(B),h(C))=1$$

Para que eso se cumpla con $h(C)=h(B)-1$:

$$\begin{array}{rl}h(A)& =1\\ h(B)& =1\\ h(C)& =0\end{array}$$