Tema 3 - Estructuras de datos y algoritmos Flashcards
Que es un TAD
Tipo abstracto de datos, es un modelo matemático para definir tipos de datos (primitivas)
List es un TAD que se implementa con…
Arrays y Listas enlazadas
Set y Multiset son TAD que se implementan con…
Arbol rojo-negro y tabla hash
Queue y Double ended queue son TAD que se implementan con…
Arrays y listas enlazadas
Stack es un TAD que se implementan con
Arrays y listas enlazadas
Priority Queue (Heap) es un tad que se implementa con para…
Monticulo
Graph es un tad que se implementa con…
Matrices y arrays de listas enlazadas
Associative array es un tad que se implementan con…
Tablas hash
Cual es el modelo de una pila(stack)
LIFO (Last In First Out)
Cual es el modelo de una cola (queue)
FIFO (First In First Out)
Push, pop, isEmpty y top son funciones utilizadas en…
Stack(Pila)
enqueue, dequeue, isEmpty y top son funciones utilizadas en…
Queue (Cola)
isEmpty, insertarDelante, insertarDetras, head y tail son funciones utilizadas en…
Listas
Con tail cogemos el elemento nº
N-1
Que es una tabla hash
Estructura de datos con dos entradas (clave y valor) vamos guardando los distintos objetos. Si quiero saber donde van a ir colocados necesito una funcion hash.
A que se le llama colision en las tablas hash
Cuando dos objetos coinciden en la misma posición de la tabla.
Ejemplo: queremos poner DNI’s en la tabla y coincide que ambos estan en el mismo lugar de la tabla
Se utilizaba para hacer caches, indices…
Que es un montículo
Estructura de informacion en forma de arbol que cumple la propiedad del monticulo.
La raiz es la mayor de todos los que hay por debajo de ella y asi sucesivamente.
Sirve para implementar una cola con prioridad (el de máxima prioridad sería la raiz del arbol).
Si son implementados con un arbol binario se le denomina monticulo binario.
Si se implementa con un array los hijos del nodo N seran 2n y 2n + 1
A que se le denomina el grado de un nodo de un árbol
El nº de hijos directos que tiene (o numero de subarboles)
Que es la profundidad de un nodo
Numero de aristas desde la raiz al nodo (el nodo raiz tiene profundidad 0)
Que es la altura de un nodo
Trayectoria mas larga desde ese nodo a una hoja
Que es el factor de equilibrio
La diferencia entre la altura un subarbol izquierdo y uno derecho.
Que tres tipos de recorridos en profundidad hay. Explicalos brevemente
Preorden (RID) –> 1º Raiz 2º Subarbol izquierdo 3º Subarbol derecho
Inorden (IRD) –> 1º Izquierdo 2º Raiz 3º Derecho
Postorden (IDR) –> 1º Izquierdo 2º Derecho 3º Raiz
Que tipos de arboles hay
Arboles binarios y arboles equilibrados
Que dos tipos de arboles binarios hay
Arbol binario de busqueda (Recorrido IRD)
Arbol Fibonacci (caso AVL)
Cual es el factor de equilibrio en los arboles equilibrados
-1 0 o 1
Puede haber una diferencia de maximo un escalon entre el subarbol izquierdo y el derecho
Algunos de los arboles equilibrados son…
AVL (Equilibra mediante rotaciones)
AA
rojo-negro
Splay
Arbol B
Clasifica las siguientes características segun pertenezcan a Arboles B, Arboles B+ o Arboles B*
Cada nodo tiene máximo M hijos
Nodos internos solo contienen claves y punteros
Inserciones y borrados en tiempo log(n) reestructurados en nodos
Garantizan la densidad de ocupación (2/3)
Cada nodo (excepto la raiz) tiene como minimo M/2 claves
Mantiene los datos ordenados
Los nodos hojas estan enlazados entre si
Arbol B
Mantiene los datos ordenados
Inserciones y borrados en tiempo log(n) reestructurados en nodos
Cada nodo tiene máximo M hijos
Cada nodo (excepto la raiz) tiene como minimo M/2 claves
Arbol B+
Nodos internos solo contienen claves y punteros
Los nodos hojas estan enlazados entre si
Arbol B*
Garantizan la densidad de ocupación (2/3)
Que es un grafo conexo
Grafo sin ciclos
Que es un multigrafo
Mas de una arista entre dos vertices
De los siguientes algoritmos relacionados con grafos detalla cada uno brevemente:
Prim
Kruskal
Dijkstra
Bellman-Ford
Ford-Fulkerson
Tarjan
Floyd-Warshall
Prim –> arbol recubridor minimo
Kruskal –> arbol recubridor minimo
Dijkstra –> camino minimo
Bellman-Ford –> camino minimo
Ford-Fulkerson –> maximizar el flujo
Tarjan –> grupos conexos
Floyd-Warshall –> Camino minimo entre 2 vertices
Llamamos signature o magic number a…
Los primeros N bytes de un fichero binario que dicen que formato representa. Si empieza 3E es jpg
Que son los tipos MIME
Cadenas que especifican de que tipo de información estamos hablando (gif, texto xml, texto html…)
Cuales de los siguientes formatos son de tipo imagen
JPG
PNG
TIFF
GIF
BMP
Todos
JPG y PNG se pueden comprimir sin perdida
PNG si, JPG no
GIF auna 512 colores y su compresión es con perdida(V/F)
Falso, 256 y sin perdida
Cuales son el significado de las siglas SVG? Nombra una herramienta que use SVG
Scalable Vector Graphics. Una herramienta es InkScape. SVG se implementa en HTML5 de forma activa
Entre las características de MP3 estan:
Compresión … perdida
Algoritmo –> F……
Usa etiquetas … para catalogar
Con perdida
Transformada de fourier discreta
Etiquetas ID3
Refiriendonos a audio WMA es…
Windows Media Audio
Refiriendonos a audio, FLAC es…
Free Lossless Audio Codec
Que es un codec
Compresor y descompresor de audio, video…
ACC es un codec de audio … perdida
Con
AVI, MKV y ASF no representan un codec si no un…
Contenedor (formato de ficheros para meter audio y video)
.avi es para el S.O … y .mov es para el S.O …
Ms y Apple
De mpg surge MPEG1, 2 y 4. Para que esta dedicado cada uno de ellos
1 –> VHS o CD
2 –> DVD
4 –> HD
Nota: Faltan 2 paginas del tema 3… Extensiones y tipos de ficheros
