1) (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
2) (50 puntos) Dos polinomios de una variable están almacenados en 2 listas simplemente vinculadas con nodo cabecera con comienzo en P1 y P2 respectivamente, donde la estructura de cada elemento de la lista es la siguiente:
Realizar la suma de los dos polinomios creando una lista doblemente vinculada circular con inicio en P3 con el polinomio resultante.
Teoría
1) (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? ¿Cuáles son las ventajas y desventajas de las representaciones secuenciales y vinculadas de listas?
A cada elemento se le asigna un siguiente, excepto al ultimo. Se debe referenciar un nombre, dirección o índice de la lista. Tipos de representación: Secuencial y Vinculada. Cola, pila, bicola, con restricción. Ventajas: se puede acceder a cualquier elemento, Lista progresiva, no desperdicia memoria (eliminación e inserción fácil). Desventaja: Tiene un solo elemento que la sigue, tiene P y F fijo, corrimiento costo.
2) (20 Puntos) Definir árboles binarios de búsqueda y árboles balanceados. ¿Cuáles son las distintas alternativas de balanceo? ¿Cuándo es necesario re-organizar un árbol?
3) (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.
4) (20 Puntos) Definir Grafo, Grafo Simple, Grafo Conexo y Grafo Dirigido ¿Qué tipos de estructuras pueden utilizarse para representar un grafo? Describir.
5) (20 Puntos) ¿Cuáles son las diferencias entre los archivos secuenciales y los archivos indexados? ¿En qué situaciones conviene utilizar cada uno de ellos?
Nota: El examen se aprueba con el 60 % de la práctica y el 60 % de la Teoría en forma independiente.