Tema 3 - Estructuras de datos y algoritmos

Question 1

Que es un TAD

Answer 1

Tipo abstracto de datos, es un modelo matemático para definir tipos de datos (primitivas)

Question 2

List es un TAD que se implementa con…

Answer 2

Arrays y Listas enlazadas

Question 3

Set y Multiset son TAD que se implementan con…

Answer 3

Arbol rojo-negro y tabla hash

Question 4

Queue y Double ended queue son TAD que se implementan con…

Answer 4

Arrays y listas enlazadas

Question 5

Stack es un TAD que se implementan con

Answer 5

Arrays y listas enlazadas

Question 6

Priority Queue (Heap) es un tad que se implementa con para…

Answer 6

Monticulo

Question 7

Graph es un tad que se implementa con…

Answer 7

Matrices y arrays de listas enlazadas

Question 8

Associative array es un tad que se implementan con…

Answer 8

Tablas hash

Question 9

Cual es el modelo de una pila(stack)

Answer 9

LIFO (Last In First Out)

Question 10

Cual es el modelo de una cola (queue)

Answer 10

FIFO (First In First Out)

Question 11

Push, pop, isEmpty y top son funciones utilizadas en…

Answer 11

Stack(Pila)

Question 12

enqueue, dequeue, isEmpty y top son funciones utilizadas en…

Answer 12

Queue (Cola)

Question 13

isEmpty, insertarDelante, insertarDetras, head y tail son funciones utilizadas en…

Answer 13

Listas

Question 14

Con tail cogemos el elemento nº

Answer 14

N-1

Question 15

Que es una tabla hash

Answer 15

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.

Question 16

A que se le llama colision en las tablas hash

Answer 16

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…

Question 17

Que es un montículo

Answer 17

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

Question 18

A que se le denomina el grado de un nodo de un árbol

Answer 18

El nº de hijos directos que tiene (o numero de subarboles)

Question 19

Que es la profundidad de un nodo

Answer 19

Numero de aristas desde la raiz al nodo (el nodo raiz tiene profundidad 0)

Question 20

Que es la altura de un nodo

Answer 20

Trayectoria mas larga desde ese nodo a una hoja

Question 21

Que es el factor de equilibrio

Answer 21

La diferencia entre la altura un subarbol izquierdo y uno derecho.

Question 22

Que tres tipos de recorridos en profundidad hay. Explicalos brevemente

Answer 22

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

Question 23

Que tipos de arboles hay

Answer 23

Arboles binarios y arboles equilibrados

Question 24

Que dos tipos de arboles binarios hay

Answer 24

Arbol binario de busqueda (Recorrido IRD)
Arbol Fibonacci (caso AVL)

Question 25

Cual es el factor de equilibrio en los arboles equilibrados

Answer 25

-1 0 o 1 Puede haber una diferencia de maximo un escalon entre el subarbol izquierdo y el derecho

Question 26

Algunos de los arboles equilibrados son...

Answer 26

AVL (Equilibra mediante rotaciones) AA rojo-negro Splay Arbol B

Question 27

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

Answer 27

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)

Question 28

Que es un grafo conexo

Answer 28

Grafo sin ciclos

Question 29

Que es un multigrafo

Answer 29

Mas de una arista entre dos vertices

Question 30

De los siguientes algoritmos relacionados con grafos detalla cada uno brevemente: Prim Kruskal Dijkstra Bellman-Ford Ford-Fulkerson Tarjan Floyd-Warshall

Answer 30

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

Question 31

Llamamos signature o magic number a...

Answer 31

Los primeros N bytes de un fichero binario que dicen que formato representa. Si empieza 3E es jpg

Question 32

Que son los tipos MIME

Answer 32

Cadenas que especifican de que tipo de información estamos hablando (gif, texto xml, texto html...)

Question 33

Cuales de los siguientes formatos son de tipo imagen JPG PNG TIFF GIF BMP

Answer 33

Todos

Question 34

JPG y PNG se pueden comprimir sin perdida

Answer 34

PNG si, JPG no

Question 35

GIF auna 512 colores y su compresión es con perdida(V/F)

Answer 35

Falso, 256 y sin perdida

Question 36

Cuales son el significado de las siglas SVG? Nombra una herramienta que use SVG

Answer 36

Scalable Vector Graphics. Una herramienta es InkScape. SVG se implementa en HTML5 de forma activa

Question 37

Entre las características de MP3 estan: Compresión ... perdida Algoritmo --> F...... Usa etiquetas ... para catalogar

Answer 37

Con perdida Transformada de fourier discreta Etiquetas ID3

Question 38

Refiriendonos a audio WMA es...

Answer 38

Windows Media Audio

Question 39

Refiriendonos a audio, FLAC es...

Answer 39

Free Lossless Audio Codec

Question 40

Que es un codec

Answer 40

Compresor y descompresor de audio, video...

Question 41

ACC es un codec de audio ... perdida

Answer 41

Con

Question 42

AVI, MKV y ASF no representan un codec si no un...

Answer 42

Contenedor (formato de ficheros para meter audio y video)

Question 43

.avi es para el S.O ... y .mov es para el S.O ...

Answer 43

Ms y Apple

Question 44

De mpg surge MPEG1, 2 y 4. Para que esta dedicado cada uno de ellos

Answer 44

1 --> VHS o CD 2 --> DVD 4 --> HD

Question 45

Nota: Faltan 2 paginas del tema 3... Extensiones y tipos de ficheros