EEDD y Algoritmos

Question 1

Árboles balanceados

Answer 1

• AVL
• Splay
• Rojo-Negro
• AA
• B+
• B*

Question 2

Algoritmos de cálculo de recubrimiento

Answer 2

• PRIM
• KRUSKAL

Question 3

Algoritmos de cálculo de camino mínimo

Answer 3

• FLOY (entre todos los nodos)
• BELLMAN-FORD
• DIJKSTRA
• A*
• JOHNSON
• VITERBI

Question 4

Algoritmo de cálculo de grupos conexos

Answer 4

• TARJAN

Question 5

Algoritmos de masificación de flujo

Answer 5

• FORD-FULKERSON

Question 6

Fichero secuencial indexado

Answer 6

ISAM

Question 7

Contenedor de correos electrónicos

Answer 7

mbox (RFC 4155)

Question 8

Formato de UN correo electrónico

Answer 8

eml (RFC 2822) / msg

Question 9

Libro electrónico

Answer 9

epub

Question 10

Fichero con “película” flash

Answer 10

swf

Question 11

Texto formateado separador por comas (,) o por punto y coma (;)

Answer 11

csv

Question 12

Buzones de Lotus de IBM

Answer 12

nsf

Question 13

Buzones de Outlook

Answer 13

pst / ost

Question 14

Instalable de Android

Answer 14

apk

Question 15

Instalable de Microsoft

Answer 15

msi

Question 16

Instalable de Linux Debian y derivados como Ubuntu

Answer 16

deb

Question 17

Instalable de Linux Redhat y derivados como Centos

Answer 17

rpm

Question 18

Instalable de MAC

Answer 18

pkg / dmg

Question 19

Compimido básico de Linux

Answer 19

tag.gz

Question 20

Certificado X509 CON su clave privada

Answer 20

p12 / pfx

Question 21

Certificado X509 SIN su clave privada

Answer 21

cer

Question 22

Que tipo de fichero es jpeg

Answer 22

Compresión con pérdida. Existen variantes sin pérdida como JPEG2000 / Lossless JPEG. jpeg: Joint Photographic Experts Group

Question 23

Que tipo de fichero es png

Answer 23

Compresión sin pérdida. Transparencia. No animación. True color (24 bits)

Question 24

Que tipo de fichero es svg

Answer 24

Scalable Vector Graphics. Tipo MIME image/svg+xml. En HTML 5 se incrusta dentro del html de forma nativa.

Question 25

Que tipo de fichero es gif

Answer 25

256 colores. Animación y transparencia. Compresión LZW sin pérdida

Question 26

Que tipo de fichero es tiff

Answer 26

Etiquetado o tagged. Lo hay con y sin compresión. Multipágina

Question 27

Que tipo de fichero es bmp

Answer 27

De Microsoft. Compresión RLE sin pérdida

Question 28

Que tipo de fichero es webp

Answer 28

Con y sin pérdida. Desarrollado por Google.

Question 29

Que es Signature o magic number

Answer 29

Fichero binario. Son los N primeros bytes que identifican qué tipo de fichero es.

Question 30

En qué consiste el algoritmo de Burbuja

Answer 30

O(n2) en caso medio (Θ) o en el peor de los casos (O). Va desplazando el nº más grande a base de comparaciones e intercambios entre elementos adyacentes. Mejor caso (Ω) O(n) si la lista ya está ordenada.

Question 31

En qué consiste el algoritmo de Inserción Directa

Answer 31

O(n2) al igual que el Burbble en el caso medio (Θ) y en el peor de los casos (O). Busca dónde insertar el dato y desplaza los siguientes elementos. Si se hace una búsqueda binaria : Inserción Binaria

Question 32

En qué consiste el Merge Sort

Answer 32

O(n log(n)) en todos los casos. Es recursivo. Divide la lista en sublistas hasta alcanzar el caso más sencillo para comparar. Mezcla las sublistas para obtener una lista ordenada.

Question 33

En qué consiste el Quick Sort

Answer 33

O(n log(n)). Es recursivo. Se elige un pivote, y en la primera pasada los menores del pivote se colocan a la izquierda y los mayores del pivote a la derecha. En la segunda pasada se hace lo mismo en ambos lados. Si se elige mal el pivote, y se elige el máximo o el mínimo, sería el peor de los casos (O) O(n^2)

Question 34

En qué consiste Heap Sort

Answer 34

O(n log(n)). Se meten los datos en un montículo MAX HEAP y se va extrayendo la cima (se realizan N llamadas a EliminarMax().)

Question 35

En qué consiste el algoritmo de Selección

Answer 35

Siempre O(n2). Se busca el mínimo y se coloca. Se busca el siguiente mínimo y se coloca a continuación.

Question 36

En qué consiste BurketSort o BinSort

Answer 36

O(n) Distribuye los números en casilleros y dentro de cada casillero aplicas el criterio que sea.

Question 37

En qué consiste Radix Sort

Answer 37

O(n K) Se basa en el número de cifras de los números a ordenar. LSD usa el dígito menos significativo y MSD el más significativo.

Question 38

¿Qué tipos de algoritmos de ordenación Exchange Sorts, existen?

Answer 38

Burbuja, Quick Sort y Cocktail

Question 39

¿Qué tipos de algoritmos de ordenación Selection Sorts, existen?

Answer 39

Selección y Heap Sort

Question 40

¿Qué tipos de algoritmos de ordenación Insertion Sorts, existen?

Answer 40

Inserción Directa/ Inserción Binaria y Shell Sort

Question 41

¿Qué tipos de algoritmos de ordenación Merge Sorts, existen?

Answer 41

Merge Sort

Question 42

¿Qué tipos de algoritmos de ordenación Distribution Sort, existen?

Answer 42

Bucketsort o Bitshort y Radix Sort

Question 43

Clasificación de algoritmos de ordenación

Answer 43

* Interno (memoria) / Externo (fichero) * Natural: tarda lo mínimo si la entrada está ordenada * Estable: mantiene orden relativo original de los datos. No desordena claves iguales

Question 44

¿Qué técnica de análisis y diseño de algoritmos es Top-Down?

Answer 44

Divide y Vencerás. Divide un problema en subproblemas y los resuelve independientemente

Question 45

¿Qué técnica de diseño de algoritmos se basa en probar todas las posibilidades?

Answer 45

Backtracking

Question 46

¿Qué técnica de diseño de algoritmos es una optimización de Divide y Vencerás?

Answer 46

Programación Dinámica. Memorización de funciones. Combina subsoluciones hasta alcanzar la solución general óptima.

Question 47

¿Cuáles son los algoritmos probabilísticos?

Answer 47

Montecarlo y Las Vegas

Question 48

¿Qué técnica de diseño de algoritmos es una optimización de Backtracking?

Answer 48

Ramificación y poda. Recuerda resultados anteriores para no repetir pasos.

Question 49

¿Qué técnica de diseño de algoritmos se basa en utilizar la opción más óptima en cada paso?

Answer 49

Voraces

Question 50

¿Cómo se representa la complejidad de un algoritmo, tanto complejidad espacial como complejidad temporal?

Answer 50

La representación de la complejidad de un algoritmo: Big O Notation (cota superior asintótica) De mejor a peor: (-) - O(1) Constante - O(log(n)) Logarítmica - O(n) Lineal - O(n log(n)) n logarítmica - O(n^2) Cuadrática - O(2^n) Exponencial - O(n!) Factorial - O(n^n) Potencial Exponencial (+)