EEDD y Algoritmos Flashcards
(86 cards)
1
Q
Árboles equilibrado o autobalanceables
A
- AVL
- Splay
- Rojo-Negro
- AA
- B
- B+
- B*
2
Q
Algoritmos de cálculo de recubrimiento
A
- PRIM
- KRUSKAL
3
Q
Algoritmos de cálculo de camino mínimo
A
- FLOY (entre todos los nodos)
- BELLMAN-FORD
- DIJKSTRA
- A*
- JOHNSON
- VITERBI
4
Q
Algoritmo de cálculo de grupos conexos
A
- TARJAN
5
Q
Algoritmos de masificación de flujo
A
- FORD-FULKERSON
6
Q
Fichero secuencial indexado
A
ISAM
7
Q
Contenedor de correos electrónicos
A
mbox (RFC 4155)
8
Q
Formato de UN correo electrónico
A
eml (RFC 2822) / msg
9
Q
Libro electrónico
A
epub
10
Q
Fichero con “película” flash
A
swf
11
Q
Texto formateado separador por comas (,) o por punto y coma (;)
A
csv
12
Q
Buzones de Lotus de IBM
A
nsf
13
Q
Buzones de Outlook
A
pst / ost
14
Q
Instalable de Android
A
apk
Nota: aab: nuevo instablable Android con todas
las versiones de diferentes plataformas
15
Q
Instalable de Microsoft
A
msi
16
Q
Instalable de Linux Debian y derivados como Ubuntu
A
deb
17
Q
Instalable de Linux Redhat y derivados como Centos
A
rpm
18
Q
Instalable de MAC
A
pkg / dmg
19
Q
Compimido básico de Linux
A
tag.gz
20
Q
Certificado X509 CON su clave privada
A
p12 / pfx
21
Q
Certificado X509 SIN su clave privada
A
cer
22
Q
Que tipo de fichero es jpeg
A
Compresión con pérdida. Existen variantes sin pérdida como JPEG2000 / Lossless JPEG. jpeg: Joint Photographic Experts Group
23
Q
Que tipo de fichero es png
A
Compresión sin pérdida. Transparencia. No animación. True color (24 bits)
24
Q
Que tipo de fichero es svg
A
Scalable Vector Graphics. Tipo MIME image/svg+xml. En HTML 5 se incrusta dentro del html de forma nativa.
25
Que tipo de fichero es gif
256 colores. Animación y transparencia. Compresión LZW sin pérdida
26
Que tipo de fichero es tiff
Etiquetado o tagged. Lo hay con y sin compresión. Multipágina
27
Que tipo de fichero es bmp
Formato de imagen. De Microsoft. Compresión RLE sin pérdida
28
Que tipo de fichero es webp
Con y sin pérdida. Desarrollado por Google.
29
Que es Signature o magic number
Fichero binario. Son los N primeros bytes que identifican qué tipo de fichero es.
30
En qué consiste el algoritmo de Burbuja
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.
31
En qué consiste el algoritmo de Inserción Directa
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
32
En qué consiste el Merge Sort
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.
33
En qué consiste el Quick Sort
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)
34
En qué consiste Heap Sort
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().)
35
En qué consiste el algoritmo de Selección
Siempre O(n2). Se busca el mínimo y se coloca. Se busca el siguiente mínimo y se coloca a continuación.
36
En qué consiste BurketSort o BinSort
O(n) Distribuye los números en casilleros y dentro de cada casillero aplicas el criterio que sea.
37
En qué consiste Radix Sort
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.
38
¿Qué tipos de algoritmos de ordenación Exchange Sorts, existen?
Burbuja, Quick Sort y Cocktail
39
¿Qué tipos de algoritmos de ordenación Selection Sorts, existen?
Selección y Heap Sort
40
¿Qué tipos de algoritmos de ordenación Insertion Sorts, existen?
Inserción Directa/ Inserción Binaria y Shell Sort
41
¿Qué tipos de algoritmos de ordenación Merge
Sorts, existen?
Merge Sort
42
¿Qué tipos de algoritmos de ordenación Distribution Sort, existen?
Bucketsort o Bitshort y Radix Sort
43
Clasificación de algoritmos de ordenación
* 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
44
¿Qué técnica de análisis y diseño de algoritmos es Top-Down?
Divide y Vencerás. Divide un problema en subproblemas y los resuelve independientemente
45
¿Qué técnica de diseño de algoritmos se basa en probar todas las posibilidades?
Backtracking
46
¿Qué técnica de diseño de algoritmos es una optimización de Divide y Vencerás?
Programación Dinámica. Memorización de funciones. Combina subsoluciones hasta alcanzar la solución general óptima.
47
¿Cuáles son los algoritmos probabilísticos?
Montecarlo y Las Vegas
48
¿Qué técnica de diseño de algoritmos es una optimización de Backtracking?
Ramificación y poda. Recuerda resultados anteriores para no repetir pasos.
49
¿Qué técnica de diseño de algoritmos se basa en utilizar la opción más óptima en cada paso?
Voraces
50
¿Cómo se representa la complejidad de un algoritmo, tanto complejidad espacial como complejidad temporal?
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
(+)
51
¿En qué consiste el acceso secuencial a ficheros?
En hacer una búsqueda desde el inicio, borrado lógico y añadir al final. Ej CINTA
52
¿En qué consiste el acceso directo a ficheros?
En acceder directamente a los registros. Una clave del registro o una función sobre la clave nos posiciona en el archivo.
53
¿En qué consiste el acceso indexado a ficheros?
Se busca la clave en un índice ordenado y nos da la posición en el archivo, ya que hay un fichero para el índice y otro para los datos
54
¿En qué consiste el acceso híbrido o ISAM a ficheros?
Acceso secuencial + Acceso indexado. Es un acceso indexado para el índice y secuencial para los datos. EJ. MyISAM de MySQL
55
¿Qué tipos de ordenación de ficheros externa existen?
- Por mezcla directa
- Por mezcla natural
56
Dentro de EEDD, ¿Cómo pueden ser los grafos?
* Dirigidos (dígrafos) / no dirigidos : unidireccional/bidireccional
* Conexos / inconexos
* Cíclicos / acíclicos
* Multigrafos
* Etiquetado o Ponderado
57
¿Qué quiere decir que un grafo está etiquetado o ponderado?
Que tiene un peso numérico en las aristas
58
¿Qué es un multigrafo?
Aquel grafo en el que hay más de una arista entre dos vértices
59
¿Qué es el orden de un grafo?
El número de nodos o vértices
60
¿Qué es el grado de un vértice en los grafos?
El número de aristas que inciden en él
61
¿Qué es el grado de un grafo?
La suma de los grados de sus vértices
62
¿Cuál es el tamaño de un grafo?
El número de aristas/caminos
63
¿Qué dos tipos de representación de grafos existen?
* Lista de adyacencia: array de vértices + listas enlazadas (cada vértice tiene enlazada una lista que contiene los vértices adyacentes a él)
* Array o Matriz de adyacencia: desperdicia memoria si hay muchos nodos (filas y columnas)
64
¿Qué estructura de datos tiene un array asociativo?
Tabla hash
Nota: el array asociativo también se conoce como diccionario o mapa
65
Primitivas del tipo abstracto de datos Stack o Pila
push, pop, isEmpty, peek/top
Nota: LIFO
66
Primitivas del tipo abstracto de datos (TaD) Queue o Cola
enqueue, dequeue, isEmpty, peek/top
Nota: FIFO
67
Primitivas del tipo abstracto de datos List o Lista
isEmpty, insertarDelante, insertarDetras, head, tail.
68
¿Qué características tiene un árbol B?
- Es un árbol equilibrado
- En cada nodo puede tener más de dos hijos y como máximo tiene M hijos (Orden=M)
- Cada nodo, excepto la raíz, tiene M/2 claves
- Inserciones y borrados en tiempo log(n) para las reestructuraciones de los nodos
- Mantiene los datos ordenados
- Muy utilizado en bases de datos y sistemas de ficheros
69
¿Qué características tiene un árbol B+?
- Los nodos internos solo contienen claves y punteros
- Las hojas están enlazadas entre sí
70
¿Qué características tiene un árbol B*?
Garantiza una densidad de ocupación de 2/3
71
Tipos de árboles binarios
- Árbol binario de búsqueda (ABB) : el recorrido inorden IRD devuelve todos los valores ordenados
- Árbol de Fibonacci : caso particular de AVL
72
Recorrido RID (PREORDEN)
Recorrido en profundidad visitando : Raíz, Subárbol izquierdo y Subárbol derecho
73
Recorrido IRD (INORDEN)
Recorrido en profundidad visitando : Subárbol izquierdo, Raíz y Subárbol derecho
74
Recorrido IDR (POSTORDEN)
Recorrido en profundidad visitando : Subárbol izquierdo, Subárbol derecho y Raíz
75
¿Qué es el orden en un árbol?
El número máximo de hijos que pueden tener sus nodos
76
¿Qué es el grado de un nodo en un árbol?
El número de hijos directos que tiene dicho nodo
77
¿Qué es el grado de un árbol?
La suma de los grados de sus nodos
78
¿Cuál es la altura de un nodo en un árbol?
El número de aristas de la trayectoria más larga de ese nodo a una hoja
79
¿Qué es la profundidad de un nodo en un árbol?
El número de aristas que hay desde ese nodo a la raíz
80
¿Qué es el peso en un árbol?
El número total de nodos
81
¿Qué es el FE de un árbol?
El FE es el factor de equilibrio. La diferencia de altura entre el subárbol izquierdo y el subárbol derecho
Nota: en los árboles equilibrados o autobalanceables el FE es -1, 0, +1.
82
¿En qué consiste el tipo MIME?
Es una cadena con la que se identifica a todos los ficheros multimedia mediante un estándar:
estructura tipo etiqueta tipo/subtipo
Ejemplos:
- image/gif
- text/xml
- text/html
- video/mpeg
- application/javascript
- application/pdf
83
¿Cómo se llama la versión de PDF especial para el archivado y conservación de documentos electrónicos a largo plazo?
PDF/A
84
¿Cómo se llama la versión de PDF que hace referencia al acceso universal?
PDF/UA
85
¿Cómo se llama la versión de PDF para impresoras?
PDF/X
86
Diferencia entre DOC y DOCX
- DOC < 2007: formato propietario OLE
- DOCX >= 2007: es un .zip con muchos ficheros XML dentro con
formato OOXML (Office Open XML). Estándar ECMA 376
