AAED Examen Final (Teoría Estructura de Datos)

¿Qué es la abstracción y por qué es esencial en programación?. Es ignorar detalles irrelevantes para resaltar lo esencial y manejar la complejidad. Es eliminar partes del programa para hacerlo más corto. Es centrarse solo en la implementación concreta. Es ocultar errores del programa.

¿Cómo se aplica la abstracción en la resolución de problemas informáticos?. Construyendo un modelo conceptual del problema antes de implementarlo. Programando directamente sin diseño previo. Optimizando el código desde el principio. Eligiendo el lenguaje más rápido.

¿Qué dos formas principales de abstracción ofrece la programación?. Abstracción operacional y abstracción de datos. Abstracción sintáctica y semántica. Abstracción funcional y estructural. Abstracción lógica y física.

¿Qué caracteriza a la abstracción operacional?. Definir y usar funciones por lo que hacen, no por cómo están implementadas. Definir estructuras de datos sin operaciones. Ignorar el comportamiento de las funciones. Especificar únicamente el código fuente.

¿Qué es un Tipo Abstracto de Datos (TAD)?. Una colección de datos con operaciones y propiedades definidas por una especificación. Una estructura concreta de memoria. Un tipo básico del lenguaje. Un algoritmo de ordenación.

¿Qué aporta la abstracción de datos a la máquina virtual del lenguaje?. La extensión con nuevos tipos de datos. La eliminación de tipos primitivos. La optimización automática del código. La independencia total del hardware.

¿Qué es la ocultación de información y por qué es importante?. Separar interfaz e implementación para reducir acoplamiento. Evitar que el programa se ejecute. Ocultar errores al usuario. Eliminar documentación innecesaria.

¿Qué papel cumple la interfaz de un TAD?. Actuar como contrato entre el diseñador y el usuario. Implementar los algoritmos internos. Gestionar la memoria dinámica. Optimizar el tiempo de ejecución.

¿Qué significa independencia de la representación en un TAD?. Que su uso y especificación no dependen de cómo se implemente. Que no utiliza memoria. Que siempre se implementa con vectores. Que no tiene operaciones.

¿Qué ventajas prácticas aporta la independencia de la representación?. Permite cambiar o elegir implementaciones según requisitos de eficiencia. Elimina la necesidad de documentar el TAD. Garantiza siempre la máxima eficiencia. Obliga a usar una sola implementación.

¿Qué es un TAD genérico?. Un TAD que define una familia de tipos con comportamiento común. Un TAD sin operaciones. Un TAD solo para tipos numéricos. Un TAD dependiente del lenguaje.

¿Por qué los contenedores suelen definirse como TAD genéricos?. Porque almacenan elementos de distintos tipos sin cambiar su comportamiento. Porque solo almacenan datos simples. Porque no permiten operaciones complejas. Porque dependen de la implementación.

¿Qué es la descomposición modular y qué persigue?. Dividir el programa en módulos cohesionados y reutilizables. Unir todo el código en un único bloque. Reducir el número de funciones. Evitar el uso de TAD.

¿Qué se entiende por módulo en programación?. Una unidad que encapsula datos y operaciones y controla su visibilidad. Un archivo con código fuente sin restricciones. Una función recursiva. Un tipo primitivo del lenguaje.

¿Cómo se encapsula un TAD en lenguajes orientados a objetos?. Mediante clases. Mediante funciones globales. Mediante macros. Mediante variables públicas.

¿En qué se diferencian encapsulamiento y ocultación de información?. Encapsular agrupa; ocultar decide qué se muestra. Son exactamente lo mismo. Encapsular es solo para datos; ocultar solo para funciones. Ocultar agrupa; encapsular elimina información.

¿Qué incluye la especificación de un TAD?. El dominio de datos y la descripción de sus operaciones. El código fuente completo. El lenguaje de implementación. El consumo de memoria exacto.

¿Qué diferencia hay entre especificación sintáctica y semántica?. La sintáctica indica cómo usar operaciones; la semántica qué hacen. La sintáctica mide el tiempo; la semántica el espacio. La semántica describe la sintaxis del lenguaje. No existe diferencia real.

¿Cómo se expresa la semántica de las operaciones en la especificación de un TAD?. Mediante precondiciones y postcondiciones. Mediante código ejecutable. Mediante comentarios informales. Mediante pruebas empíricas.

¿Qué criterios guían la selección de operaciones de un TAD?. Que sean básicas, completas y permitan generar todo el dominio. Que sean muchas y variadas. Que dependan del hardware. Que optimicen solo el tiempo.

¿Cómo se clasifican las operaciones de un TAD?. En constructoras, destructoras, observadoras y modificadoras. En públicas y privadas. En recursivas e iterativas. En simples y complejas.

¿Qué implica implementar un TAD?. Elegir una representación y algoritmos que cumplan la especificación. Cambiar la especificación original. Eliminar la abstracción. Definir solo la interfaz.

¿Cuál es la diferencia entre un TAD y una estructura de datos?. El TAD es el modelo conceptual; la estructura es su implementación. Son exactamente lo mismo. La estructura es abstracta y el TAD concreto. El TAD solo existe en teoría.

¿Cómo se clasifican las estructuras de datos según su gestión de memoria?. Estáticas, pseudoestáticas y dinámicas. Simples y compuestas. Lineales y no lineales. Públicas y privadas.

¿Qué criterio principal guía la elección de la estructura de datos?. La eficiencia en tiempo y espacio según la aplicación. El lenguaje de programación usado. La facilidad de implementación únicamente. El número de operaciones disponibles.

¿Cuál es el proceso general de programación basada en TAD?. Identificar TAD, especificarlos, programar con ellos y luego implementarlos. Implementar primero y especificar después. Programar sin abstracción previa. Optimizar antes de diseñar.

¿Cuál es el principal beneficio de programar utilizando TADs y modularización?. Reducir la complejidad separando diseño e implementación. Eliminar completamente los errores. Aumentar el número de líneas de código. Evitar el uso de algoritmos.

¿Cómo se define conceptualmente un número racional en el TAD racional?. Como una clase de fracciones equivalentes con un representante canónico. Como dos enteros almacenados sin restricciones. Como un número real aproximado. Como una fracción cualquiera sin normalizar.

¿Qué garantiza el constructor del TAD racional?. Que el racional queda en forma irreducible y con denominador positivo. Que el número sea entero. Que el valor sea aproximado. Que el denominador sea siempre 1.

¿Por qué el uso del TAD racional no depende de su implementación interna?. Porque solo se interactúa mediante su interfaz especificada. Porque no usa memoria dinámica. Porque siempre se implementa igual. Porque el compilador lo optimiza.

¿Qué es un Tipo Abstracto de Datos (TAD) y qué lo diferencia de una estructura concreta?. Un TAD define qué operaciones se pueden hacer y su comportamiento, no cómo se implementan. Un TAD describe la forma exacta en memoria de una estructura de datos. Un TAD es una implementación concreta optimizada de una estructura. Un TAD es un conjunto de algoritmos ligados a un lenguaje específico.

¿Por qué un TAD separa interfaz y representación interna?. Para permitir cambiar la implementación sin afectar al uso. Para reducir el número de operaciones disponibles. Para mejorar únicamente la eficiencia temporal. Para evitar el uso de memoria dinámica.

¿Qué elementos definen formalmente un TAD?. El conjunto de valores y el conjunto de operaciones sobre ellos. El código fuente y la estructura interna. El lenguaje de programación y el compilador. Las estructuras de datos y los algoritmos asociados.

¿Por qué una misma estructura puede implementar distintos TAD?. Porque la estructura es la implementación, no la abstracción. Porque todos los TAD son equivalentes. Porque una estructura solo puede usarse de una forma. Porque los TAD dependen del lenguaje.

¿Qué es una pila y cuál es su política de acceso a los elementos?. Es un TAD LIFO: último en entrar, primero en salir. Es una estructura FIFO con acceso por ambos extremos. Es una lista con acceso aleatorio. Es una secuencia ordenada automáticamente.

¿Cuáles son las operaciones fundamentales de una pila y qué hacen?. push inserta, pop elimina el elemento superior, top lo consulta. insertar añade al final, borrar elimina cualquiera, buscar consulta. push elimina, pop inserta y top borra. crear, destruir y recorrer.

¿Por qué en una pila solo se accede a un único elemento?. Porque el acceso está restringido al elemento del tope. Porque los demás elementos no existen en memoria. Porque la pila no almacena más de un elemento. Porque los elementos están ordenados.

¿Qué condiciones provocan desbordamiento y subdesbordamiento en una pila?. Desbordamiento al insertar llena; subdesbordamiento al extraer vacía. Desbordamiento al extraer llena; subdesbordamiento al insertar vacía. Desbordamiento al acceder al tope; subdesbordamiento al recorrer. Desbordamiento por recursión; subdesbordamiento por iteración.

¿Qué diferencias conceptuales hay entre implementar una pila con arrays o con listas enlazadas?. Arrays tienen tamaño fijo; listas permiten tamaño dinámico. Arrays son dinámicos; listas tienen tamaño fijo. Arrays no permiten push ni pop. Listas enlazadas no permiten acceso al tope.

¿Cuál es el coste temporal típico de las operaciones básicas de una pila y por qué?. O(1), porque no dependen del número de elementos. O(n), porque recorren toda la pila. O(log n), porque dividen el problema. O(n²), por los desplazamientos internos.

¿Por qué la pila es adecuada para gestionar llamadas a funciones o recursión?. Porque respeta el orden LIFO de activación y finalización. Porque permite acceso aleatorio a los marcos de activación. Porque reduce el uso de memoria. Porque elimina la necesidad de parámetros.

¿Por qué una pila no es adecuada para búsquedas arbitrarias?. Porque no permite acceso directo a elementos internos. Porque no almacena suficientes elementos. Porque sus operaciones son costosas. Porque solo funciona con datos numéricos.

¿Qué es el TAD Cola y qué tipo de situaciones reales modela correctamente?. Un TAD FIFO que modela colas de espera, impresión, planificación y procesamiento secuencial. Un TAD LIFO que modela llamadas a funciones y recursión. Una estructura con acceso aleatorio usada para búsquedas. Un TAD exclusivo para estructuras circulares.

¿Cuál es la política de acceso de una cola y en qué se diferencia de una pila?. Es FIFO (First In, First Out); la pila es LIFO. Es LIFO (Last In, First Out); la pila es FIFO. Ambas usan FIFO pero con distintos extremos. Ambas usan acceso aleatorio.

¿Existe una posición fija obligatoria para el frente y el final de una cola?. No, es una convención de implementación, no del TAD. Sí, el frente debe estar siempre en la posición 0. Sí, el final debe coincidir con el último índice del vector. Depende del lenguaje de programación.

¿Por qué la implementación vectorial circular es preferible a la vectorial lineal?. Porque evita desplazamientos y mantiene todas las operaciones en O(1). Porque elimina la necesidad de conocer el tamaño máximo. Porque usa menos memoria que cualquier otra implementación. Porque simplifica el acceso al frente.

¿Qué se debe conocer al usar una representación pseudoestática de una cola?. El número máximo de elementos que puede almacenar. El número mínimo de elementos que contendrá. El orden de llegada exacto de los elementos. El tiempo de ejecución de las operaciones.

¿Por qué una cola enlazada necesita dos punteros (inicio y fin)?. Para permitir inserción y borrado en O(1) en ambos extremos. Para recorrer la cola en ambos sentidos. Para reducir el consumo de memoria. Para evitar el uso de nodos dinámicos.

¿El TAD Cola enlazado utiliza nodo cabecera?. No, usa directamente punteros a inicio y fin. Sí, siempre necesita un nodo cabecera. Solo si la cola es circular. Depende del tamaño de la cola.

¿Existe el TAD Cola Circular como TAD distinto?. No, solo existe la representación circular del TAD Cola estándar. Sí, es un TAD diferente con operaciones propias. Sí, pero solo para colas vectoriales. Depende de la implementación.

¿Por qué en una cola vectorial circular puede quedar una posición sin usar?. Para distinguir entre cola llena y vacía si no se usa contador. Porque esa posición es inaccesible. Para mejorar la eficiencia temporal. Porque el vector no se llena completamente.

¿Qué TAD es adecuado para procesar elementos en orden inverso al de llegada?. El TAD Pila, no la Cola. El TAD Cola circular. El TAD Lista. Cualquiera de ellos indistintamente.

¿Desde el punto de vista del espacio, cuándo es mejor una cola vectorial que una enlazada?. Cuando se prioriza eficiencia espacial y se conoce el tamaño máximo. Cuando el tamaño es totalmente impredecible. Cuando se insertan y eliminan muchos elementos. Cuando se necesita capacidad ilimitada.

¿Es obligatorio implementar una cola con vector o con lista doblemente enlazada?. No, basta una lista simplemente enlazada con dos punteros. Sí, es obligatorio usar lista doblemente enlazada. Sí, solo puede implementarse con vector. Depende del TAD utilizado.

¿Por qué una cola con prioridad no se implementa eficientemente con una cola simple?. Porque no permite insertar elementos según prioridad. Porque no permite eliminar elementos. Porque no respeta el orden FIFO. Porque consume demasiada memoria.

¿En qué se parecen y en qué se diferencian las operaciones básicas de pilas y colas?. Son similares, pero la cola opera en dos extremos y la pila en uno solo. Son idénticas tanto en nombre como en funcionamiento. La pila opera en dos extremos y la cola en uno. No comparten ninguna operación básica.

¿Puede implementarse una pila usando una cola o viceversa sin estructuras auxiliares?. No, porque FIFO y LIFO tienen especificaciones incompatibles. Sí, siempre que se use recursión. Sí, cambiando el orden de inserción. Depende del número de elementos.

¿Existe el “TAD Lista simplemente enlazada” o “TAD Lista doblemente enlazada” como TAD distintos?. No, existe el TAD Lista; lo demás son implementaciones. Sí, son TAD diferentes con operaciones distintas. Depende del lenguaje de programación. Solo si la lista es circular.

¿De qué depende el coste de la operación anterior() en el TAD Lista?. De la representación usada, no del TAD en sí. Del número de elementos almacenados. Del tipo de datos de la lista. De si la lista está ordenada.

¿Por qué la operación anterior() es O(n) en una lista simplemente enlazada, incluso con nodo cabecera?. Porque hay que recorrer la lista desde el inicio para encontrar el nodo previo. Porque no existe puntero al nodo actual. Porque el nodo cabecera añade coste extra. Porque la lista no está ordenada.

¿Por qué no puede justificarse anterior() como O(1) solo por tener un puntero físico al nodo previo?. Porque la operación lógica sigue requiriendo acceso secuencial. Porque los punteros no cuentan como acceso directo. Porque el TAD prohíbe el uso de punteros. Porque el acceso físico no influye en la complejidad.

¿Cuándo puede implementarse buscar() en tiempo O(log n) en el TAD Lista?. Solo con representación vectorial y acceso aleatorio. En cualquier lista enlazada ordenada. Siempre que la lista esté ordenada. Solo en listas doblemente enlazadas.

¿Por qué una lista enlazada ordenada no permite búsqueda logarítmica?. Porque no tiene acceso directo al elemento medio. Porque el orden impide dividir el problema. Porque la lista no tiene tamaño fijo. Porque las comparaciones son costosas.

¿En qué representaciones del TAD Lista puede implementarse fin() en O(1)?. En vectorial y en enlazada si se mantiene un puntero al último nodo. Solo en representación vectorial. Solo en listas doblemente enlazadas. En ninguna representación.

¿Existe alguna representación enlazada del TAD Lista donde fin() no pueda ser O(1)?. No, puede lograrse con puntero al último o con lista circular/doblemente enlazada. Sí, en listas simplemente enlazadas sin nodo cabecera. Sí, en listas ordenadas. Depende del tamaño de la lista.

¿Existen las posiciones inicio() y fin() en el TAD Lista Circular?. No, conceptualmente no existen; es una estructura sin extremos definidos. Sí, siempre existen pero apuntan al mismo nodo. Solo existe inicio(), no fin(). Depende de la implementación concreta.

¿El hecho de que una lista esté ordenada mejora el orden de complejidad de la búsqueda?. No, sigue siendo O(n), aunque el promedio pueda parar antes. Sí, pasa a ser O(log n). Sí, pasa a ser O(1). Solo en listas doblemente enlazadas.

¿Por qué la elección entre lista simple y doble depende del uso de ciertas operaciones?. Porque operaciones como anterior() o borrado intermedio son más eficientes en doblemente enlazada. Porque las listas simples no permiten borrado. Porque las listas dobles usan menos memoria. Porque las listas simples son más rápidas siempre.

¿Pilas y Colas permiten acceso O(1) a cualquier elemento si contienen los mismos datos?. No, sólo permiten acceso restringido a sus extremos. Sí, si se conoce la posición del elemento. Sí, porque son estructuras lineales. Depende de la implementación.

¿En qué se diferencian estructuralmente Pila y Cola si se analizan sus operaciones básicas?. Son similares, pero la Pila opera en un extremo y la Cola en dos opuestos. La Cola opera en un extremo y la Pila en dos. Ambas operan exactamente igual. No se diferencian en nada.

¿Puede implementarse una Pila a partir de una Bicola restringiendo su uso?. Sí, usando un solo extremo se comporta como una Pila. No, porque una Bicola es FIFO. Solo si se usa una estructura auxiliar. Depende del número de elementos.