B2T3 EEDD Flashcards
TAD
Tipo Abstracto de Datos.
Modelo matemático para definir tipos de datos (primitivas)
stack
Lista circular LIFO
push, pop, isEmpty, top
queue
Lista circular FIFO
enQueue, deQueue, isEmpty, top
lista
EEDD secuencia. Ordenados de manera consecutiva
isEmpty, insertarDelante, insertarDetras, head, tail
Tabla Hash
Se añaden elementos sabiendo la posición que ocupa cada dato insertado.
Si está mal diseñado se producen colisiones.
Solución direcc. abierto/cerrado
Montículo
Max-heap: la raíz el valor más alto del árbol
Min-heap: la raíz el valor más bajo del árbol
Grado (árboles)
Número de hijos directos que tiene
Orden (árboles)
Número máximo de hijos que puede tener un nodo
Profundidad de nodo
Aristas de la raíz al nodo.
En raíz profundidad =0
Altura de nodo
Trayectoria más larga del nodo a una hoja.
Altura en cada hoja = 0
Peso
Número de nodos del árbol
Factor de equilibrio
Diferencia de altura entre subárbol izquierdo y derecho.
Tipos de árboles equilibrados (autobalanceados)
-AVL (rotaciones)
-AA
-Rojo-negro
-Splay
-Árbol B
Recorridos en profundidad
-Preorden (RID)
-Inorden(IRD)
-Postorden(IDR)
Árboles multicamino
-Árbol B: Cada nodo puede tener más de 2 hijos, orden M
Datos ordenados
Inserciones y borrados en tiempo log(n)
Cada nodo tiene máximo M hijos
Cada nodo tiene como mínimo M/2 hijos
-Árbol B+:
Nodos internos solo contienen claves y punteros
Los nodos hojas están enlazados entre sí
-Árbol b*
Garantiza densidad de ocupación 2/3
Tipos de grafo
-Dirigidos
-No dirigidos
-Conexo: todos sus vértices conectados por 1 camino
-Multigrafo: más de una arista entre 2 vértices
Orden del grafo
Número de vértices (nodos)
Grado de un vértice
Número de arcos incidentes en el vértice
Tipos de representación de grafos
-Matriz de adyacencia -> desperdicia memoria
-Lista de adyacencia
Algoritmos árbol recubridor mínimo
Cubre todos los nodos con el menor coste posible.
Prim y Kruskal
Algoritmos camino mínimo
-Dijsktra
-Bellman-Ford
-A*
-Johnson
-Viterbi
Otros algoritmos
-Ford-Fulkerson: camino para maximizar flujo
-Tarjan: grupos conexos
-Floyd-Warshall: camino entre 2 vértices
Tipos de acceso a ficheros
-Acceso secuencial:
Búsqueda desde el inicio
Borrado lógico
Se añade sobre el final
-Acceso directo(a los registros)
Clave del registro => posición en archivo
Función sobre la clave => posición en archivo
-Acceso indexado. Fichero datos + fichero índice.
Se busca la clave sobre el índice ordenado y nos da posición en archivo
-Caso híbrido => ISAM (ej. MyISAM en MySQL).
Indexado para índice, secuencial para datos
Ordenación de ficheros (externa, no en memoria)
-Mezcla directa, haciendo particiones y ordenando por pares
-Mezcla natural, tiene en cuenta los tramos ya ordenados
Tipos fichero imagen
JPEG, PNG, GIF, TIFF, BMP, SVG, webp
Tipos fichero audio
MP3, WAV, FLAC, WMA, AC3, AAC, OPUS, VORBIS(.ogg)
Contenedores vídeo
MKV, AVI, ASF, OFF, 3GP, MP4, MOV, webM, OGM
Códecs vídeo
DIVX/XDIV, AVC(264), HEVC(265), VVC(266), AV1, VP8, VP9, MPEG-1, MPEG-2, MPEG-4, WMV, Theora
Tipos ficheros extras
t/o = template, m = macro, b = binario
xls, rtf, open office, PDF/A, PS(PostScript), PCL, fuentes(otf, otc, ttf, ttc, tte, woff, woff2
