Estructuras de datos, algoritmos y formatos de ficheros — Test de Cuerpo de Técnicos Auxiliares de Informática de la Administración del Estado

Esta sección revela las respuestas correctas. Te recomendamos hacer el test antes de consultarla.

• En una estructura de datos tipo pila, el principio de acceso a los elementos se conoce como:

  Respuesta correcta: LIFO (Last In, First Out).

  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.

• ¿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?

  Respuesta correcta: O(n^2).

  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.

• ¿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?

  Respuesta correcta: Grafo.

  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.

• En el contexto de complejidad algorítmica, la notación O(n) indica que el tiempo de ejecución:

  Respuesta correcta: Crece de forma lineal 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.

• ¿Qué operación básica en una tabla hash tiene una complejidad promedio de O(1) en condiciones ideales?

  Respuesta correcta: Inserción de un par clave-valor.

  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.

• El algoritmo de ordenación Mergesort se basa fundamentalmente en la técnica de:

  Respuesta correcta: Dividir y conquistar (Divide and Conquer).

  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.

• En un árbol binario de búsqueda (BST), para cualquier nodo, todos los valores en su subárbol izquierdo son:

  Respuesta correcta: Menores que el valor del nodo.

  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.

• ¿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?

  Respuesta correcta: XML (eXtensible Markup Language).

  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.

• En una cola, la operación que añade un elemento al final de la misma se denomina comúnmente:

  Respuesta correcta: 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.

• El algoritmo de búsqueda binaria (binary search) requiere como precondición que la lista sobre la que se busca esté:

  Respuesta correcta: Ordenada.

  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).

• ¿Cuál es la principal característica que distingue a un fichero de formato binario de uno de texto plano?

  Respuesta correcta: El binario puede contener cualquier secuencia de bytes, incluidos caracteres no imprimibles.

  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).

• En una lista enlazada simple, cada nodo contiene típicamente:

  Respuesta correcta: Un valor y un puntero al siguiente nodo.

  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.

• El algoritmo de ordenación Burbuja (Bubble Sort) tiene una complejidad temporal en el peor caso de:

  Respuesta correcta: O(n^2).

  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).

• En el formato JSON, un conjunto de pares clave-valor se representa mediante:

  Respuesta correcta: Un objeto, delimitado por llaves {}.

  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 [].

• ¿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?

  Respuesta correcta: Array (vector).

  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.

• ¿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?

  Respuesta correcta: Quicksort (en su implementación común).

  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).

• En un grafo, el grado de un vértice se define como:

  Respuesta correcta: El número de aristas que inciden en él.

  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).

• El formato CSV (Valores Separados por Comas) almacena datos tabulares donde cada fila:

  Respuesta correcta: Se representa en una línea de texto, con campos separados por un delimitador (como una coma).

  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).

• La complejidad O(log n) es típica de algoritmos que:

  Respuesta correcta: Dividen el problema a la mitad en cada paso.

  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.

• ¿Qué operación en una lista enlazada doble permite el desplazamiento tanto hacia adelante como hacia atrás desde un nodo dado?

  Respuesta correcta: Tiene punteros al nodo anterior y al siguiente.

  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.

• En el contexto de algoritmos de búsqueda, una búsqueda secuencial o lineal en un array no ordenado tiene complejidad:

  Respuesta correcta: O(n) en el peor caso.

  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).

• Un árbol binario completo es aquel en el que:

  Respuesta correcta: Todos los niveles están completamente llenos, excepto posiblemente el último, que se llena de izquierda a derecha.

  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.

• La función principal de una tabla hash es:

  Respuesta correcta: Proporcionar un acceso rápido a los datos mediante una clave, aplicando una función hash.

  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)).

• El algoritmo de ordenación por selección (Selection Sort) funciona:

  Respuesta correcta: 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.

• ¿Qué representa la 'n' en la notación de complejidad O(n)?

  Respuesta correcta: El tamaño del conjunto de datos de entrada.

  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'.

• ¿Cuál de las siguientes estructuras de datos es FIFO (First In, First Out)?

  Respuesta correcta: Cola.

  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.

• En un fichero XML, la declaración de la versión y codificación se coloca típicamente al inicio con una sintaxis como:

  Respuesta correcta: <?xml version="1.0" encoding="UTF-8"?>

  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="..."?>.

• La técnica de 'hashing cerrado' o 'direccionamiento cerrado' para resolver colisiones en una tabla hash generalmente utiliza:

  Respuesta correcta: Listas enlazadas en cada bucket (cubo).

  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.

• La travesía en preorden de un árbol binario visita los nodos en el orden:

  Respuesta correcta: Raíz, subárbol izquierdo, subárbol derecho.

  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.

• La complejidad en el caso promedio del algoritmo Quicksort, asumiendo una elección buena del pivote, es:

  Respuesta correcta: O(n 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.

• ¿Cuál de los siguientes NO es un formato de intercambio de datos basado en texto?

  Respuesta correcta: 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.

• En una lista enlazada, el acceso a un elemento en una posición arbitraria index 'i' tiene complejidad:

  Respuesta correcta: O(n).

  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.