AAED PARTE 4

¿Qué es una lista?. Una colección de elementos donde solo se puede acceder al primero y al último. Una secuencia lineal de elementos definida por posiciones con predecesor y sucesor. Una estructura jerárquica donde cada elemento puede tener varios sucesores. Un conjunto de datos sin orden definido entre sus elementos.

¿El TAD lista y el TAD lista circular son TADs diferentes?. No, en realidad se trata del mismo Tipo Abstracto de Datos, simplemente presentado o realizado mediante una implementación diferente. Sí, porque su especificación y relaciones entre posiciones son distintas. No, solo cambia la forma de recorrer la estructura. Sí, pero únicamente en la forma de almacenar los datos.

¿En una representación vectorial de una lista, cómo representamos la posición fin?. Mediante un puntero especial al último elemento. Con un valor entero igual al número actual de elementos. Utilizando una posición fija reservada del vector. Mediante un valor nulo que indica final de recorrido.

Ventajas e inconvenientes de la implementación vectorial del TAD Lista. Acceso rápido por índice, pero inserciones y borrados costosos. Tamaño dinámico ilimitado con bajo consumo de memoria. Inserciones eficientes, pero acceso lento a posiciones intermedias. Gestión compleja de punteros con alto coste temporal.

Ventajas e inconvenientes de la implementación dinámica del TAD Lista. Acceso directo eficiente, pero capacidad limitada. Inserciones rápidas, pero acceso lento y mayor uso de memoria. Bajo consumo de memoria y acceso aleatorio constante. Eliminaciones costosas por desplazamiento de elementos.

¿Por qué surge el nodo cabecera en el TAD Lista?. Para reducir el consumo de memoria de la estructura. Para evitar tratar de forma especial al primer elemento. Para permitir acceso directo al último nodo. Para eliminar la necesidad de punteros externos.

¿Con qué problema fundamental nos encontramos si suprimimos L en los argumentos de las operaciones del TAD lista?. Se pierde eficiencia temporal en las operaciones básicas. Se rompe la independencia entre especificación e implementación. Aumenta el consumo de memoria de la estructura. Se limita el número de operaciones disponibles.

¿Cuándo se utiliza el TAD Lista Circular?. Cuando se necesita acceso directo por índice. Cuando no existen extremos definidos en la secuencia. Cuando se requiere inserción solo al final. Cuando se desea una lista con nodo cabecera.

Diferencia entre TAD Lista Circular y TAD Lista. La lista circular permite acceso aleatorio constante. En la lista circular no existen extremos ni posición fin. La lista circular requiere siempre nodo cabecera. El TAD Lista no admite operaciones de recorrido.

¿Cuándo es conveniente utilizar una implementación mediante estructura enlazada doble en el TAD Lista?. Cuando solo se recorre la lista en un sentido. Cuando se necesita acceso bidireccional eficiente. Cuando se desea minimizar el uso de memoria. Cuando el tamaño de la lista es fijo.

En la lista Circular, ¿es posible implementar alguna operación de orden logarítmico?. Sí, usando búsqueda binaria sobre punteros. No, las operaciones son O(1) u O(n). Sí, si la lista está ordenada. Solo si se usa una lista doblemente enlazada.

¿Qué condición tiene que cumplir una lista para que la búsqueda sea logarítmica? ¿Y de orden cuadrático?. Acceso secuencial y datos ordenados; cuadrática en vectores. Acceso directo y datos ordenados; cuadrática por accesos repetidos. Uso de punteros dobles; cuadrática en listas circulares. Nodo cabecera obligatorio; cuadrática en listas simples.

¿Para qué se utiliza una implementación mediante estructura enlazada doble?. Para reducir el consumo de memoria. Para obtener acceso eficiente en ambos sentidos. Para permitir acceso aleatorio por índice. Para evitar el uso de punteros externos.

¿Por qué en la especificación del TAD lista, en la operación anterior, las precondiciones son L=(a₁,a₂,…,aₙ) 2 ≤ p ≤ n+1?. Porque la primera posición no tiene predecesor válido. Porque la posición fin nunca puede tener predecesor. Porque todas las posiciones tienen sucesor. Porque p siempre debe ser menor que n.

¿Por qué en la especificación del TAD lista, en la operación siguiente, las precondiciones son L=(a₁,a₂,…,aₙ) 1 ≤ p ≤ n?. Porque la posición fin tiene sucesor. Porque el último elemento no tiene sucesor válido. Porque la primera posición no tiene predecesor. Porque todas las posiciones tienen anterior.

¿Por qué en la especificación del TAD Lista Circular, en las operaciones anterior y siguiente, las precondiciones son L=(a₁,a₂,…,aₙ,a₁) 1 ≤ p ≤ n?. Porque existe un nodo cabecera implícito. Porque todas las posiciones tienen anterior y siguiente. Porque no existe la posición fin. Porque la lista permite acceso directo.

¿Qué pasaría si insertaras o eliminaras en la primera posición en una implementación de lista enlazada sin cabecera?. Nada, se ejecutaría igual que en otras posiciones. Habría que usar un código especial para modificar el inicio. Se produciría un desbordamiento de memoria. Se perdería la referencia al último nodo.

Representando el TAD lista mediante un vector, ¿es posible evitar el coste O(n) para inserciones y borrados en los extremos?. No, siempre es necesario desplazar elementos. Sí, usando un vector circular. Solo si la lista es estática. Solo en listas doblemente enlazadas.

¿Por qué se pasa el parámetro posición por referencia en una lista en las operaciones insertar y eliminar con estructuras enlazadas?. Para reducir el número de copias de datos. Para que la posición siga siendo válida tras modificar enlaces. Para permitir acceso directo por índice. Para cumplir las precondiciones del TAD.

¿En qué programas utilizarías el TAD Lista?. En aplicaciones con acceso estrictamente FIFO. En programas que gestionan secuencias con inserciones arbitrarias. En sistemas donde los elementos se procesan siguiendo el orden LIFO. En aplicaciones con tamaño fijo de datos.