1) (50 puntos) En dos listas simplemente vinculadas se almacenan 2 polinomios de tal forma que si para los polinomios existe un término que se repite en ambos, es decir el mismo factor y los mismos exponentes para las variables x, y, z, el nodo existe una sola vez y es compartido por las listas.
Los polinomios están ordenados de mayor a menor según los exponentes de las variables y primero las ‘X’, luego las ‘Y’ y por último las ‘Z’. Las listas comienzan en P1 y P2.
La estructura del nodo es:
| signo y coef. | exp.X | exp.Y | exp.Z | LinkL1 | LinkL2 |
Realizar la multiplicación del Polinomio 1 por una constante con las consideraciones correspondiente respecto del otro polinomio ya que luego de la multiplicación un término (nodo) que era compartido puede dejar de serlo y por el contrario 2 términos que no eran iguales pueden serlo ahora.
Ejemplo de 2 polinomios:
3x2 – 5x + 4y3 – 6z2 + z
4x3 – 5x + 3z2 - 9z
Aclaración: El polinomio 1 se recorre por LinkL1 y el Polinomio 2 por LinkL2. En los nodos compartidos ambos campos tienen valor.
2) (50 Puntos ) Una expresión matemática entre valores numéricos o variables está almacenada en forma secuencial en una lista secuencia circular con P apuntando al primero al anterior ocupado y F en el último elemento. En cada posición de la lista se puede encontrar un operador (+, -, *, /), una constante numérica, el nombre de una variable, paréntesis de apertura y cierre o corchetes de apertura y cierre. Construir un algoritmo que procese la expresión y vaya informando si se encuentran los siguientes errores:
- Dos valores numéricos seguidos o dos nombres de variables seguidas sin operadores entre ellos.
- Dos operadores seguidos.
- Paréntesis o Corchetes de apertura pero no de cierre o a la inversa, solo de cierre y no de apertura.
- Una expresión entre paréntesis puede estar dentro de una expresión entre corchetes pero no a la inversa.
Los errores deben informarse a medida que se detectan o al finalizar el recorrido de la estructura.
Ej.de expresiones válidas: [5 * (A + C – 8) / B – (J * A)]
(D * 36) + T * -6
Teoría
1) (20 Puntos) Definir “Estructura de Datos”. ¿Por qué se habla de Estructuras Lógicas de Datos? ¿Cuál es la clasificación general de las Estructuras de Datos y cuáles son sus propiedades?
2) (20 Puntos) ¿Cuáles son las características de una Lista Lineal y a través de qué tipo de implementaciones en memoria puede representárselas? ¿Qué tipos especiales de listas lineales existen?
3) (20 Puntos) Definir árbol binario de búsqueda y árboles balanceados. ¿Cuándo se desbalancea un árbol y cuáles son las distintas alternativas de balanceo?
4) (20 Puntos) ¿Cuál es el fundamento de los árboles enhebrados y cuáles son las ventajas y desventajas de su utilización? ¿Es conveniente enhebrar por derecha e izquierda o solo por derecha? Justifique su respuesta.
5) (20 Puntos) Definir Grafo, Grafo Simple, Grafo Conexo y Grafo Dirigido ¿Qué tipos de estructuras de datos pueden utilizarse para representar un grafo? Describir.
Nota: El examen se aprueba con el 60 % de la práctica y el 60 % de la Teoría en forma independiente.