Bloque 2 Tema 3 Informática Básica - TAI

¿Cuál de las siguientes afirmaciones define mejor el concepto de Tipo Abstracto de Datos (TAD)?. Una estructura de datos basada únicamente en punteros y memoria dinámica para almacenar elementos. Un tipo de dato primitivo propio del lenguaje de programación que no admite modificación. Una especificación de un conjunto de datos y las operaciones permitidas sobre ellos, independiente de su implementación. Un algoritmo optimizado para la búsqueda rápida de elementos en un conjunto ordenado.

¿Qué disciplina de acceso caracteriza a una estructura de datos tipo Pila (Stack)?. Acceso aleatorio por índice. FIFO (First In, First Out). LIFO (Last In, First Out). LILO (Last In, Last Out).

En una Lista Doblemente Enlazada, ¿cuál es la principal ventaja respecto a una Lista Simplemente Enlazada?. Reduce a la mitad el consumo global de memoria por cada nodo almacenado. Elimina la necesidad de controlar los casos en los que la lista queda vacía. Garantiza un tiempo de acceso aleatorio a cualquier elemento mediante índice en O(1). Permite la navegación y el recorrido bidireccional de los nodos de manera eficiente.

Si se desea implementar el mecanismo de 'Deshacer/Rehacer' (Undo/Redo) en un editor de texto, ¿qué combinación de estructuras de datos es la más adecuada?. Dos colas. Una cola de prioridad. Dos pilas. Una lista simplemente enlazada y un array.

¿Qué ocurre si se intenta realizar una operación 'Desapilar' (Pop) o 'Desencolar' (Dequeue) sobre una Pila o Cola que está completamente vacía?. La operación se transforma automáticamente en una inserción (Push/Enqueue). La estructura añade automáticamente un elemento nulo para evitar fallos. Se produce una condición de error por Subdesbordamiento (Underflow). Se produce una condición de error por Sobredesbordamiento (Overflow).

¿Qué nombre recibe la operación elemental de una Pila (Stack) que permite examinar el elemento del tope sin modificar la estructura?. Top. Enqueue. Push. Pop.

¿Cuál es la característica principal que distingue a una Bicola o Cola Doblemente Terminada (Deque)?. Organiza sus elementos automáticamente según una prioridad numérica asociada. Permite inserciones por un extremo y extracciones por ambos extremos exclusivamente. Permite realizar inserciones y eliminaciones por cualquiera de sus dos extremos. Mantiene sus elementos organizados en una estructura completamente circular en memoria.

En la taxonomía de listas, ¿qué distingue fundamentalmente a una Lista Circular de una Lista Lineal estándar?. Solo permite el acceso y eliminación de elementos por un único extremo. El puntero del último nodo apunta hacia el primer nodo en lugar de ser nulo. Cada nodo posee dos punteros directos hacia sus nodos adyacentes anterior y posterior. Todos los elementos almacenados deben estar ordenados de forma ascendente obligatoriamente.

En una Cola con Prioridad (Priority Queue), ¿cómo se determina el orden de salida de los elementos?. En orden inverso a su inserción (disciplina LIFO). De manera aleatoria mediante una función de dispersión hashing. En función de una clave o valor numérico asignado a cada elemento. Estrictamente por el orden cronológico de llegada (disciplina FIFO).

¿Cuáles son los términos estándar para denotar las operaciones de inserción y extracción en una Cola lineal básica?. Insert para la inserción y Remove para la extracción. Append para la inserción y Splice para la extracción. Enqueue para la inserción y Dequeue para la extracción. Push para la inserción y Pop para la extracción.

¿Qué caracteriza a una Lista Doblemente Enlazada respecto a sus componentes estructurales básicos?. Contiene un único puntero de cabecera que apunta simultáneamente a dos nodos. Los nodos están contiguos físicamente en las direcciones de memoria principal. Cada nodo contiene el dato y dos punteros: uno al nodo siguiente y otro al anterior. Cada nodo contiene dos campos de datos independientes y un puntero único.

¿Cómo se define el comportamiento de acceso LIFO en el contexto de una Pila?. El primer elemento en ingresar es el primero en ser procesado y extraído. El último elemento en ingresar es el primero en ser procesado y extraído. El elemento de menor valor numérico es extraído de forma prioritaria. Los elementos se extraen según su posición arbitraria mediante un índice entero.

¿Cuál de las siguientes afirmaciones define formalmente la propiedad fundamental de un Árbol Binario de Búsqueda (ABB)?. La diferencia de altura entre el subárbol izquierdo y derecho de cualquier nodo es de máximo 1. Cada nodo no hoja contiene al menos dos claves y un número variable de hijos según su profundidad. Para todo nodo N, las claves de su subárbol izquierdo son menores que la clave de N, y las del derecho son mayores. Todos los niveles del árbol están completamente llenos excepto posiblemente el último nivel.

En la teoría de árboles generales, ¿cómo se define la 'altura' de un árbol?. El número total de nodos que componen la estructura jerárquica. El número máximo de hijos que puede tener cualquier nodo del árbol. La longitud del camino más largo desde la raíz hasta cualquiera de sus hojas. La cantidad de nodos hoja que carecen de descendientes directos.

¿Qué condición de balance estricta exige un Árbol AVL para garantizar su equilibrio?. El factor de equilibrio de cada nodo, FE = h_{der} - h_{izq}, debe ser -1, 0 o 1. Todos los caminos desde un nodo raíz hasta las hojas deben contener la misma cantidad de nodos negros. La altura del árbol no debe superar la cantidad de log_2(n) bajo ninguna circunstancia. El subárbol izquierdo debe poseer la misma cantidad exacta de nodos que el subárbol derecho.

En un Árbol Rojo-Negro, ¿cuál de las siguientes propiedades sobre la coloración de sus nodos es OBLIGATORIA?. Todas las hojas nulas (hojas NIL) se consideran de color rojo. Si un nodo es rojo, entonces ambos hijos deben ser negros. Si un nodo es negro, necesariamente sus dos hijos deben ser de color rojo. La raíz del árbol puede ser indistintamente roja o negra según la paridad del número de nodos.

¿Cómo se define un Árbol B de orden m en la categoría de árboles multicamino?. Un árbol de búsqueda balanceado donde cada nodo interno tiene como máximo m hijos. Un árbol en el que todos los nodos deben tener exactamente m claves almacenadas obligatoriamente. Un árbol binario que almacena hasta m valores repetidos en su estructura de hojas. Una estructura jerárquica no balanceada donde el grado de cada nodo crece linealmente con la altura.

¿Cuál es la diferencia estructural fundamental entre un Árbol B y un Árbol B+?. En el Árbol B+, los datos reales se almacenan únicamente en las hojas, y las hojas forman una lista enlazada. El Árbol B requiere equilibrar la altura mediante rotaciones, mientras que el Árbol B+ nunca requiere reequilibrio. En el Árbol B+, todas las claves se mantienen almacenadas exclusivamente en los nodos internos superiores. El Árbol B permite nodos con un número variable de hijos, mientras que el Árbol B+ es estrictamente binario.

¿Qué caracteriza a un Árbol Binario Lleno (Full Binary Tree)?. La altura de todas sus hojas difiere en como máximo un nivel de profundidad. Todo nodo tiene exactamente 0 o 2 hijos. Todos los niveles están completamente ocupados de nodos sin excepción. Cada nodo tiene un número de hijos igual al nivel de profundidad en el que reside.

En la teoría de árboles Rojo-Negro, ¿qué representa la propiedad de la 'Altura Negra' (bh)?. La profundidad máxima que puede alcanzar un camino compuesto únicamente por nodos rojos. El nivel absoluto donde se encuentra el primer nodo de color negro empezando por la raíz. El número de nodos negros en cualquier camino simple desde un nodo hasta una hoja descendiente. La proporción porcentual entre el número total de nodos negros y rojos del árbol.

¿Cuál es la diferencia estructural fundamental que distingue a un Árbol de un Grafo general?. Un árbol almacena elementos en orden lineal mientras que un grafo utiliza matrices tridimensionales. Un grafo siempre es ponderado mientras que los árboles no admiten pesos en sus aristas. Un árbol permite múltiples ciclos orientados mientras que un grafo prohíbe las conexiones múltiples. Un árbol es un grafo no dirigido, conexo y acíclico con un único camino entre cualquier par de vértices.