Práctica

1) (50 puntos) Dadas dos colas coexistiendo en una estructura secuencial circular con comienzo y fin en P1, F1 y P2, F2, donde P1 y P2 apuntan al anterior a la primera posición ocupada de cada lista respectivamente y F1 y F2 a los últimos elementos, reacomodar las listas de tal manera que en la lista 1 queden los elementos pares y en la lista 2 los impares.

2) (50 puntos) Un Archivo de Texto se encuentra almacenado en una estructura con las siguientes características:

- Una lista simplemente vinculada, con nodo cabecera, que tiene un nodo por cada renglón del texto.

- La INFO de cada nodo es una lista secuencial de 100 caracteres que es la máxima capacidad de cada renglón.

- Un párrafo termina con un punto y los siguientes caracteres hasta los 100 son blancos y el siguiente renglón contiene una sangría (espacios en blanco) de cinco caracteres.

Construir un algoritmo que permita conocer la cantidad de párrafos de un solo renglón y los elimine del texto.

Teoría

1) (20 Puntos) Definir “Estructura de Datos” y sus propiedades. ¿Por qué se denominan estructuras lógicas de datos a las Pilas, Colas, Árboles, etc.?

Conjunto de datos que se caracteriza por su organización y las operaciones que se pueden realizar con ellas. Propiedades: Estatica, dinámica y de Representacion. Se denominan estructuras lógicas porque se la puede representar de diferentes formas con respecto a la forma física.

2) (20 Puntos) ¿En qué casos utilizaría listas vinculadas en lugar de listas secuenciales? ¿Cuál es la ventaja del uso de listas doblemente vinculadas con relación a listas simplemente vinculadas? ¿Para qué se utilizan los nodos cabecera?

En caso de que requiera insertar o eliminar varios elementos porque en una lista secuencial por el corrimiento es costoso. La ventaja sobre la simplemente vinculada es poder moverte hacia delante o atrás sin perder el numero anterior. Facilita la inserción como primer nodo.

3) (20 Puntos) Definir árboles balanceados y las distintas alternativas de balanceo. ¿Por qué se utilizan los árboles balanceados por su altura en lugar de un árbol totalmente balanceado?

Arbol balanceado cuando a simple vista esta lo mas balanceado posible respecto a su altura. Balanceo según su peso(cantidad iguales de nodos en izq y der) y según su altura(cantidad de niveles que puede diferir como máximo 1). Son mas fáciles de comprobar xq por peso tenes que contar nodo por nodo y por altura simplemente ver los niveles.

4) (20 Puntos) Definir árbol de montón y describir el procedimiento para insertar nodos en dicho árbol.

Arbol de monton Max (padre > que sus hijos), árbol de monton Min (padre < que sus hijos). Se pone un nodo X al final del árbol de tal modo que se satisfaga la condición de que sea un árbol casi completo y luego se lleva el valor a donde corresponde haciendo cambios con sus antecedentes.

5) (20 Puntos) Definir Grafo, Grafo Simple, Grafo Conexo y Grafo Dirigido ¿Qué tipos de estructuras pueden utilizarse para representar un grafo? Describir cada uno y plantear un ejemplo sencillo.

Nota: El examen se aprueba con el 60 % de la práctica y el 60 % de la Teoría en forma independiente.