Bloque2-Tema3-Estructuras de datos Flashcards
Que es un tipo abstracto mde datos?
Modelo matematico para definir tipo de datos (Primitivas)
Un tad va con sus primitivas. Las primitivas definen al tipo abstracto de datos
Que es una estructura de datos?
Concepto mas concreto orientado a la implementacion.
Implementacion tipicas de una Lista?
Array, Lista enlazada.
Implementacion tipicas de un set/Multiset?
Arbol rojo negro, tabla hash.
Implementacion tipicas de una cola o una bicola.
Array, lista [doble] enlazada.
Implementaciones tipicas de una pila?
Array, lista enlazada.
Implementaciones tipicas de una priority queue
Monticulo.
Implementacion tipicas de un grafo?
Matriz, array de listas enlazadas.
Implementaciones tipicas de un array asociativo (Diccionario, Mapa)?
Tabla hash.
Que es una bicola?
Los elementos se pueden insertar o eliminar por el principio o por el final.
Cual es una estructura LIFO?
Pila
Cual es una estructura FIFO?
Cola
Primitivas de una pila?
Push, pop, isEmpty, Top,
Primitivas de una cola?
Enqueu, dequeue, isEmpty, peek.
Primitivas de una lista?
IsEmpty, InsertarDelante, InsertarDetras, head, tail.
Que es una tabla hash?
Una tabla hash, matriz asociativa, hashing, mapa hash, tabla de dispersión o tabla fragmentada es una estructura de datos que implementa el tipo de dato abstracto llamado Diccionario.
Asocia llaves o claves con valores.
Que puede suceder si una funcion hash de una tabla hash esta mal diseñada?
Que se produzcan colisiones.
Direccionamiento cerrado o hashing abierto
Cada casilla en el array referencia a una lista con los registros insertados que colisionan en dicha casilla.
Direccionamiento abierto o hashing cerrado
Las tablas hash de direccionamiento abierto pueden almacenar los registros directamente en el array. Las colisiones se resuelven mediante un sondeo del array, en el que se buscan diferentes localidades del array (secuencia de sondeo) hasta que el registro es encontrado o se llega a una casilla vacía, indicando que no existe esa llave en la tabla.
Que es un monticulo?
Estructura basa en arbol que cumple con la propiedad del monticulo.
Hay Max_Heap y MIn_Heap. En Max Heap el valor superior es mayor o igual que todos los que tiene por dbeajo.
Tiene una complejidad de O(log(n))
Si se implementa con un arbol binario-> Monticulo binario.
Que contiene una tabla hash?
La propia tabla(Con indices y valores) + zona de colisiones.
Hablando de arboles, que es el grado de un nodo?
Numero de hijos directos.
Hablando de arboles, que es la profundidad de nodo?
Nº de aristas desde la raiz al nodo.
Nodo raiz = 0
Que es la altura de un nodo?
Trayectoria mas larga desde ese nodo a una hoja.
Que es el factor de equilibrio(FE)?
Diferencia altura entre subarbol izquierdo y derecho.
Que tipos de recorridos en profundidad conoces?
Preorden(Raiz, Izquierda, Derecha)
Inorden(Izquierda, Raiz, Derecha)
PostOrden(Izquierda, Derecha, Raiz)
Tipos de arboles?
-Arboles binarios
-Arboles equilibrados(Autobalanceados)
-Arboles B
-Arboles B+
-Arboles B*
Tipos de arboles binarios?
-Arbol binario de busqueda (Si lo recorres en inorden dan los elementos ordenados)
-Arbol de Fibonacci (Caso particular de AVL)-> Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci.
Que es un arboles equilibrados(Autobalanceados)?
Un arbol dond el factor de equilibrio es -1, 0 o 1.
Que tipos de arboles equilibrados(Autobalanceados) conoces?
-AVL
-AA
-Rojo Negro
-Splay
-Arbol B
Que es un arbol B?
Un arbol donde cada nodo puede tener mas de dos hijos(Orden) M.
-Mantiene los datos ordenadores
-Inserciones y borrados en tiempo log(n)
-Cada nodo tiene como maximo M hijos.
-Cada nodo(excepto la raiz) tiene como minimo M/2 claves.
Caracteristicas de los arboles B+?
- Nodos internos solo contienen claves y punteros.
-Los nodos hojas estan enlazados entre si.
Que es un arbol B*?
Uno que garantiza al menos una densidad de ocupacion de 2/3.
Donde empieza el nivel de un arbol, en 0 o en 1?
-No hay consenso si empieza en 0 o 1. Asi que ojo en el examen. Mirate la imagen par entender el nivel.
Altura del arbol: profundidad maxima de un nodo + 1
Que es el peso de un arbol?
Numero total de nodos de un arbol.
Que es el orden de un arbol?
Es el numero maximo de hijos que puede tener un nodo. Por lo que el orden limita al grado.
Cuando esta unn arbol binario lleno?
Cuando todos los nodos tienen 0 o 2 hijos.
Que hace la primitiva crear(constructor)
Crea la pila vacia.
Tipos de grafos?
-Dirigidos o digrafo-> Las aristan tienen un sentido definido.
-No digiridos.
-Grafo conexo
-Multigrafo-Mas de una arista entre dos vertices.
-Grafo etiquetado/ponderado-> Peso numero en aristas.
Que es un grafo conexo?
un grafo conexo o conectado es un grafo en que todos sus vértices están conectados por un camino o por un semicamino
Que es un grafo dirigido?
Las aristan tienen un sentido definido.
Que es un multigrafo?
Cuando hay mas de una arista entre dos vertices.
Que es un grafo ponderado.
Es un grafo en el que las aristas tienen un valor o peso asociado.
Que es el orden del grafo?
Numero de vertices.
Que es el grado de un vertice?
Numero de aristas incidentes.
Formas de representar un grafo?
Listas de adyacencia.
Matrices de adyacencia.
Que es un algoritmo recubridor minimo?
Es el que menos gasta para tocar todos los nodos.
Que es el algoritmo de camino minimo?
El que encuentra un camino entre dos vértices o nodos.
Algoritmos de camino minimo?
-Dijkstra (un solo par de vertices,)
-Bellman-Ford
-A*
-Floyd-Warshall (Te da todo los pares de caminos minimos.)
Algoritmos recubridores minimos?
-Prim
-Kruskal (Grafo conexo y ponderado)
De que se encarga el algoritmo de Tarjan?
De encontrar grupos fuertemente conexos.
De que se encarga el algoritmo Ford-Fulkerson?
Encontrar caminos para maximizar el flujo.
Tipos de acceso a ficheros.
-Acceso Scuencial (Ej: Cinta)
-Busqueda desde el inicio.
-Borrado logico
-Se añade sobre el final
-Acceso directo
-Clave del registro-> Posicion en archivo
-Funcion(Clave)-> Posicion en archivo.
-Acceso indexado.
-Se busca la clave el indice ordenado -> Posicion
Tipos de ordenacion de ficheros externa.
-Mezcla directa: -> combina dos o mas secuencias en una sola secuencia ordenada por medio de la selección.
-Mezcla natural->Aprovecha la existencia de secuencias ya ordenadas dentro de los datos de los archivos
ISAM es secuencial + indexado?
Si
Que es un tipo de medio?
Un identificador de dos partes para formatos de archivo transmitidos por Internet.
Que significa JPEG?
Joint Photographic Expert Group
Tipos MIME comunes?
image/gif
text/xml
text/html
application/javascript
video/mpeg
application/pdf
Que tipo de archivo es JPG?
Fichero de imagen con compresion con perdidas.
Existen variantes sin perdidas.
JPEG2000 y Lossless JPEG
Que tipo de archivo es PNG?
Fichero de imagen con compresion sin perdidas.
-Usa trasparencia
-True color(24 bits)
-Sin animacion.
Que tipo de archivo es GIF?
Fichero de imagen.
-Comprension LZW sin perdida
-Animation y trasparencia
-256 colores.
Que tipo de archivo es TIFF?(Tagged)
Fichero de imagen con comprension sin perdida(Multipagina)
Que tipo de archivo es BMP?(Microsoft)
Comprension RLE sin perdidas.
En un fichero binario, para que sirve el signature(magic number)
Ocupa los primeros bytes de información de un fichero. Identifican el tipo de fichero.
Que es SVG?
Scalable Vector Graphic.
Tipo MIME de SVG?
image/svg+xml
Herramienta para hacer SVGs?
INKScape
Que es el fichero DOCX?
Fichero de ofimatica, que es en realidad un zip con muchos xml dentro (ooxml = Office open xml)
ECMA de ooxml = Office open xml?
ECMA 376
Que tipos de extensiones tiene los ficheros de WORD?
.doc
.docx
.dot
.dotm
.dotx
m-> Macro
t-> Template
Que tipos de extensiones tiene los ficheros de EXCEL?
.xls
.xlsx
.xlsm (macro habilitado)
.xlt
.xlsb
m-> Macro
t-> Template
Cual es el formato de un fichero excel que tiene una macro habilitada.
xlsm
m-> Macro
t-> Template
Que tipos de extensiones tiene los ficheros de PowerPoint?
.ppt
.pptx
.pps
.pot
.pptm
.potm
.ppsx
.ppsm
m-> Macro
t-> Template
Que es el tipo de fichero .rtf
Rich text de Microsoft.
Tipos de ficheros de PDF?
ISO 32000-1:2008
PDA/A (Largo plazo)
Tipos de ficheros de impresion?
.PS (Postscript Vectorial)
.PCL
Tipos de ficheros de texto de open office?
.ODT (Documento)
.OTT (Plantilla)
T final de texto.
Tipos de ficheros de hoja de calculo de open office?
.ODS
S cuando es hoja de calculo
Tipos de ficheros de presentacion de open office?
.ODP
P de presentacion
Otros formatos de fichero de open office
.ODG
.ODC
.ODF
.ODI
.ODH
.ODB
Que es el tipo de fichero .exe?
Ejecutable de Microsoft
Que es el tipo de fichero .msi?
Instalable de Microsoft
Que es el tipo de fichero .dmg o .pkg?
Instalable de MAC. (Lo llaman archivo de imagen)
Que es el tipo de fichero .deb?
Instalable de Linux DEBIAN y derivados como UBUNTU
Que es el tipo de fichero .rpm?
Instalable de Linux REDHAT y derivados como CENTOS
Que es el tipo de fichero .tar.gz?
Comprimido basico de linux
Que es el tipo de fichero .vcf?
Vcard File -> Informacion de contacto
Que tipo de fichero es .p12 o .pfx
Certificado x509 con su clave privada
Que tipo de fichero es .cer?
Certificado x509 sin su clave privada
Que tipo de formato es .eml(RFC2822) o .msg?
Formato de un correo.
Que tipo de formato es .mbox ?
Contenedor de mails -> RFC 4155
Que tipo de formato es .pst o .ost
Buzones de outlook
Que tipo de formato es .nsf
Buzones de lotus.
Que tipo de formato es .apk
Instalable de android
aab, instalable que sustituye a apk
Que es el formato .ipa
instalable de IOS
Que tipo de formato es .csv
Texto formateado con comas/puntos y coma
Que tipo de formato es swf
Fichero con “pelicula” flash
Que tipo de formato es epub
Libro electronico
Que tipo de formato es .ISO
Una imagen ISO es un archivo informático donde se almacena una copia o imagen exacta de un sistema de archivos.
Que es un CODEC?
Es un programa o dispositivo hardware capaz de codificar o decodificar una señal o flujo de datos digitales.
Que es un contenedor?
Una especie de cajon para audio y video.
Que formatos de contenedor conoces?
.MKV
.AVI
.ASF
.OGG
.3GP
.MP4
.MOV
.WebM (Vorbis/opus audio y VP8, VP9 y AV1 para video)
Que es el fichero .Mp3?
Formato de audio.
-Compresion con perdidas.
-Etiqueta ID3(Identifica autor, album, etc)
Que es el fichero .WAV?
-Contenedor de AUDIO
-admite codec ACM(Compresion) y LPCM(Sin compresion)
Que es el fichero .FLAC?
FOrmato de audio.
-Compresion sin perdidas.
Que es el fichero .WMA
Formato de audio.
Que es el fichero .AC3
Audio
Compresion con perdidas multicanal
Que es .AAC / .m4a / .m4b / .3gp
Audio
Compresion con perdidas
Que es el formato .OPUS
Audio
compresion con perdidas.
Que es el formato .VORBIS
Audio
compresion con perdidas.
Que formatos de video conoces que no sean de contenedor.
-DIVX y XDIV
-AVC
-HEVC
-VVC
-AV1
-VP8
-VP9
-MPEG-1 Part 2
-MPEG-2 Part 2
-MPEG-4 Part 2
-WMV
-Theora
Que formatos de video son usados por youtube?
AV1, VP8 y VP9
