Tema 03 - Informática

Respecto a los árboles B+ usados en índices de bases de datos, señale la opción INCORRECTA: Todas las claves se encuentran duplicadas en las hojas y en los nodos internos. Todas las hojas aparecen al mismo nivel, garantizando profundidad uniforme. Los nodos internos almacenan únicamente claves de separación y punteros. El recorrido secuencial ordenado del fichero se realiza enlazando las hojas.

Considere un vector estático y una lista enlazada simple; elija la afirmación correcta sobre su coste de acceso: Acceder al elemento k-ésimo cuesta Θ(1) en ambos casos. En la lista enlazada el acceso al elemento k-ésimo es Θ(k). En el vector la inserción al principio es Θ(1). En la lista enlazada eliminar el primer nodo requiere Θ(n).

Al representar un grafo disperso con n vértices y m aristas, la estructura que minimiza memoria asintótica es: Matriz de adyacencia de n×n. Lista de adyacencia con vector de punteros. Matriz de incidencia n×m. Tabla hash con pares ordenados (u,v).

¿Qué operación sobre un montículo binario (heap) de n elementos garantiza O(log n) en el peor caso?. Consultar el menor (peek). Insertar un nuevo elemento. Obtener el tamaño. Comprobar si está vacío.

En un fichero secuencial ordenado sobre cinta magnética, la búsqueda binaria no es apropiada porque: El dispositivo no permite posicionamiento real. El tiempo de rebobinado es constante. El acceso es estrictamente secuencial sin saltos eficientes. El algoritmo exige que los registros estén desordenados.

Un índice primario basado en árbol ISAM se caracteriza por: Rebasa dinámicamente su altura para mantener el factor de ocupación. Realiza divisiones y fusiones de nodos en cada inserción. Mantiene niveles superiores estáticos mientras nuevas claves se añaden a hojas de desbordamiento. Garantiza que todas las claves permanezcan en memoria principal.

El hashing extensible (extendible hashing) evita colisiones mediante: Sondas lineales en el área primaria. Re-hash con doble dispersión. Directorios que crecen duplicando su tamaño y dividen cubos al saturarse. Listas enlazadas por bloque con punteros invertidos.

Para un disco con bloques de 4 KB y registro fijo de 512 B, ¿cuántos registros caben físicamente en un bloque y qué sucede con el espacio restante?. 7 registros y 128 B de slack. 8 registros y 0 B libres. 9 registros ajustados con relleno. 7 registros y 0 B sin desperdicio.

¿Cuál de los siguientes algoritmos de ordenación interna es estable y tiene coste Θ(n log n) en el peor caso?. Heapsort. Mergesort. Quicksort. Shellsort.

Seleccione la afirmación correcta sobre Quicksort con elección de pivote aleatoria: El número esperado de comparaciones es Θ(n). El peor caso se produce con entradas aleatorias. La altura media del árbol de recursión es O(log n). Utiliza espacio adicional Θ(n) para las particiones.

En un grafo no ponderado y conectado, el algoritmo que garantiza encontrar la distancia mínima en número de aristas desde un origen a todos los vértices es: DFS. BFS. Dijkstra. Prim.

El planificador Round-Robin de un sistema operativo con quantum muy pequeño tiende a: Minimizar el turnaround pero empeorar el overhead por cambios de contexto. Maximizar la latencia interactiva sin impacto en el overhead. Ser equivalente a FCFS cuando el quantum → ∞. Provocar inanición (starvation) de procesos cortos.

En UTF-8, la secuencia de bytes 0xE2 0x82 0xAC representa: El carácter ‘€’ usando tres bytes. El carácter ‘€’ usando codificación de 4 bytes. Una secuencia ilegal al romper la regla de continuidad 10xxxxxx. El carácter ‘£’ en ISO-8859-1.

El algoritmo de compresión LZW utilizado en GIF y TIFF se basa en: Análisis estadístico de frecuencias y códigos prefijos variables. Construcción dinámica de un diccionario de cadenas encontradas durante la lectura. Transformada Burrows-Wheeler seguida de codificación aritmética. Predicción lineal y cuantificación diferencial.

En los formatos de imagen, indique la respuesta correcta: PNG usa compresión con pérdida basada en cuantización de color. JPEG2000 aplica transformada wavelet y permite modos sin pérdida. BMP incorpora obligatoriamente paleta comprimida RLE. WebP solo admite compresión sin pérdida.

Señale la respuesta correcta referente al tipo abstracto de datos (TAD) Pila: Se basa en el principio FIFO (first-in, first-out). Cada extracción elimina el elemento del fondo de la pila. Su operación de inserción habitual se denomina push y la de eliminación pop. Sólo puede implementarse con un vector de tamaño fijo.

Señale la respuesta INCORRECTA respecto a las listas doblemente enlazadas: Cada nodo mantiene referencias tanto al siguiente como al anterior nodo. Permiten recorridos en ambos sentidos con coste O(1) por movimiento. Suprimen la necesidad de puntero a la lista en operaciones de inserción. Ocupan más memoria por nodo que una lista simplemente enlazada.

En un árbol AVL, ¿cuál de las siguientes afirmaciones es correcta?. La diferencia de altura entre los hijos de todo nodo nunca supera 1. Las hojas pueden diferir arbitrariamente en su profundidad. El recorrido in-order produce los nodos en orden descendente. La inserción nunca provoca rotaciones dobles.

Respecto a la representación de grafos en memoria, señale la respuesta correcta: Una matriz de adyacencia requiere O(V+E) espacio. Una lista de arcos es óptima para grafos densos. Una lista de adyacencia permite enumerar los vecinos de un vértice en tiempo proporcional a su grado. La matriz de adyacencia impide almacenar grafos dirigidos.

En la organización secuencial indexada (ISAM), señale la respuesta correcta: Todo acceso debe leerse secuencialmente desde el primer registro. El índice se mantiene automáticamente equilibrado tras cada inserción. Los registros nuevos se almacenan en áreas de desbordamiento. No existe separación física entre índice y datos.

Señale la respuesta INCORRECTA sobre los ficheros con dispersión (hashing) y direccionamiento abierto: Pueden sufrir clustering primario con exploración lineal. El factor de carga alto deteriora el tiempo medio de búsqueda. Eliminaciones lógicas requieren marcar celdas como “borradas”. Garantizan siempre O(1) tiempo de búsqueda en el peor caso.

En planificación de CPU, si se conocen de antemano las duraciones de los procesos y se busca minimizar el tiempo medio de espera, ¿qué algoritmo resulta óptimo?. Round-Robin. First-Come, First-Served (FCFS). Shortest Job First (SJF) no expropiativo. Prioridades estáticas sin envejecimiento.

Dados N elementos ordenados, la búsqueda binaria requiere: Θ(N) comparaciones en promedio. Θ(log₂ N) comparaciones en el caso medio y peor. Θ(log₂ N) sólo en el mejor caso. Θ(√N) en el peor caso por la división repetida.

Señale la respuesta correcta sobre la estabilidad de algoritmos de ordenación: Quicksort es estable por diseño de su partición in-place. Heapsort es estable si utiliza un comparador estable. Merge sort es estable siempre que la fusión preserve el orden de igualdad. Shell sort es estable cuando la secuencia de incrementos incluye 1.

Respecto a la codificación UTF-8, señale la respuesta correcta: Utiliza siempre 2 bytes por carácter. Es compatible hacia atrás con ASCII en el rango 0x00–0x7F. Almacena primero el byte menos significativo de cada carácter. Codifica todo carácter Unicode en exactamente 3 bytes.

¿Qué técnica de compresión sin pérdida construye su diccionario durante la compresión a partir de cadenas previamente vistas?. Huffman. LZW. RLE (Run Length Encoding). Burrows-Wheeler Transform sin codificación posterior.

¿Cuál de los siguientes formatos de archivo incorpora el magic number 89 50 4E 47 16 ?. GIF. JPEG. PNG. TIFF.

El algoritmo de ordenación Heapsort se caracteriza por: Requerir memoria auxiliar O(N). Ser estable y adaptativo. Garantizar O(N log N) comparaciones en el peor caso. Presentar mejor rendimiento que Quicksort en la práctica media.

Respecto a los árboles B y B+, señale la respuesta correcta: En un B+-tree las claves pueden residir tanto en nodos internos como en hojas. Un B-tree garantiza que todas las hojas estén al mismo nivel. En un B+-tree la búsqueda se detiene en el primer nodo interno que contenga la clave. Las hojas del B+-tree no están enlazadas secuencialmente.

En la organización de ficheros sobre cinta magnética, se denomina gap interbloque al: Espacio sin señal grabado entre dos bloques de datos consecutivos. Área reservada donde se almacena la tabla de índices. Conjunto de bytes de relleno usados para alinear registros en un sector. Método alternativo de direccionamiento mediante hashing externo.