BII Tema 3 Secc Estructuras De Datos Flashcards
Concepto monticulo
Max heap: el de arriba el mayor de todos
Min heap: el de arriba el menor de todos.
Estructura basada en arbol que se reconstruye muy eficientemente
Complejidad O log N para inserciones y borrados
Arboles equilibrados
ejemplos
Aquellos arboles cuyo factor de equilibrio está entre -1 , 0 , -1
Autobalanceables: si se inserta un nuevo elemento lo reestructura para que siga siendo equilibrado
Ejemplos :
AVL (Rotaciones es como hace el equilibrado)
AA
Rojo-negro
Splay
Árbol B
Arboles multicamino
(Árboles B)
En cada nodo puede tener más de un dato
- Árbol B : cada nodo puede tener más de 2 hijos.dentro de los nodos está la info y la clave
Datos ordenados
- Árbol B+ : nodos internos solo tienen claves y punteros. Los nodos hoja están entrelazados entre si mediante una lista enlazada. Los datos están en las hojas, en los nodos están los punteros y claves
- Árbol B* : garantiza densidad de ocupación (2/3) muy densos
Recorridos en profundidad de un arbol
Preorden (RID)
Inorden (IRD)
Postorden (IDR)
Grado de un nodo
N° de hijos directos que tiene ese nodo
Profundidad de un nodo
N° de aristas de la raíz al nodo
Altura nodo
Camino más largo de ese nodo hasta una hoja
Factor equilibrio de un árbol
Diferencia altura entre el subárbol izquierdo con el subárbol derecho
Peso del arbol
Sumar todos los nodos
Orden del arbol
N° máximo de hijos que puede tener un nodo
Grado arbol
N° máximo de hijos que tiene alguno de sus nodos
Nivel del arbol
Es la altura de la raíz
la altura de la raiz
árbol vacío sería 0. (Ojo según autor)
Grafos
Estructuras que son un red de nodos
Grafo dirigidos y no dirigidos
Grafos dirigidos : tienen un sentido definido
Grafos no dirigidos : no tienen un sentido, va en los 2 sentidos
Multigrafo
Cuando hay más de un camino para llegar entre dos nodos / vertices
Grafo etiquetado/ponderado
Cuando tiene pesos en las aristas
Grafo conexo
Todos los Nodos conectados entre si por al menos un camino
Grafo. Grado de un vértice/nodo
N° de aristas incidentes
Orden de un grafo
N° de vertices
Grafos. manera de representarlos
Lista adyacencia
Matrices adyacencia
TAD.
Tipo abstracto de datos.
Modelo matemático para definir un tipo de dato/info. Esa info se define mediante sus primitivas( operaciones)
Estructura de datos
Concepto más concreto orientado a la implementación
Implementaciones estructura de datos
Lista ( secuencia)
Colas (queue)
Pila ( stack)
Priority queue (heap)
Árbol
Grafo
Array asociativo
Estructura datos
Estáticas y dinamicas
-Estáticas : tienen un tamaño inicial y no pueden crecer mientras se ejecute el programa. El tamaño se define antes
- simples
- compuestas
-Dinamicas: pueden crecer en N elementos
-Arboles, listas enlazadas, tablas hash
- lineales: pila, cola, lista
- no lineales : arboles, grafos
Concepto tabla hash
Gran estructura de datos
Estructura clave valor
- clave : para indexar
- valor: respecto de su clave. El valor que indexamos
Solución colisiones tabla hash
-Direccionamiento cerrado/ hashing abierto/ encadenamiento separado
Cada casilla del array referencia a una lista, aquí mete los registros que colisionan
- direccionamiento abierto / hashing cerrado
Almacenar directamente en el array. Sondeo de array para ver si la casilla está libre. Donde lineal, cuadrático, doble hasheo
Acceso a información en ficheros.
Acceso secuencial
Ejemplo: cinta ( va siempre hacia adelante el almacenamiento de datos)
Se añade sobre el final
Acceso a la información en ficheros
Acceso directo
Acceso directo( a los registros)
2 formas
- clave registro
- función (claves)
Acceso a la información en ficheros
Acceso indexado
Fichero datos + fichero índices. Separa estas dos zonas
Se busca la clave sobre el índice ordenado= posicion
Fichero isam
Fichero secuencial + indexado
Ordenación de ficheros
Mezcla directa : secuencias tamaño fijo
Mezcla natural : igual que directa pero más lista, se da cuenta si están ordenados
Algoritmos
Dijstra
Algoritmo camino mínimo entre dos nodos
OSPF
Algoritmos
Bellman- ford
Camino mínimo entre dos nodos
RIP
Algoritmo
Floyd warshall
Camino mínimo todos los pares de nodos
Todos con todos
Algoritmo
A*
Camino minimo
Algoritmo
Prim
Recubrimiento minimo
Algoritmo kruskal
Recubrimiento minimo
Algoritmo tarjan
Grupos conexos. Quién está conectado con quién
Algoritmo ford- fulkerson
Camino para maximizar flujo
Ficheros audio
Con pérdidas
-Mp3- mpeg1 o mpeg2
-Ac3 - multicanal
-AAC - mpeg2 4 part3 ( sucesor MP3: .m4a, .m4b, acc, 3gp
-OPUS- .opus
- vorbis- .ogg
Ficheros audio
Sin perdidas
FLAC - .flac
FICHERO .WAV
Contenedor audio
.WAV, .wave
Concepto fichero .wma
Microsoft. Existen 4 codecs
Formatos de vídeo
Contenedores
Mkv
Avi
Asf
Ogg
3gp (para móviles)
MP4
Mov
Webm(basado en mkv)
Formatos video
Codecs
Divx y xdiv
Avc ( H.264 o mpeg4 part 10)
Hevc ( H.265 o mpeg H part2)
VVC (H.266 o mpeg I part3)
AV1
VP8
VP9
MPEG 1 part2 (video cd)
MPEG 2 part 2 (H.262- Dvd)
MPEG 4 part 2 (H.263 - Hd)
Wmv
Theora
Archivos imagen
JPG -compresión con pérdidas
PNG - compresión sin perdidas
Gif
Tiff
BMP
Svg
Archivos open office
Odt - texto
Ott - texto (plantilla)
Ods - hoja cálculo
Odp - presentación
…..
Archivo PDF/A
PDF a largo plazo
Ficheros ofimática
Xls
Doc /dot
Docx/docm/dotx/dotm
RTF ( texto enriquecido)
Xlsx/xlsm/xltx/xlsb/
PPTX/pptm/Potx/potm
Ppsx/ppsm
Archivo . AAB
App bundle
Formato publicación android
No te descargas la versión que necesitas. Te descargas el archivo y el te pone la correcta
Fichero .msi
Instalable microsof
Archivo .pkg / .dmg
Instalable mac
Archivo .deb
Instalable Linux debían y derivados ubuntu
Archivo .rpm
Instalable Linux red hat y derivados de centos
Archivo .tar.gz
Comprimido básico linux
Archivo .vcf
Vcard file. Información de contactos
Archivo .p12/ pfx
Certificado x509 con su clave privada
Archivo .cer
Certificado x509 sin su clave privada
Archivo. Eml/ .msg
Formato correo
Archivo .mbox
Contenedor de mails
Archivo .pst y .ost
Buzones Outlook
Archivos .nsf
Buzones lotus
Archivo .apk
Instalable android
Archivos .ipa
Instalable ios
Archivo .swf
Fichero flash
Fichero .epub
Libro electrónico
