Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

B2 - Apuntes > Tema 3 - Estructuras de datos y algoritmos > Flashcards

Tema 3 - Estructuras de datos y algoritmos Flashcards

1
Q

Que es un TAD

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

List es un TAD que se implementa con…

A

Arrays y Listas enlazadas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Set y Multiset son TAD que se implementan con…

A

Arbol rojo-negro y tabla hash

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

Arrays y listas enlazadas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Stack es un TAD que se implementan con

A

Arrays y listas enlazadas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

Monticulo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Graph es un tad que se implementa con…

A

Matrices y arrays de listas enlazadas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Associative array es un tad que se implementan con…

A

Tablas hash

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Cual es el modelo de una pila(stack)

A

LIFO (Last In First Out)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Cual es el modelo de una cola (queue)

A

FIFO (First In First Out)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Stack(Pila)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

Queue (Cola)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Listas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Con tail cogemos el elemento nº

A

N-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Que es una tabla hash

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

A que se le llama colision en las tablas hash

A

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…

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Que es un montículo

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Que es la profundidad de un nodo

A

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

20
Q

Que es la altura de un nodo

A

Trayectoria mas larga desde ese nodo a una hoja

21
Q

Que es el factor de equilibrio

A

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

22
Q

Que tres tipos de recorridos en profundidad hay. Explicalos brevemente

A

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

23
Q

Que tipos de arboles hay

A

Arboles binarios y arboles equilibrados

24
Q

Que dos tipos de arboles binarios hay

A

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

25
Q

Cual es el factor de equilibrio en los arboles equilibrados

A

-1 0 o 1

Puede haber una diferencia de maximo un escalon entre el subarbol izquierdo y el derecho

26
Q

Algunos de los arboles equilibrados son…

A

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

27
Q

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

A

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)

28
Q

Que es un grafo conexo

A

Grafo sin ciclos

29
Q

Que es un multigrafo

A

Mas de una arista entre dos vertices

30
Q

De los siguientes algoritmos relacionados con grafos detalla cada uno brevemente:

Prim
Kruskal
Dijkstra
Bellman-Ford
Ford-Fulkerson
Tarjan
Floyd-Warshall

A

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

31
Q

Llamamos signature o magic number a…

A

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

32
Q

Que son los tipos MIME

A

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

33
Q

Cuales de los siguientes formatos son de tipo imagen

JPG
PNG
TIFF
GIF
BMP

A

Todos

34
Q

JPG y PNG se pueden comprimir sin perdida

A

PNG si, JPG no

35
Q

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

A

Falso, 256 y sin perdida

36
Q

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

A

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

37
Q

Entre las características de MP3 estan:

Compresión … perdida
Algoritmo –> F……
Usa etiquetas … para catalogar

A

Con perdida
Transformada de fourier discreta
Etiquetas ID3

38
Q

Refiriendonos a audio WMA es…

A

Windows Media Audio

39
Q

Refiriendonos a audio, FLAC es…

A

Free Lossless Audio Codec

40
Q

Que es un codec

A

Compresor y descompresor de audio, video…

41
Q

ACC es un codec de audio … perdida

A

Con

42
Q

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

A

Contenedor (formato de ficheros para meter audio y video)

43
Q

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

A

Ms y Apple

44
Q

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

A

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

45
Q

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

A

B2 - Apuntes (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions