Tipos abstractos y Estructuras de datos. Organizaciones de ficheros. Algoritmos. Formatos de información y ficheros.

Tema desarrollado para el ejercicio único del Cuerpo de Técnicos Auxiliares de Informática de la Administración del Estado. Es el tema 3 del bloque II «Tecnología básica», que en nuestra numeración interna es el tema 12 de 33.

Cuánto pesa y cómo pregunta. Del bloque II salen 14 preguntas y este tema aporta dos: en mayo de 2026 fueron el formato CSV y el formato JSON, las dos citando la RFC por su número. Pero su alcance real es mayor de lo que ese dos sugiere, porque las estructuras de datos y los algoritmos reaparecen en el bloque III, en las preguntas de desarrollo, y en los supuestos prácticos. Contando todo, el tribunal ha preguntado aquí por árboles rojo-negro, árboles 2-3-4, recorridos en preorden, número máximo de nodos, algoritmos de ordenación lineales, el algoritmo de Dijkstra y las reglas de XML.

El patrón es el de siempre en la parte técnica: cita la norma por su número —RFC 4180, RFC 8259, la recomendación XML del W3C— y pide una regla exacta de ella. Este apunte va, por tanto, con la regla literal delante.

Índice

1. Tipos abstractos y estructuras de datos
   • Qué es un tipo abstracto de datos
   • Estructuras lineales: array, lista, pila y cola
   • Árboles
   • Árboles equilibrados: AVL, rojo-negro, 2-3-4 y B
   • Tablas hash
   • Grafos
2. Organizaciones de ficheros
   • Registros, campos, claves y las cuatro organizaciones
   • Los ficheros según su papel y las copias de seguridad
3. Algoritmos
   • Qué es un algoritmo y cómo se representa
   • La complejidad y la notación O
   • Algoritmos de ordenación
   • Búsqueda y recursividad
   • Algoritmos sobre grafos
   • Estrategias de diseño
   • Los límites de lo que se puede calcular
4. Formatos de información y ficheros
   • CSV, según la RFC 4180
   • JSON, según la RFC 8259
   • XML y su familia
   • Formatos ofimáticos y de documento
   • Compresión
   • Serialización, Base64 y los tipos MIME
   • Los formatos de la administración electrónica
5. Cuadros para memorizar
6. Lo que ya ha preguntado el tribunal

1. Tipos abstractos y estructuras de datos

1.1. Qué es un tipo abstracto de datos

Un tipo abstracto de datos (TAD) es la definición de un conjunto de valores y de las operaciones que se pueden hacer con ellos, sin decir cómo están implementados por dentro. Una estructura de datos es, precisamente, una implementación concreta de un TAD.

La diferencia es la clave del epígrafe y se explica con un ejemplo: la pila es un TAD —dice que se puede apilar, desapilar y consultar la cima, y que el último en entrar es el primero en salir— y ese TAD puede implementarse con un array o con una lista enlazada. Quien la usa no necesita saber cuál de las dos hay debajo.

Esa separación se llama encapsulamiento u ocultación de la información, y aporta tres cosas: se puede cambiar la implementación sin tocar el código que la usa, se reduce el acoplamiento y se puede razonar sobre la corrección del programa a partir del contrato del TAD.

Las estructuras se clasifican en dos grandes familias:

• Lineales: cada elemento tiene un antecesor y un sucesor a lo sumo. Arrays, listas, pilas, colas.
• No lineales: un elemento puede tener varios sucesores. Árboles y grafos. También se cuentan aquí las tablas hash, que son de acceso directo.

Y en estáticas (su tamaño se fija al crearlas, como el array) frente a dinámicas (crecen y menguan durante la ejecución, como la lista enlazada).

1.2. Estructuras lineales: array, lista, pila y cola

Estructura	Cómo funciona	Coste de acceso
Array o vector	Posiciones contiguas en memoria, todas del mismo tipo, accesibles por índice	Acceso directo en O(1); insertar o borrar en medio cuesta O(n) porque hay que desplazar
Lista enlazada	Nodos dispersos, cada uno con el dato y un puntero al siguiente	Insertar y borrar en O(1) si se tiene el nodo; acceder al elemento i cuesta O(n), porque hay que recorrer
Pila (stack)	LIFO: el último en entrar es el primero en salir. Operaciones: apilar, desapilar y consultar la cima	Todas en O(1)
Cola (queue)	FIFO: el primero en entrar es el primero en salir. Operaciones: encolar y desencolar	Todas en O(1)

Dos variantes que se preguntan: la lista doblemente enlazada, en la que cada nodo apunta al siguiente y al anterior y por tanto se puede recorrer en los dos sentidos; y la lista circular, en la que el último apunta al primero.

De la cola, dos variantes más: la cola circular, que reaprovecha las posiciones liberadas de un array, y la cola de prioridad, en la que no sale el primero que llegó sino el más urgente, y que se implementa normalmente con un montículo (heap).

Dónde aparecen en la práctica, que es lo que ayuda a recordar cuál es cuál: la pila es la estructura de las llamadas a función —de ahí la pila de llamadas y el desbordamiento de pila de una recursión mal parada—, de la operación «deshacer» y del recorrido en profundidad. La cola es la de la impresión, la de los mensajes y la del recorrido en anchura.

1.3. Árboles

Un árbol es una estructura jerárquica de nodos donde cada nodo tiene un padre —salvo la raíz, que no tiene ninguno— y cero o más hijos. Los nodos sin hijos son hojas; los que tienen hijos, nodos internos.

Vocabulario que el tribunal usa en los enunciados:

• Grado de un nodo: su número de hijos. Grado del árbol: el mayor de todos.
• Nivel o profundidad: la distancia a la raíz. ⚠ Ojo, porque hay dos convenios: unos cuentan la raíz como nivel 0 y otros como nivel 1. El tribunal usó el convenio de raíz = nivel 1, y lo dijo expresamente en el enunciado.
• Altura: el nivel más profundo que alcanza el árbol.
• Subárbol: cualquier nodo con todos sus descendientes.

Un árbol binario es aquel en el que ningún nodo tiene más de dos hijos, llamados izquierdo y derecho. Dos cifras que hay que saberse:

• El número máximo de nodos en un nivel i (contando la raíz como nivel 1) es 2 elevado a i−1.
• El número máximo de nodos de un árbol binario de h niveles es 2 elevado a h, menos 1. Con 4 niveles: 2⁴ − 1 = 15 nodos. Es exactamente la pregunta que cayó en la convocatoria extraordinaria de 2026.

Un árbol binario de búsqueda (ABB) añade una regla: en todo nodo, los valores del subárbol izquierdo son menores y los del derecho, mayores. Eso permite buscar dividiendo el problema por la mitad en cada paso, en O(log n)… siempre que el árbol esté equilibrado. Si los datos entran ya ordenados, el ABB degenera en una lista y el coste se desploma a O(n): ese es justo el motivo por el que existen los árboles equilibrados del apartado siguiente.

Los recorridos, que son pregunta segura

Recorrer un árbol es visitar todos sus nodos en algún orden. Hay tres recorridos en profundidad y uno en anchura, y la diferencia entre los tres primeros está solo en cuándo se visita la raíz:

Recorrido	Orden de las operaciones	Para qué sirve
Preorden	Raíz, subárbol izquierdo, subárbol derecho	Copiar o serializar el árbol conservando su forma
Inorden	Subárbol izquierdo, raíz, subárbol derecho	En un árbol binario de búsqueda, devuelve los valores ordenados de menor a mayor
Postorden	Subárbol izquierdo, subárbol derecho, raíz	Liberar memoria o evaluar expresiones, porque procesa los hijos antes que el padre
Por niveles (anchura)	Todos los nodos de un nivel antes de pasar al siguiente	Se implementa con una cola, no con recursión

⚠ Truco para no fallarlo: el nombre dice dónde va la raíz. Preorden, la raíz antes; inorden, la raíz en medio; postorden, la raíz después. El subárbol izquierdo siempre va antes que el derecho. El tribunal preguntó el preorden en 2026 y la respuesta era, literalmente, «visitar el nodo raíz, recorrer el subárbol izquierdo y recorrer el subárbol derecho».

1.4. Árboles equilibrados: AVL, rojo-negro, 2-3-4 y B

Todos resuelven el mismo problema —que el árbol de búsqueda no degenere— con reglas distintas, y el tribunal ha preguntado por tres de ellos.

Árbol	Su regla
AVL	Para cada nodo, la diferencia de altura entre sus dos subárboles (el factor de equilibrio) no puede pasar de 1. Es el más estrictamente equilibrado, así que busca muy rápido pero reequilibra mucho al insertar
Rojo-negro	Cada nodo es rojo o negro, con cuatro reglas (abajo). Equilibra menos que el AVL pero hace menos rotaciones, y por eso es el que llevan dentro muchas bibliotecas estándar
2-3-4	Cada nodo puede tener 2, 3 o 4 hijos (2-nodo, 3-nodo o 4-nodo), y todas las hojas están al mismo nivel. Es un caso particular de árbol B de orden 4
B y B+	Muchos hijos por nodo, todas las hojas al mismo nivel. Están pensados para disco: cada nodo ocupa un bloque, de modo que se minimiza el número de accesos. Son la estructura de los índices de las bases de datos y de muchos sistemas de ficheros

Las reglas del árbol rojo-negro, porque el tribunal pidió cuál era correcta y las tres falsas eran versiones retorcidas de estas mismas:

1. Todo nodo es rojo o negro.
2. La raíz es negra. Esta fue la respuesta correcta en 2026.
3. Si un nodo es rojo, sus dos hijos son negros (no puede haber dos rojos seguidos). Cuidado: el distractor decía «sus hijos son rojos».
4. Para cada nodo, todos los caminos de ese nodo a sus hojas descendientes contienen el mismo número de nodos NEGROS. Cuidado otra vez: el distractor decía «la misma cantidad de nodos rojos».

Y del 2-3-4, lo que el tribunal dio por bueno en 2024: los nodos pueden tener 2, 3 o 4 hijos. Las falsas eran que cumple las propiedades del árbol binario de búsqueda (no: no es binario), que las hojas pueden estar a distinto nivel (no: están todas al mismo) y que las reestructuraciones van de las hojas a la raíz (en el 2-3-4 se hacen de arriba abajo al descender).

1.5. Tablas hash

Una tabla hash guarda pares clave-valor y calcula, con una función resumen (hash), la posición donde va cada clave. Su gracia es que el acceso es O(1) en el caso medio, sin recorrer nada.

El problema son las colisiones: dos claves distintas que caen en la misma posición. Son inevitables, porque hay muchas más claves posibles que posiciones. Dos formas de resolverlas:

• Encadenamiento (hashing abierto): en cada posición hay una lista con todas las claves que caen ahí.
• Direccionamiento abierto: se busca otra posición libre siguiendo una regla —lineal, cuadrática o con un segundo hash—.

El factor de carga es la proporción entre elementos guardados y posiciones disponibles. Cuando sube demasiado, las colisiones se disparan y el coste medio se degrada hacia O(n); por eso las implementaciones redimensionan la tabla y recolocan todo (rehashing) al pasar de cierto umbral.

⚠ Una tabla hash no mantiene ningún orden. Si hace falta recorrer las claves ordenadas, la estructura correcta es un árbol de búsqueda, no una tabla hash.

Otras estructuras que conviene tener nombradas

Estructura	Qué garantiza	Dónde se usa
Montículo (heap)	Un árbol binario casi completo en el que todo padre es mayor —o menor— que sus hijos. La raíz es siempre el máximo (o el mínimo)	Colas de prioridad y el algoritmo heapsort. Extraer el máximo cuesta O(log n)
Conjunto (set)	Colección sin elementos repetidos y sin orden garantizado	Comprobar pertenencia; unión, intersección y diferencia
Diccionario o mapa	Asociación clave → valor, con claves únicas	Es el TAD; la tabla hash y el árbol de búsqueda son dos implementaciones suyas
Matriz	Array de dos o más dimensiones	Cálculo, imágenes, matrices de adyacencia. Si está casi vacía se guarda como matriz dispersa, listando solo los elementos no nulos
Trie o árbol de prefijos	Cada camino desde la raíz deletrea una clave	Autocompletado y diccionarios de palabras

Y una aclaración de vocabulario que se presta a trampa: «diccionario» es el TAD y «tabla hash» es una implementación. Un diccionario puede estar implementado con un árbol de búsqueda, y entonces sí mantiene el orden de las claves, a costa de que el acceso pase de O(1) a O(log n).

1.6. Grafos

Un grafo es un conjunto de vértices (o nodos) unidos por aristas. Es la estructura más general: un árbol es un caso particular de grafo (conexo y sin ciclos).

• Dirigido (las aristas tienen sentido) o no dirigido.
• Ponderado si cada arista lleva un peso o coste; es lo que permite hablar del camino «más corto» y no solo del más corto en número de saltos.
• Conexo si desde cualquier vértice se puede llegar a cualquier otro.
• Cíclico o acíclico. Un grafo dirigido acíclico se abrevia DAG, y es la estructura de las dependencias entre tareas.

Dos formas de representarlo en memoria, con un compromiso claro:

Representación	Cómo es	Cuándo conviene
Matriz de adyacencia	Una tabla n × n donde la casilla (i, j) dice si hay arista	Grafos densos. Comprobar si dos vértices están unidos es O(1), pero ocupa n² siempre
Lista de adyacencia	Para cada vértice, la lista de sus vecinos	Grafos dispersos, que son la mayoría. Ocupa proporcionalmente a las aristas que hay de verdad

Y dos recorridos, que se distinguen por la estructura auxiliar que usan:

• En profundidad (DFS): se hunde por una rama hasta el final antes de retroceder. Usa una pila, o la recursión, que es una pila disfrazada.
• En anchura (BFS): visita todos los vecinos antes de bajar un nivel. Usa una cola, y encuentra el camino con menos saltos en un grafo sin pesos.

Elegir la estructura: el cuadro que resume el tema

Toda la primera parte del tema se condensa en una pregunta práctica: ¿cuál elijo?. La respuesta depende de qué operación se va a hacer más veces.

Estructura	Buscar	Insertar	Borrar	¿Mantiene orden?
Array sin ordenar	O(n)	O(1) al final	O(n)	No
Array ordenado	O(log n) (binaria)	O(n)	O(n)	Sí
Lista enlazada	O(n)	O(1) con el nodo	O(1) con el nodo	Solo si se mantiene
Árbol equilibrado	O(log n)	O(log n)	O(log n)	Sí
Tabla hash	O(1) medio	O(1) medio	O(1) medio	No

La regla de decisión sale sola del cuadro: si hace falta acceso inmediato por clave y no importa el orden, tabla hash; si hace falta recorrer en orden o consultar rangos, árbol equilibrado; si el conjunto es pequeño y se recorre entero, un array basta y sobra. Y ojo con el «O(1) medio» de la tabla hash: es una media, y con una función resumen mala o un factor de carga alto se degrada hasta O(n).

2. Organizaciones de ficheros

Un fichero es un conjunto de registros del mismo tipo guardados en un soporte permanente. Cada registro se compone de campos, y uno o varios campos forman la clave que identifica al registro.

Conviene separar dos nociones que se confunden:

• Registro lógico: la unidad con la que trabaja el programa (una ficha de personal, un asiento).
• Registro físico o bloque: la unidad que de verdad se lee del disco de una sola vez. En un bloque suelen caber varios registros lógicos, y a esa proporción se la llama factor de bloqueo.

La organización del fichero es cómo se colocan los registros en el soporte, y decide qué tipos de acceso permite. Cuatro organizaciones clásicas:

Organización	Cómo se colocan	Acceso	Ventaja e inconveniente
Secuencial	Uno detrás de otro, en el orden en que se escribieron o por clave	Solo secuencial	Aprovecha el 100 % del espacio y es óptima para procesar el fichero entero; para leer un registro concreto hay que recorrer todo lo anterior
Secuencial indexada	Los datos en secuencia, más uno o varios índices que dicen dónde está cada clave	Secuencial y directo	Lo mejor de los dos mundos; a cambio hay que mantener el índice y ocupa espacio adicional
Directa o aleatoria	La posición se calcula a partir de la clave con una función (hashing)	Solo directo	Acceso inmediato a un registro; pésima para recorrer en orden, y hay que gestionar colisiones y desbordamientos
Invertida	Se construyen índices por campos distintos de la clave	Directo por cualquiera de esos campos	Permite consultar por muchos criterios; es la organización de los buscadores documentales

El índice de un fichero secuencial indexado se implementa casi siempre con un árbol B+: sus hojas están todas al mismo nivel y encadenadas entre sí, de modo que sirve tanto para localizar una clave concreta como para recorrer un rango en orden. Es la misma estructura que usan los índices de una base de datos relacional, y por eso conviene tener clara aquí la conexión con el tema 5 del bloque.

Dos conceptos más de mantenimiento que se preguntan: la zona de desbordamiento, donde van los registros que no caben en su sitio natural, y la reorganización, el proceso periódico que reconstruye el fichero y vacía esa zona. Un fichero secuencial indexado que nunca se reorganiza va degradando su rendimiento sin que nada avise.

Las operaciones sobre un fichero

Sea cual sea la organización, el repertorio de operaciones es el mismo y conviene tenerlo enumerado, porque los enunciados lo usan:

• Creación: se reserva espacio y se define la estructura de los registros.
• Apertura y cierre: se establece y se deshace el enlace entre el programa y el fichero. Cerrar no es un formalismo: es lo que garantiza que los búferes pendientes se vuelcan al soporte.
• Consulta o lectura, alta, baja y modificación de registros.
• Recorrido completo, ordenación, fusión de dos ficheros y partición en varios.
• Reorganización: reconstruir el fichero para recuperar el espacio de las bajas y vaciar la zona de desbordamiento.

Las bajas merecen una nota, porque son un clásico: en la mayoría de las organizaciones no se borra físicamente el registro, sino que se marca como dado de baja (baja lógica). El espacio no se recupera hasta la reorganización. Eso explica dos cosas que un técnico ve a menudo: que un fichero no mengüe al borrar registros, y que los datos «borrados» sigan siendo recuperables.

Bloqueo y rendimiento

El factor de bloqueo —cuántos registros lógicos entran en un bloque físico— es la palanca de rendimiento más simple que existe. Un factor alto significa menos accesos al disco para leer lo mismo, y como el acceso al disco es varios órdenes de magnitud más lento que la memoria, la mejora es enorme. A cambio, se desperdicia el espacio sobrante del último bloque, lo que se llama fragmentación interna.

Los registros pueden ser de longitud fija —todos ocupan lo mismo, de modo que la posición del registro n se calcula multiplicando— o de longitud variable, que aprovechan mejor el espacio pero obligan a guardar la longitud de cada uno y a recorrer para localizarlos.

Los ficheros según su papel

Además de por su organización, los ficheros se clasifican por la función que cumplen dentro de una aplicación, y esta terminología aparece en los enunciados:

• Maestro: contiene los datos permanentes y actualizados de la entidad —el fichero de personal, el de terceros—. Es el que refleja la situación en cada momento.
• De movimientos o de transacciones: recoge los cambios que aún han de aplicarse al maestro (altas, bajas, modificaciones). En el proceso por lotes clásico, se acumulan movimientos y se aplican de una vez.
• Histórico: guarda los datos que ya no están activos pero deben conservarse, normalmente por obligación legal.
• De trabajo o temporal: resultados intermedios que se destruyen al terminar el proceso.
• De maniobra y de resultados: los auxiliares de un proceso concreto y su salida.

La actualización del maestro con el fichero de movimientos es el procedimiento por lotes de manual, y tiene una condición que se pregunta: los dos ficheros deben estar ordenados por la misma clave. Solo así puede recorrerse cada uno una única vez, avanzando por el que va retrasado, sin necesidad de buscar.

Las copias de seguridad

Conservar un fichero exige copiarlo, y hay tres estrategias que se distinguen por qué copian y por qué hace falta para restaurar:

Tipo	Qué copia	Para restaurar hace falta
Completa (full)	Todo, siempre	Solo la última copia. Lenta de hacer, rapidísima de restaurar
Incremental	Lo cambiado desde la última copia de cualquier tipo	La última completa y TODAS las incrementales posteriores, en orden. La más rápida de hacer y la más lenta y frágil de restaurar
Diferencial	Lo cambiado desde la última copia COMPLETA	La última completa y solo la última diferencial. Término medio: crece cada día, pero restaurar son dos pasos

⚠ La distinción entre incremental y diferencial es pregunta clásica y se falla mucho. La regla mnemotécnica: la incremental mira a la copia anterior, sea del tipo que sea, y por eso encadena; la diferencial mira siempre a la completa, y por eso solo hacen falta dos ficheros para restaurar.

A esto se le añade la regla práctica más repetida en seguridad, la 3-2-1: tres copias de los datos, en dos soportes distintos y una de ellas fuera de las instalaciones. Y la advertencia que la acompaña: una copia que no se ha probado a restaurar no es una copia.

Organización de ficheros y sistema de ficheros no son lo mismo

⚠ Una confusión frecuente que conviene cortar aquí. La organización de ficheros es cómo el programa estructura los registros dentro de un fichero. El sistema de ficheros —NTFS, ext4, FAT32— es cómo el sistema operativo organiza los ficheros dentro del soporte: directorios, permisos, tabla de asignación. Son dos niveles distintos y se estudian en temas distintos: el sistema de ficheros pertenece al tema 4 de este mismo bloque.

Hoy, además, buena parte de lo que antes se resolvía con ficheros indexados lo hace un sistema gestor de bases de datos, que aporta lo que el fichero no tiene: control de concurrencia, integridad, transacciones y un lenguaje de consulta. Los conceptos de este epígrafe siguen valiendo porque son exactamente los que el gestor implementa por dentro.

3. Algoritmos

3.1. Qué es un algoritmo y cómo se representa

Un algoritmo es una secuencia finita y ordenada de pasos no ambiguos que resuelve un problema. Sus propiedades, que se preguntan una a una:

• Finitud: termina después de un número finito de pasos. Un proceso que no termina no es un algoritmo.
• Precisión o falta de ambigüedad: cada paso está definido sin lugar a interpretación.
• Entrada: cero o más datos de partida.
• Salida: al menos un resultado. Un algoritmo que no produce nada no sirve de nada.
• Efectividad: cada operación es lo bastante básica como para poder ejecutarse.
• Independencia del lenguaje: el algoritmo es anterior al programa; el programa es su expresión en un lenguaje concreto.

Formas de representarlo:

• Pseudocódigo: lenguaje natural estructurado, con las palabras clave de las estructuras de control. Es el más usado porque se lee sin conocer ningún lenguaje.
• Diagrama de flujo u ordinograma: representación gráfica con símbolos normalizados —el óvalo para inicio y fin, el rectángulo para el proceso, el rombo para la decisión, el romboide para la entrada y la salida—.
• Diagrama de Nassi-Shneiderman u ordinograma estructurado: cajas anidadas, sin flechas, lo que impide dibujar saltos y fuerza a programar de forma estructurada.
• Tablas de decisión: para lógica con muchas condiciones combinadas; garantizan que no se olvida ningún caso.

El teorema de Böhm-Jacopini, base de la programación estructurada, demuestra que cualquier algoritmo puede escribirse combinando únicamente tres estructuras de control:

1. Secuencia: una instrucción detrás de otra.
2. Selección o alternativa: si se cumple una condición se hace una cosa y si no, otra.
3. Iteración o repetición: se repite mientras se cumpla una condición.

La consecuencia práctica del teorema es que la instrucción de salto incondicional es prescindible, y de ahí la campaña histórica contra su uso.

Lo que hay dentro de un algoritmo

Antes de las estructuras de control están los tipos de datos con los que se trabaja. Los simples o primitivos son el entero, el real, el carácter, el lógico o booleano y, en algunos lenguajes, el enumerado. Los compuestos agrupan varios: la cadena, el array, el registro o estructura (campos de tipos distintos bajo un mismo nombre) y todos los del epígrafe 1.

Y una distinción de la que salen preguntas: una variable puede cambiar de valor durante la ejecución; una constante, no. Poner los valores fijos como constantes con nombre —en vez de esparcir el número por el código— es lo que permite cambiarlos en un solo sitio.

Las estructuras de control desarrolladas:

• Selección simple: si condición entonces … fin si.
• Selección doble: si … si no … fin si.
• Selección múltiple: según el valor de una expresión, se ejecuta una rama u otra. Evita encadenar diez condiciones.
• Bucle mientras (while): comprueba la condición antes de entrar, así que puede no ejecutarse ninguna vez.
• Bucle repetir-hasta (do-while): comprueba la condición al final, así que se ejecuta al menos una vez. Esta diferencia es pregunta segura.
• Bucle para (for): se usa cuando el número de repeticiones se conoce de antemano, con una variable de control que se inicializa, se compara y se incrementa.

Un contador es una variable que se incrementa en una cantidad fija; un acumulador, una que va sumando cantidades variables; y un interruptor o bandera, una variable lógica que recuerda si algo ha ocurrido. Los tres tienen que inicializarse antes del bucle, y olvidarlo es el error más repetido de quien empieza.

Cómo se comprueba que un algoritmo es correcto

Que un algoritmo parezca razonable no basta. Hay tres niveles de comprobación:

• La prueba de escritorio o traza: se ejecuta el algoritmo a mano con unos datos concretos, anotando el valor de cada variable en cada paso. Es lenta pero descubre errores que la lectura no ve.
• La verificación formal: se demuestra matemáticamente que el algoritmo cumple su especificación, usando precondiciones (lo que debe cumplirse al entrar), postcondiciones (lo que garantiza al salir) e invariantes de bucle (lo que se mantiene cierto en cada vuelta).
• Las pruebas: ejecutar con juegos de datos elegidos. Y conviene recordar la advertencia clásica: las pruebas demuestran la presencia de errores, nunca su ausencia.

Al elegir los juegos de prueba se atiende a los casos límite, que es donde se esconden los fallos: la lista vacía, la lista de un solo elemento, el valor cero, el máximo representable, la entrada ya ordenada y la ordenada al revés.

3.2. La complejidad y la notación O

La complejidad mide cómo crecen los recursos que consume un algoritmo cuando crece el tamaño de la entrada. Se distingue la temporal (operaciones) de la espacial (memoria).

La notación O grande expresa una cota superior asintótica: describe el comportamiento en el peor caso y para entradas grandes, despreciando las constantes y los términos de menor orden. Un algoritmo que hace 3n² + 5n + 100 operaciones es O(n²), porque para n grande lo demás no importa.

Orden	Nombre	Ejemplo típico
O(1)	Constante	Acceder a un elemento de un array por su índice; apilar o desapilar
O(log n)	Logarítmica	Búsqueda binaria; buscar en un árbol equilibrado
O(n)	Lineal	Recorrer una lista; búsqueda secuencial
O(n log n)	Cuasilineal	Mergesort, heapsort y quicksort en el caso medio. Es el mejor coste posible para ordenar por comparación
O(n²)	Cuadrática	Burbuja, inserción y selección; dos bucles anidados
O(2ⁿ)	Exponencial	Explorar todos los subconjuntos. Inabordable salvo para n pequeñísimo
O(n!)	Factorial	Probar todas las permutaciones (el viajante por fuerza bruta)

Junto a la O grande se manejan la omega (Ω), que es la cota inferior, y la theta (Θ), que se usa cuando la cota superior y la inferior coinciden. El tribunal suele quedarse en la O.

Cómo se calcula el orden de un algoritmo, en la práctica

Determinar la complejidad de un fragmento no exige matemáticas: basta con contar bucles y ver cómo se relacionan.

• Una secuencia de operaciones simples —asignaciones, comparaciones, aritmética— es O(1), por muchas que sean, porque su número no depende del tamaño de la entrada.
• Un bucle que recorre los n elementos es O(n).
• Dos bucles anidados que recorren n cada uno son O(n²). Tres anidados, O(n³).
• Dos bucles consecutivos, no anidados, se SUMAN: O(n) + O(n) = O(2n) = O(n). Las constantes se desprecian, así que dos recorridos siguen siendo lineales. Este es el error más común: consecutivo suma, anidado multiplica.
• Un bucle en el que la variable de control se divide entre dos en cada vuelta es O(log n), porque el número de vueltas es el número de veces que se puede partir n por la mitad.
• Si dentro de un bucle O(n) se llama a algo O(log n), el conjunto es O(n log n).

Un ejemplo con números: un algoritmo O(n²) que tarda un segundo con 1.000 elementos tardará cien segundos con 10.000, porque el tiempo crece con el cuadrado. Uno O(n log n) pasaría de un segundo a poco más de trece. Esa es la diferencia entre un programa que aguanta el crecimiento y uno que hay que reescribir a los dos años.

Y una advertencia que el examen no suele pedir pero conviene tener: la notación O ignora las constantes, de modo que para entradas pequeñas un algoritmo de orden peor puede ser más rápido. Por eso muchas implementaciones de quicksort cambian a ordenación por inserción cuando el subarray baja de una decena de elementos.

3.3. Algoritmos de ordenación

Algoritmo	Cómo funciona	Complejidad media	Peor caso
Burbuja	Compara pares adyacentes y los intercambia; los mayores «flotan» al final	O(n²)	O(n²)
Selección	Busca el mínimo y lo pone en su sitio; repite con el resto	O(n²)	O(n²)
Inserción	Va insertando cada elemento en su lugar dentro de la parte ya ordenada	O(n²)	O(n²), pero O(n) si la entrada ya está casi ordenada
Quicksort	Elige un pivote, reparte y ordena las dos mitades (divide y vencerás)	O(n log n)	O(n²) si el pivote se elige siempre mal
Mergesort	Parte por la mitad, ordena cada mitad y mezcla	O(n log n)	O(n log n) garantizado, pero necesita memoria adicional
Heapsort	Construye un montículo y va extrayendo el máximo	O(n log n)	O(n log n) garantizado, y sin memoria adicional
Radix y Counting	No comparan: reparten por dígitos o cuentan ocurrencias	Lineal, O(n)	Lineal, pero solo valen para claves acotadas (enteros, cadenas de longitud fija)

⚠ La pregunta que cayó en 2026 fue cuál de estos algoritmos se ejecuta en tiempo lineal, con heapsort, mergesort y quicksort como distractores. La respuesta es Radix, y el motivo es importante: los tres distractores ordenan comparando elementos, y está demostrado que ninguna ordenación por comparación puede bajar de O(n log n). Radix no compara: reparte por dígitos, y por eso escapa a ese límite.

Dos propiedades más que se preguntan: un algoritmo es estable si conserva el orden relativo de los elementos con la misma clave (lo son inserción, burbuja y mergesort; no lo son quicksort ni heapsort en sus versiones normales), y es in situ (in place) si no necesita memoria adicional apreciable (lo son burbuja, inserción, selección, quicksort y heapsort; no lo es mergesort).

Cuando los datos no caben en memoria: la ordenación externa

Todos los algoritmos del apartado anterior suponen que los datos están en memoria. Si el fichero es mayor que la memoria disponible, el problema cambia por completo: lo caro deja de ser comparar y pasa a ser leer y escribir en disco.

La solución clásica es la ordenación por mezcla externa, en dos fases:

1. Fase de creación de tramos: se lee del fichero tanto como quepa en memoria, se ordena ahí dentro con un algoritmo normal y se escribe como un tramo ordenado en un fichero auxiliar. Se repite hasta agotar la entrada.
2. Fase de mezcla: se mezclan los tramos de dos en dos —o de k en k— leyendo solo el primer registro pendiente de cada uno, hasta quedarse con un único tramo, que es el fichero ordenado.

Lo que importa aquí no es el número de comparaciones sino el número de pasadas sobre el fichero, y por eso se mezclan tantos tramos a la vez como permita la memoria: cada pasada extra son millones de accesos a disco. Es el mismo razonamiento que justifica el árbol B+ para los índices, y por eso este apartado cierra el círculo con el epígrafe 2.

3.4. Búsqueda y recursividad

• Búsqueda secuencial o lineal: se recorre desde el principio. O(n), pero no exige nada: sirve sobre datos desordenados.
• Búsqueda binaria o dicotómica: se compara con el elemento central y se descarta la mitad que no puede contenerlo. O(log n), pero exige que los datos estén ORDENADOS. Ese requisito es el distractor favorito del tema.

Un algoritmo es recursivo cuando se llama a sí mismo con un problema más pequeño. Todo algoritmo recursivo necesita dos cosas, y si falta una el programa no termina:

1. Un caso base, que se resuelve sin volver a llamarse.
2. Un caso recursivo que se acerque al caso base en cada llamada.

La recursión es elegante pero cuesta: cada llamada apila un marco en la pila de llamadas, y si la profundidad se dispara aparece el desbordamiento de pila. Toda recursión puede reescribirse de forma iterativa, y a veces conviene hacerlo por eso mismo.

3.5. Algoritmos sobre grafos

Algoritmo	Qué resuelve
Dijkstra	El camino más corto desde UN vértice origen al resto, en un grafo con pesos. No admite pesos negativos
Bellman-Ford	Lo mismo que Dijkstra pero admitiendo pesos negativos, a cambio de ser más lento
Floyd-Warshall	El camino más corto entre TODOS los pares de vértices
Kruskal y Prim	El árbol de expansión mínima: unir todos los vértices con el menor coste total. Kruskal va escogiendo aristas por peso; Prim hace crecer un árbol desde un vértice

⚠ La pregunta de 2023 fue exactamente esta distinción: «el algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista» es Dijkstra, con Kruskal, Prim y Floyd-Warshall como distractores. La frase «dado un vértice origen» es la que descarta a Floyd-Warshall, y «camino más corto» la que descarta a Kruskal y Prim, que resuelven otro problema.

3.6. Estrategias de diseño

• Divide y vencerás: partir el problema en subproblemas independientes del mismo tipo, resolverlos y combinar. Mergesort y quicksort son los ejemplos canónicos.
• Algoritmos voraces (greedy): en cada paso se toma la decisión que parece mejor en ese momento, sin reconsiderar. Es rapidísimo y no siempre da el óptimo, aunque en algunos problemas sí está demostrado que lo da: Dijkstra, Kruskal y Prim son voraces.
• Programación dinámica: se aplica cuando los subproblemas se solapan. Se resuelve cada uno una sola vez y se guarda el resultado en una tabla para no repetirlo.
• Vuelta atrás (backtracking): se explora sistemáticamente el espacio de soluciones y se retrocede en cuanto una rama se demuestra inviable.

Los límites de lo que se puede calcular

No todo problema tiene algoritmo, y no todo algoritmo es utilizable. Tres nociones que redondean el epígrafe:

• Problemas indecidibles: los que demostradamente no admiten algoritmo. El caso canónico es el problema de la parada: no existe ningún programa que, dado otro programa y su entrada, decida siempre si terminará o se quedará colgado. Lo demostró Turing en 1936, y explica por qué ninguna herramienta de análisis puede garantizar la detección de todos los bucles infinitos.
• Problemas tratables e intratables: un problema es tratable si existe un algoritmo de complejidad polinómica —la clase P—. Los que solo se resuelven en tiempo exponencial se consideran intratables en la práctica: con n = 100, un algoritmo O(2ⁿ) no termina en la vida del universo.
• P y NP: la clase NP agrupa los problemas cuya solución, si alguien te la da, puedes verificar en tiempo polinómico, aunque encontrarla parezca costar mucho más. Si P es igual a NP es el problema abierto más famoso de la informática. Los problemas NP-completos son los más duros de NP: el viajante, la mochila, la satisfacibilidad.

La consecuencia práctica no es teórica: cuando un problema es NP-completo, lo sensato deja de ser buscar el óptimo y pasa a ser aceptar una heurística que dé una solución buena en un tiempo razonable.

4. Formatos de información y ficheros

La distinción de partida es entre ficheros de texto plano, cuyo contenido son caracteres legibles y que se pueden abrir con cualquier editor, y ficheros binarios, cuya interpretación depende del programa que los creó. CSV, JSON, XML y YAML son texto; una imagen o un ejecutable, binario.

4.1. CSV, según la RFC 4180

El formato de valores separados por comas parece trivial y no lo es: hasta la RFC 4180 cada programa hacía lo que quería. Sus reglas, que son las que preguntó el tribunal en 2026:

• Cada registro va en una línea propia, separada por CRLF (retorno de carro y salto de línea).
• Los campos se separan por comas, y la última línea puede llevar o no salto final.
• Los campos que contengan comas, comillas dobles o saltos de línea DEBEN ir encerrados entre comillas dobles. Es decir, un campo sí puede contener una coma, siempre que vaya entrecomillado.
• Una comilla doble dentro de un campo entrecomillado se escribe duplicándola.
• Puede existir una primera línea de cabecera con los nombres de los campos, y su presencia se declara con el parámetro header.
• El tipo MIME registrado es text/csv, no «application/csv».

Los cuatro distractores de la pregunta oficial atacaban justo esas reglas: que las comillas dobles están prohibidas (falso, son el mecanismo de escape), que los campos nunca pueden contener comas (falso si van entrecomillados) y que el tipo MIME es «application/csv» (falso).

4.2. JSON, según la RFC 8259

La notación de objetos de JavaScript se ha convertido en el formato de intercambio dominante. Su norma vigente es la RFC 8259, y lo que hay que saberse es su lista cerrada de tipos.

Un valor JSON debe ser uno de estos siete:

Valor	Qué es
object	Una colección NO ordenada de pares nombre/valor, entre llaves
array	Una secuencia ordenada de valores, entre corchetes
number	Un número, sin distinguir entero de decimal
string	Una cadena entre comillas dobles
true	Literal
false	Literal
null	Literal

⚠ Aquí está la trampa entera del tema. La norma no habla de un tipo «boolean»: enumera los literales true y false por separado. Y no existen ni «date», ni «undefined», ni «function», ni «NaN». Los cuatro distractores de la pregunta de 2026 eran exactamente esas variantes, y todas suenan razonables a quien programa en JavaScript.

Tres reglas más que también cayeron:

• Un objeto JSON es una colección NO ORDENADA de pares nombre/valor. Que muchas implementaciones conserven el orden de inserción es cosa suya, no de la norma.
• JSON no admite comentarios en su sintaxis estándar. Es una de sus limitaciones más criticadas y el motivo de que existan formatos derivados.
• No permite definir tipos de datos personalizados: la lista de siete es cerrada.

Su tipo MIME es application/json y la codificación recomendada, UTF-8. Para validar la estructura de un documento JSON existe JSON Schema, que hace con JSON lo que XSD hace con XML.

4.3. XML y su familia

XML es un metalenguaje de marcas del W3C: no define etiquetas, sino las reglas para que cada cual defina las suyas. Su distinción capital es entre estar bien formado y ser válido:

• Bien formado es cumplir la sintaxis: un único elemento raíz, toda etiqueta abierta se cierra, el anidamiento es correcto, los valores de los atributos van entre comillas y se distinguen mayúsculas de minúsculas.
• Válido es, además, ajustarse a un esquema que define qué elementos y atributos se admiten y en qué orden.

⚠ «¿Cuántos elementos raíz puede contener un documento XML bien formado?» preguntó el tribunal en 2026. La respuesta es uno solo: el elemento raíz, cuyas etiquetas de apertura y cierre no están dentro de ningún otro elemento. Y en el supuesto práctico pidió reconocer el fragmento bien formado y la forma correcta de escribir un atributo, que es nombre="valor" con comillas dobles, no con dos puntos ni sin comillas.

Dos mecanismos que hacen falta en cuanto se mete contenido de verdad dentro de un XML, porque los caracteres < y & son marcado y no pueden escribirse tal cual:

• Las cinco entidades predefinidas, que son las únicas que XML trae de serie: < por <, > por >, & por &, ' por la comilla simple y " por la doble.
• Las secciones CDATA, escritas <![CDATA[ … ]]>, cuyo contenido el analizador no interpreta como marcado. Es lo cómodo para incrustar un fragmento de código o de HTML sin tener que escapar carácter a carácter.

La familia que lo rodea:

Tecnología	Para qué sirve
DTD	El esquema original. Sencillo, pero no usa sintaxis XML y no maneja tipos de datos ni espacios de nombres
XSD (XML Schema)	El esquema moderno. Está escrito en XML, maneja tipos de datos, permite definir tipos personalizados y restricciones sobre los valores de elementos y atributos, y admite espacios de nombres
XPath	Lenguaje para localizar partes de un documento XML
XSLT	Lenguaje para transformar un XML en otro formato (otro XML, HTML, texto)
XQuery	Lenguaje de consulta sobre colecciones de documentos XML
Espacios de nombres	Prefijos que evitan que dos vocabularios distintos choquen dentro del mismo documento

De XSD, el tribunal dio por correcta en 2024 que puede definir restricciones sobre los valores de los elementos y atributos, y por falsas que no pueda definir tipos personalizados, que solo valga sin espacios de nombres y que no pueda referenciarse desde otro esquema.

XML sigue siendo el formato de la administración electrónica: las firmas XAdES, el intercambio de identidad con SAML 2 que usa Cl@ve, la factura electrónica y los documentos del Esquema Nacional de Interoperabilidad son XML.

Servicios web: SOAP, WSDL y REST

De la familia XML sale la generación de servicios web que sigue sosteniendo buena parte de la interoperabilidad entre Administraciones, y el tribunal la preguntó en 2026. Conviene no mezclar las tres piezas, porque cada una responde a una cosa distinta:

Pieza	Qué es
SOAP	El protocolo de mensajería: define un «envelope» —sobre— con su cabecera y su cuerpo, y las reglas de codificación de las invocaciones remotas
WSDL	El lenguaje XML que DESCRIBE el servicio: qué operaciones ofrece, con qué mensajes y en qué dirección se le encuentra. La versión 2.0 del W3C parte de un modelo abstracto de lo que el servicio ofrece y lo liga después a un protocolo concreto
UDDI	El directorio donde publicar y localizar servicios. Es la pieza que menos cuajó
REST	No es un protocolo sino un estilo de arquitectura: se opera sobre recursos identificados por su URL con los métodos de HTTP (GET, POST, PUT, DELETE) y sus códigos de estado. Hoy intercambia sobre todo JSON

⚠ «¿Cuál es la finalidad de WSDL 2.0?» cayó en 2026, y los tres distractores eran justamente las otras piezas: el «envelope» y las reglas de codificación (que es SOAP), los métodos y códigos de estado sobre recursos (que es HTTP/REST) y el canal bidireccional con «handshake» y «framing» sobre TCP (que es WebSocket). Quien distinga las cuatro no falla la pregunta.

YAML y los ficheros de configuración

YAML es un formato de serialización pensado para que lo lea una persona. Frente a JSON aporta tres cosas: usa la sangría en lugar de llaves y corchetes, admite comentarios con almohadilla —cosa que JSON no— y permite referencias internas para no repetir. A cambio, la sangría significativa lo hace frágil: un espacio de más cambia el significado, y por eso no admite tabuladores.

Todo JSON válido es, además, YAML válido, porque YAML es un superconjunto suyo. Es el formato habitual de los ficheros de configuración de infraestructura y de las tuberías de integración continua.

Junto a él conviven otros formatos de configuración de larga vida: los ficheros .ini, con sus secciones entre corchetes y sus pares clave=valor; los .properties del mundo Java; y TOML, más reciente y con una gramática más estricta que el .ini.

Formatos de imagen, audio y vídeo

Familia	Formatos	Nota
Imagen de mapa de bits	JPEG, PNG, GIF, BMP, TIFF, WebP	Guardan píxeles: al ampliar, pixelan. JPEG con pérdida; PNG y GIF sin ella
Imagen vectorial	SVG, EPS	Guardan instrucciones de dibujo: escalan a cualquier tamaño sin perder calidad. SVG está escrito en XML
Audio	MP3, AAC, OGG · WAV, FLAC	Los primeros con pérdida; WAV sin comprimir y FLAC sin pérdida
Vídeo	MP4, MKV, AVI (contenedores) · H.264, H.265, AV1 (códecs)	⚠ Contenedor y códec no son lo mismo: el contenedor empaqueta las pistas, el códec las comprime. Un mismo .mp4 puede llevar dentro códecs distintos

Esa última distinción explica una avería típica del soporte: un vídeo que «no se ve» aunque su extensión sea conocida. La extensión indica el contenedor; lo que falta es el códec.

Serialización y codificación en texto

Serializar es convertir una estructura de datos en memoria en una secuencia de bytes que pueda guardarse o enviarse; deserializar es el camino inverso. CSV, JSON, XML y YAML son formatos de serialización en texto; también los hay binarios, más compactos y rápidos pero ilegibles.

⚠ La deserialización de datos que vienen de fuera es una de las puertas de entrada de ataque más conocidas: si el formato permite reconstruir objetos arbitrarios, un atacante puede lograr ejecución de código. La regla es no deserializar nunca sin validar y sin restringir los tipos admitidos.

Y un mecanismo que aparece constantemente en administración electrónica: Base64. No es cifrado ni compresión: es una codificación que representa datos binarios usando solo 64 caracteres imprimibles, para poder meterlos dentro de un formato de texto —el contenido de un fichero dentro de un XML, un certificado, un adjunto de correo—. Su coste es que aumenta el tamaño en torno a un tercio, porque cada 3 bytes se convierten en 4 caracteres. Confundir Base64 con cifrado es un error grave y frecuente: cualquiera puede descodificarlo sin ninguna clave.

4.4. Formatos ofimáticos y de documento

Formato	Norma	Nota
ODF (OpenDocument)	ISO/IEC 26300	El formato abierto de documento ofimático. Extensiones .odt, .ods, .odp
OOXML (Office Open XML)	ISO/IEC 29500	El de Microsoft Office. Extensiones .docx, .xlsx, .pptx
PDF	ISO 32000	Formato de presentación fija, independiente del dispositivo
PDF/A	ISO 19005	La variante para conservación a largo plazo: sin contenido activo y con las fuentes incrustadas

Los dos primeros comparten una característica que sorprende: un .odt o un .docx es en realidad un fichero comprimido en ZIP que contiene varios documentos XML y las imágenes. Se puede renombrar a .zip y abrirlo para verlo.

En la Administración, qué formatos pueden usarse no es una elección libre: lo fija el Catálogo de estándares del Esquema Nacional de Interoperabilidad, que distingue los de uso general y los de uso específico, y que es la razón de que ODF y PDF aparezcan una y otra vez en los pliegos.

Cómo se identifica un formato

Un fichero no lleva escrito qué es. Hay tres mecanismos para averiguarlo, y conviene saber cuál es fiable:

• La extensión: una convención del nombre. Es la menos fiable, porque se cambia renombrando.
• El número mágico: los primeros bytes del propio fichero, que identifican el formato. Un PDF empieza por %PDF, un ZIP por PK, un PNG por una secuencia fija. Es el mecanismo que usan las herramientas serias.
• El tipo MIME: la etiqueta con la que se declara el contenido al transmitirlo por red, en la forma tipo/subtipo.

Formato	Tipo MIME
CSV	text/csv
JSON	application/json
XML	application/xml (o text/xml)
PDF	application/pdf
Texto plano · HTML	text/plain · text/html
Binario genérico	application/octet-stream

⚠ El tipo MIME lo declara quien envía, así que tampoco es prueba: al recibir un fichero subido por un usuario hay que comprobar el contenido real, no fiarse ni de la extensión ni del MIME declarado.

HTML frente a XML

Los dos descienden de SGML y se parecen, pero persiguen cosas distintas:

• HTML tiene un vocabulario fijo de etiquetas y describe cómo se presenta un documento. Es tolerante: los navegadores intentan mostrar el documento aunque falten cierres.
• XML no tiene vocabulario propio y describe qué significan los datos, no cómo se ven. Es estricto: un documento mal formado sencillamente no se procesa.

De la unión de los dos criterios nació XHTML: el vocabulario de HTML con las reglas estrictas de XML. Y HTML5 es hoy la versión vigente del primero, con sus etiquetas semánticas y sus atributos de accesibilidad, que es por donde el tribunal lo llevó al supuesto práctico de 2026.

4.5. Compresión

Dos familias que no se pueden confundir:

• Sin pérdida: al descomprimir se recupera exactamente el original. Es obligatorio para texto, programas y datos. ZIP, GZIP, 7z, PNG, FLAC.
• Con pérdida: se descarta información que se supone poco perceptible, y el original ya no se puede recuperar. Solo vale para medios: JPEG, MP3, MPEG.

La tasa de compresión depende sobre todo de la redundancia del contenido: un texto se comprime mucho porque repite palabras; un fichero ya comprimido o cifrado no se comprime nada, porque su contenido es estadísticamente indistinguible del ruido. De ahí una consecuencia práctica: comprimir dos veces no reduce más, y a veces aumenta el tamaño por la sobrecarga de la cabecera.

Dentro de la compresión sin pérdida conviven dos ideas, y los compresores de uso corriente las combinan:

• La codificación de longitud variable, que asigna códigos más cortos a los símbolos que más se repiten y más largos a los raros. Es el algoritmo de Huffman, que construye un árbol binario a partir de las frecuencias y obtiene de él un código que ningún otro código empieza, de modo que se puede descodificar sin ambigüedad.
• Los métodos de diccionario de la familia LZ (LZ77, LZ78, LZW), que sustituyen cada secuencia ya vista por una referencia a su aparición anterior.

ZIP y GZIP usan las dos a la vez: su algoritmo DEFLATE es LZ77 seguido de Huffman, y de ahí que rindan tanto con texto. Conviene tener presente que Huffman no pierde nada: descartar lo poco perceptible es cosa de la otra familia.

Los formatos con los que trabaja la Administración

Este tema es técnico, pero desemboca directamente en el bloque I: el expediente electrónico se construye con estos formatos, y sus nombres caen en las dos partes del examen.

Formato	Qué es
XAdES	Firma electrónica avanzada sobre XML. Es la de los documentos del expediente electrónico
CAdES	La misma familia de firma, pero sobre datos binarios cualesquiera
PAdES	La misma familia, incrustada en un PDF, de modo que el documento firmado sigue siendo un PDF que cualquiera abre
Facturae	El formato XML de la factura electrónica en el sector público español, firmada con XAdES
SAML 2	Estándar abierto basado en XML para intercambiar datos de autenticación y autorización entre sistemas. Es el que usa Cl@ve, y así lo dijo el propio enunciado del tribunal

Las tres primeras se distinguen por sobre qué se firma, no por la fuerza de la firma: XML, binario o PDF. Es una pregunta recurrente y se resuelve mirando la letra que precede a «AdES».

Y un concepto transversal que conviene fijar aquí: el resumen criptográfico o hash (SHA-256 y siguientes) es la huella de longitud fija que se calcula sobre un fichero. No es cifrado —no se puede deshacer— y es lo que permite comprobar que un documento no ha sido alterado: si cambia un solo bit, el resumen cambia por completo. Sobre ese resumen, y no sobre el fichero entero, es sobre lo que se aplica la firma electrónica.

5. Cuadros para memorizar

Dato	Valor
Pila · Cola	LIFO · FIFO
Máximo de nodos de un árbol binario de h niveles	2ʰ − 1 (con 4 niveles, 15)
Preorden	Raíz · izquierdo · derecho
Inorden · Postorden	Izq · raíz · der ·|· Izq · der · raíz
Recorrido por niveles	Con una cola
Rojo-negro: la raíz	Es NEGRA; los hijos de un rojo son negros; igual nº de negros por camino
Árbol 2-3-4	Nodos de 2, 3 o 4 hijos; todas las hojas al mismo nivel
Búsqueda binaria	O(log n), exige datos ORDENADOS
Ordenación por comparación: mejor cota	O(n log n). Radix y counting son lineales porque NO comparan
Quicksort: medio y peor	O(n log n) · O(n²)
Dijkstra · Floyd-Warshall · Kruskal y Prim	Un origen · todos los pares · árbol de expansión mínima
CSV (RFC 4180)	Registros separados por CRLF; comas y comillas dentro de un campo, entre comillas dobles; MIME text/csv
JSON (RFC 8259)	object, array, number, string, true, false, null. Objeto NO ordenado. Sin comentarios
XML bien formado	UN solo elemento raíz; atributos entre comillas dobles
ODF · OOXML · PDF · PDF/A	ISO 26300 · ISO 29500 · ISO 32000 · ISO 19005

5.1. El coste de cada estructura, de un vistazo

La tabla que de verdad hay que llevar sabida, porque el tribunal pregunta «cuál es más eficiente para…» y la respuesta está aquí:

Estructura	Buscar	Insertar	Lo que la hace útil
Array (acceso por índice)	O(n) sin ordenar	O(n)	Acceso directo a la posición i en O(1)
Array ordenado	O(log n) binaria	O(n)	Búsqueda rápida a cambio de inserción cara
Lista enlazada	O(n)	O(1) con el nodo	Inserción y borrado sin desplazar nada
Árbol binario de búsqueda equilibrado	O(log n)	O(log n)	Mantiene el orden, permite recorridos
Tabla hash	O(1) promedio	O(1) promedio	La más rápida, pero pierde el orden

🚨 Las dos trampas: la búsqueda binaria exige que esté ordenado —sobre un array desordenado no es aplicable, no es que sea lenta—, y la tabla hash es O(1) en promedio: en el peor caso, con todas las claves colisionando, degenera en O(n).

5.2. Organizaciones de fichero: cuál elegir

Organización	Acceso	Cuándo se usa
Secuencial	Solo en orden, del principio al fin	Procesos por lotes que leen el fichero entero
Directa o aleatoria	Por dirección calculada con la clave	Acceso inmediato a un registro conocido
Indexada	Por índice y también secuencial	Cuando hacen falta las dos formas

La indexada es la respuesta cuando el enunciado pide acceso directo y recorrido ordenado: es la única que da las dos cosas, a costa de mantener el índice.

5.3. Los números que caen

• Un byte son 8 bits; un carácter ASCII básico ocupa 7 bits y su extensión, 8.
• UTF-8 es de longitud variable: de 1 a 4 bytes por carácter. Las vocales acentuadas del español ocupan dos.
• CSV está descrito en el RFC 4180 y JSON en el RFC 8259. Que el tribunal cite la norma por su número es su costumbre en la parte técnica.
• La compresión se divide en sin pérdida (ZIP, PNG, FLAC: se recupera el original bit a bit) y con pérdida (JPEG, MP3, MPEG: no se recupera). Un fichero de texto o un ejecutable nunca se comprimen con pérdida.

5.4. Los algoritmos de ordenación que se preguntan

Algoritmo	Caso medio	Peor caso	¿Estable?
Burbuja e inserción	O(n²)	O(n²)	Sí
Selección	O(n²)	O(n²)	No
Quicksort	O(n log n)	🚨 O(n²)	No
Mergesort	O(n log n)	O(n log n)	Sí
Heapsort	O(n log n)	O(n log n)	No

Dos ideas que resuelven la mayoría de las preguntas. La primera: quicksort es el más rápido en la práctica pero NO garantiza O(n log n); con un pivote desafortunado degenera en O(n²). Mergesort sí lo garantiza, a costa de memoria adicional. La segunda: un algoritmo es estable si conserva el orden relativo de los elementos con la misma clave, y eso importa cuando se ordena dos veces por criterios distintos.

5.5. Recursividad e iteración

Toda función recursiva necesita dos cosas: un caso base que la detenga y una llamada que se acerque a él. Si falta el caso base, el resultado no es un bucle infinito sino un desbordamiento de pila, porque cada llamada consume un marco de pila.

Cualquier algoritmo recursivo puede escribirse de forma iterativa y al revés. La recursiva se lee mejor en problemas que se definen sobre sí mismos —recorridos de árboles, «divide y vencerás»—; la iterativa gasta menos memoria. Y sobre la recursividad de cola: cuando la llamada recursiva es la última operación, algunos compiladores la convierten en un bucle y el consumo de pila desaparece.

5.6. Pila y cola: la pareja que se intercambia

Una pila es LIFO (el último en entrar es el primero en salir) y sus operaciones se llaman apilar y desapilar; una cola es FIFO (el primero en entrar es el primero en salir). La pila es la estructura de las llamadas a función y del botón «deshacer»; la cola, la de los trabajos de impresión y la de los procesos listos.

🚨 Y una tercera que se cuela como distractor: la cola de prioridad NO es FIFO —sale primero el de mayor prioridad, no el que antes llegó— y suele implementarse sobre un montículo (heap).

6. Lo que ya ha preguntado el tribunal

• «En el formato de ficheros CSV, descrito en RFC 4180, ¿qué regla es correcta?» → cada registro en una línea separada por CRLF, y los campos con comas, comillas o saltos de línea entre comillas dobles (2026). Apartado 4.1.
• «Según la definición estándar de JSON, RFC 8259, un valor JSON debe pertenecer a uno de estos tipos o literales» → object, array, number, string, true, false y null (2026). Apartado 4.2.
• «Según el estándar JSON (RFC 8259), ¿cuál de las siguientes afirmaciones es correcta?» → un objeto JSON es una colección no ordenada de pares nombre/valor (extraordinaria de 2026). Apartado 4.2.
• «Señale la opción correcta en relación a los árboles rojo-negro» → la raíz es un nodo negro (2026). Apartado 1.4.
• «Para recorrer un árbol binario no vacío en preorden…» → visitar la raíz, recorrer el subárbol izquierdo y recorrer el derecho (extraordinaria de 2026). Apartado 1.3.
• «Considerando el nodo raíz como nivel 1, ¿cuál es el número máximo de nodos en un árbol binario de 4 niveles?» → 15 (extraordinaria de 2026). Apartado 1.3.
• «Con respecto a los árboles 2-3-4, señale la respuesta correcta» → los nodos pueden tener 2, 3 o 4 hijos (2024). Apartado 1.4.
• «¿Cuál de los siguientes algoritmos de ordenación se ejecuta en tiempo lineal?» → Radix (2026, supuesto). Apartado 3.3.
• «El algoritmo para el camino más corto, dado un vértice origen, en un grafo con pesos» → Dijkstra (2023). Apartado 3.5.
• «¿Cuántos elementos raíz puede contener un documento XML bien formado?» → solo uno (2026). Apartado 4.3.
• «¿Cuál de los siguientes fragmentos XML está bien formado?» y «¿cómo se incluye correctamente un atributo?» → el que cierra bien todas las etiquetas y el que escribe id_alumno="10" con comillas dobles (2026, supuesto). Apartado 4.3.
• «¿Cuál de las siguientes afirmaciones sobre XML Schema (XSD) es correcta?» → puede definir restricciones sobre los valores de elementos y atributos (promoción interna de 2024, supuesto). Apartado 4.3.

Qué enseña esta lista. Doce preguntas y ni una pide programar: piden la regla exacta del estándar o la propiedad exacta de la estructura. Y los distractores son siempre versiones mínimamente alteradas de la verdad —«nodos rojos» donde la regla dice negros, «boolean» donde la norma enumera true y false—, de modo que quien se sepa la regla a medias falla. Este es un tema de precisión, no de comprensión, y por eso el cuadro del apartado 5 es la mejor inversión de tiempo. Recuerda que cada error resta un tercio.