Estructuras de datos, algoritmos y formatos de ficheros — Cuerpo de Técnicos Auxiliares de Informática de la Administración del Estado
Test de 32 preguntas con explicaciones justificadas.
Pregunta 1: En una estructura de datos tipo pila, el principio de acceso a los elementos se conoce como:
- A) FIFO (First In, First Out).
- B) LIFO (Last In, First Out).
- C) Aleatorio.
- D) Por índice.
Una pila es una estructura LIFO (Last In, First Out), donde el último elemento insertado es el primero en ser extraído. Esto se contrasta con una cola, que es FIFO.
Pregunta 2: ¿Cuál es la complejidad temporal en el peor caso del algoritmo de ordenación Quicksort si el pivote se elige siempre de manera que genere particiones desequilibradas?
- A) O(n log n).
- B) O(log n).
- C) O(n^2).
- D) O(n).
En el peor caso de Quicksort (p.ej., cuando el array ya está ordenado y el pivote es siempre el menor o mayor elemento), el algoritmo degenera a una complejidad de O(n^2), ya que realiza n llamadas recursivas procesando listas de tamaño n-1, n-2, etc.
Pregunta 3: ¿Qué estructura de datos no lineal es ideal para representar conexiones o relaciones entre pares de objetos, como en redes de carreteras o redes sociales?
- A) Árbol binario.
- B) Cola de prioridad.
- C) Grafo.
- D) Array unidimensional.
Un grafo es una estructura de datos no lineal que consiste en un conjunto de vértices (nodos) y aristas (conexiones) que relacionan pares de vértices, ideal para modelar relaciones como redes.
Pregunta 4: En el contexto de complejidad algorítmica, la notación O(n) indica que el tiempo de ejecución:
- A) Crece de forma logarítmica con el tamaño de entrada.
- B) Es constante, independiente del tamaño de entrada.
- C) Crece de forma lineal con el tamaño de entrada.
- D) Crece de forma cuadrática con el tamaño de entrada.
La notación O(n) representa una complejidad lineal, lo que significa que el tiempo de ejecución del algoritmo es directamente proporcional al tamaño 'n' de los datos de entrada.
Pregunta 5: ¿Qué operación básica en una tabla hash tiene una complejidad promedio de O(1) en condiciones ideales?
- A) Ordenación.
- B) Búsqueda por valor (sin clave).
- C) Inserción de un par clave-valor.
- D) Recorrido secuencial de todos los elementos.
En una tabla hash bien diseñada y con una función hash eficiente, las operaciones de inserción, búsqueda por clave y eliminación tienen un coste promedio constante O(1), asumiendo una baja tasa de colisiones.
Pregunta 6: El algoritmo de ordenación Mergesort se basa fundamentalmente en la técnica de:
- A) Intercambio de elementos adyacentes.
- B) Selección del elemento mínimo en cada pasada.
- C) Dividir y conquistar (Divide and Conquer).
- D) Inserción de elementos en su posición correcta.
Mergesort es un algoritmo de ordenación que sigue el paradigma 'Divide y Vencerás': divide recursivamente la lista en mitades hasta tener sublistas de un elemento, y luego las fusiona (merge) en orden.
Pregunta 7: En un árbol binario de búsqueda (BST), para cualquier nodo, todos los valores en su subárbol izquierdo son:
- A) Mayores que el valor del nodo.
- B) Iguales al valor del nodo.
- C) Menores que el valor del nodo.
- D) No tienen ninguna relación predefinida.
Por definición, en un Árbol Binario de Búsqueda (BST) válido, todos los nodos en el subárbol izquierdo de un nodo dado contienen valores menores, y todos los del subárbol derecho contienen valores mayores.
Pregunta 8: ¿Qué formato de fichero está específicamente diseñado para representar datos jerárquicos usando etiquetas y es legible tanto por humanos como por máquinas?
- A) CSV (Comma-Separated Values).
- B) JSON (JavaScript Object Notation).
- C) XML (eXtensible Markup Language).
- D) Binario.
XML es un lenguaje de marcado que utiliza etiquetas para definir una estructura de datos jerárquica y es textual, por lo que es legible. JSON también es jerárquico y legible, pero la especificidad de 'etiquetas' es característica principal de XML.
Pregunta 9: En una cola, la operación que añade un elemento al final de la misma se denomina comúnmente:
- A) Pop o desapilar.
- B) Push o apilar.
- C) Dequeue o desencolar.
- D) Enqueue o encolar.
En una cola (estructura FIFO), la operación de inserción se llama 'encolar' (enqueue) y añade el elemento al final. La operación de extracción es 'desencolar' (dequeue) y retira el primer elemento.
Pregunta 10: El algoritmo de búsqueda binaria (binary search) requiere como precondición que la lista sobre la que se busca esté:
- A) Almacenada en una lista enlazada.
- B) Ordenada.
- C) Distribuida en una tabla hash.
- D) Compuesta únicamente por números enteros.
La búsqueda binaria divide repetidamente el espacio de búsqueda a la mitad, lo que solo es posible si los datos están previamente ordenados. Su complejidad es O(log n).
Pregunta 11: ¿Cuál es la principal característica que distingue a un fichero de formato binario de uno de texto plano?
- A) El binario solo puede almacenar números.
- B) El binario puede contener cualquier secuencia de bytes, incluidos caracteres no imprimibles.
- C) El texto plano ocupa siempre más espacio.
- D) El binario es siempre más rápido de procesar.
Un fichero binario almacena datos en formato de bytes crudos, que pueden representar cualquier tipo de dato (imágenes, ejecutables, números en formato interno). Un fichero de texto almacena secuencias de caracteres codificados (como ASCII o UTF-8).
Pregunta 12: En una lista enlazada simple, cada nodo contiene típicamente:
- A) Un valor y un puntero al nodo anterior y otro al siguiente.
- B) Solo un valor.
- C) Un valor y un puntero al siguiente nodo.
- D) Un valor y dos índices.
Un nodo de una lista enlazada simple está compuesto por dos campos: el dato (valor) y un enlace (puntero/referencia) al siguiente nodo en la secuencia. Una lista doblemente enlazada tendría punteros al anterior y al siguiente.
Pregunta 13: El algoritmo de ordenación Burbuja (Bubble Sort) tiene una complejidad temporal en el peor caso de:
- A) O(n log n).
- B) O(n).
- C) O(n^2).
- D) O(log n).
Bubble Sort compara e intercambia repetidamente elementos adyacentes si están en el orden incorrecto. En el peor caso (lista inversamente ordenada), realiza aproximadamente n*(n-1)/2 comparaciones e intercambios, lo que es O(n^2).
Pregunta 14: En el formato JSON, un conjunto de pares clave-valor se representa mediante:
- A) Un array, delimitado por corchetes [].
- B) Un objeto, delimitado por llaves {}.
- C) Una cadena, delimitada por comillas "".
- D) Un número, sin delimitadores.
En JSON, un objeto es una colección no ordenada de pares clave/valor, delimitada por llaves {}. Un array es una lista ordenada de valores, delimitada por corchetes [].
Pregunta 15: ¿Qué estructura de datos permite un acceso rápido a los elementos mediante un índice numérico, pero tiene un coste de inserción o eliminación en medio potencialmente alto?
- A) Lista enlazada simple.
- B) Pila.
- C) Array (vector).
- D) Árbol AVL.
Un array permite acceso por índice en tiempo constante O(1). Sin embargo, insertar o eliminar un elemento en una posición intermedia puede requerir desplazar muchos elementos, con coste O(n) en el peor caso.
Pregunta 16: ¿Cuál de estos algoritmos de ordenación es conocido por ser 'in-place', es decir, no requiere memoria adicional significativa más allá del array de entrada?
- A) Mergesort.
- B) Quicksort (en su implementación común).
- C) Counting Sort.
- D) Radix Sort.
Quicksort típicamente se implementa de forma 'in-place', usando el espacio del array original y realizando intercambios dentro de él, con una pequeña pila para la recursividad (O(log n) en el mejor caso). Mergesort generalmente requiere memoria auxiliar O(n).
Pregunta 17: En un grafo, el grado de un vértice se define como:
- A) La altura máxima desde ese vértice a una hoja.
- B) El número de aristas que inciden en él.
- C) El peso total de sus aristas salientes.
- D) Su posición en una lista de adyacencia.
En teoría de grafos, el grado de un vértice es el número de aristas que son incidentes a él. En un grafo dirigido, se distingue entre grado de entrada (aristas que llegan) y grado de salida (aristas que salen).
Pregunta 18: El formato CSV (Valores Separados por Comas) almacena datos tabulares donde cada fila:
- A) Es un objeto JSON.
- B) Se representa en una línea de texto, con campos separados por un delimitador (como una coma).
- C) Requiere etiquetas de apertura y cierre.
- D) Debe tener un número fijo de columnas definido en la primera línea siempre.
Un fichero CSV representa datos tabulares en texto plano, donde cada línea corresponde a una fila y los campos dentro de la línea están separados por un carácter delimitador (generalmente una coma o punto y coma).
Pregunta 19: La complejidad O(log n) es típica de algoritmos que:
- A) Recorren una lista una vez.
- B) Dividen el problema a la mitad en cada paso.
- C) Comparan cada elemento con todos los demás.
- D) Tienen dos bucles anidados sobre los datos.
Una complejidad logarítmica O(log n) surge en algoritmos que reducen el tamaño del problema a la mitad (o una fracción constante) en cada paso, como la búsqueda binaria en un array ordenado o las operaciones en un árbol binario de búsqueda balanceado.
Pregunta 20: ¿Qué operación en una lista enlazada doble permite el desplazamiento tanto hacia adelante como hacia atrás desde un nodo dado?
- A) Tiene un puntero solo al siguiente nodo.
- B) Tiene punteros al nodo anterior y al siguiente.
- C) Almacena el índice del nodo anterior.
- D) Utiliza un array interno para navegación.
Una lista doblemente enlazada contiene en cada nodo dos punteros/referencias: uno al nodo siguiente (next) y otro al nodo anterior (prev). Esto permite recorrer la lista en ambas direcciones eficientemente.
Pregunta 21: En el contexto de algoritmos de búsqueda, una búsqueda secuencial o lineal en un array no ordenado tiene complejidad:
- A) O(1) en el mejor caso.
- B) O(log n) en el caso promedio.
- C) O(n) en el peor caso.
- D) O(n^2) en todos los casos.
La búsqueda lineal recorre los elementos uno a uno hasta encontrar el deseado. En el peor caso (elemento no presente o al final), debe examinar los n elementos, dando una complejidad O(n).
Pregunta 22: Un árbol binario completo es aquel en el que:
- A) Cada nodo tiene exactamente dos hijos.
- B) Todos los niveles están completamente llenos, excepto posiblemente el último, que se llena de izquierda a derecha.
- C) No tiene ningún nodo con más de dos hijos.
- D) La altura del subárbol izquierdo y derecho difiere como máximo en uno.
Un árbol binario completo tiene todos sus niveles completamente llenos de nodos, excepto quizás el último nivel, que debe estar lleno de izquierda a derecha sin huecos. Esta definición es clave para estructuras como los heaps.
Pregunta 23: La función principal de una tabla hash es:
- A) Mantener los datos ordenados por clave.
- B) Proporcionar un acceso rápido a los datos mediante una clave, aplicando una función hash.
- C) Almacenar datos en una estructura jerárquica.
- D) Implementar una política FIFO para el acceso.
Una tabla hash asocia claves con valores. Usa una función hash para calcular un índice (posición) a partir de la clave, permitiendo un acceso, inserción y borrado muy rápido en promedio (O(1)).
Pregunta 24: El algoritmo de ordenación por selección (Selection Sort) funciona:
- A) Intercambiando repetidamente elementos adyacentes desordenados.
- B) Construyendo la secuencia ordenada uno a uno, insertando cada elemento en su posición correcta.
- C) Dividiendo la lista en sublistas, ordenándolas y fusionándolas.
- D) Encontrando repetidamente el elemento mínimo del segmento no ordenado y colocándolo al principio.
Selection Sort divide la lista en una parte ordenada (al inicio) y otra desordenada. En cada iteración, encuentra el mínimo elemento de la parte desordenada y lo intercambia con el primer elemento de esa parte, expandiendo la zona ordenada.
Pregunta 25: ¿Qué representa la 'n' en la notación de complejidad O(n)?
- A) El número de operaciones por segundo que realiza la CPU.
- B) El tamaño del conjunto de datos de entrada.
- C) El número de algoritmos ejecutándose en paralelo.
- D) La cantidad de memoria disponible en bytes.
En análisis de algoritmos, 'n' denota típicamente el tamaño de la entrada (número de elementos a procesar). La notación O(f(n)) describe cómo crece el tiempo de ejecución o el uso de memoria en función de ese tamaño 'n'.
Pregunta 26: ¿Cuál de las siguientes estructuras de datos es FIFO (First In, First Out)?
- A) Pila.
- B) Árbol.
- C) Cola.
- D) Lista enlazada.
Una cola es una estructura FIFO: el primer elemento en entrar es el primero en salir. Esto contrasta con la pila (LIFO). Una lista enlazada puede implementar ambos comportamientos, pero su principio no es intrínsecamente FIFO.
Pregunta 27: En un fichero XML, la declaración de la versión y codificación se coloca típicamente al inicio con una sintaxis como:
- A) <!DOCTYPE ...>
- B) <?xml version="1.0" encoding="UTF-8"?>
- C) <xml encoding="UTF-8">
- D) <!-- XML 1.0 -->
La declaración XML (o prólogo) es opcional pero recomendada. Especifica la versión del XML y la codificación de caracteres. Su formato es <?xml version="..." encoding="..."?>.
Pregunta 28: La técnica de 'hashing cerrado' o 'direccionamiento cerrado' para resolver colisiones en una tabla hash generalmente utiliza:
- A) Listas enlazadas en cada bucket (cubo).
- B) Buscar la siguiente celda vacía dentro de la misma tabla (sondeo).
- C) Redimensionar la tabla inmediatamente tras una colisión.
- D) Descartar el nuevo elemento en caso de colisión.
El direccionamiento cerrado (closed addressing) maneja colisiones almacenando todos los elementos que hash a la misma posición en una estructura de datos auxiliar, típicamente una lista enlazada (separate chaining). El direccionamiento abierto (open addressing) busca otra celda dentro de la tabla.
Pregunta 29: La travesía en preorden de un árbol binario visita los nodos en el orden:
- A) Subárbol izquierdo, raíz, subárbol derecho.
- B) Raíz, subárbol izquierdo, subárbol derecho.
- C) Subárbol izquierdo, subárbol derecho, raíz.
- D) De izquierda a derecha por niveles.
En un recorrido en preorden (pre-order) de un árbol binario, primero se visita la raíz, luego se recorre el subárbol izquierdo en preorden, y finalmente el subárbol derecho en preorden.
Pregunta 30: La complejidad en el caso promedio del algoritmo Quicksort, asumiendo una elección buena del pivote, es:
- A) O(n).
- B) O(n log n).
- C) O(n^2).
- D) O(log n).
En el caso promedio, Quicksort divide el array en dos partes de tamaño aproximadamente similar de forma recursiva, dando lugar a una complejidad de O(n log n). Esto asume que el pivote divide la lista de forma balanceada la mayoría de las veces.
Pregunta 31: ¿Cuál de los siguientes NO es un formato de intercambio de datos basado en texto?
- A) JSON.
- B) XML.
- C) CSV.
- D) Un ejecutable (.exe).
JSON, XML y CSV son formatos de texto plano legibles por humanos y máquinas. Un archivo ejecutable (.exe) es un formato binario diseñado para ser ejecutado por un sistema operativo, no para el intercambio estructurado de datos.
Pregunta 32: En una lista enlazada, el acceso a un elemento en una posición arbitraria index 'i' tiene complejidad:
- A) O(1).
- B) O(log i).
- C) O(n).
- D) O(i).
En una lista enlazada (simple o doble), para acceder al elemento en la posición i, es necesario recorrer la lista desde la cabeza (o desde la cola si es doble y i está cerca) nodo a nodo. Esto requiere en el peor caso O(n) tiempo, donde n es la longitud de la lista.