BII Tema 3 Secc Estructuras De Datos Flashcards

1
Q

Concepto monticulo

A

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

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

Arboles equilibrados
ejemplos

A

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

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

Arboles multicamino
(Árboles B)

A

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

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

Recorridos en profundidad de un arbol

A

Preorden (RID)
Inorden (IRD)
Postorden (IDR)

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

Grado de un nodo

A

N° de hijos directos que tiene ese nodo

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

Profundidad de un nodo

A

N° de aristas de la raíz al nodo

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

Altura nodo

A

Camino más largo de ese nodo hasta una hoja

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

Factor equilibrio de un árbol

A

Diferencia altura entre el subárbol izquierdo con el subárbol derecho

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

Peso del arbol

A

Sumar todos los nodos

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

Orden del arbol

A

N° máximo de hijos que puede tener un nodo

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

Grado arbol

A

N° máximo de hijos que tiene alguno de sus nodos

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

Nivel del arbol

A

Es la altura de la raíz
la altura de la raiz
árbol vacío sería 0. (Ojo según autor)

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

Grafos

A

Estructuras que son un red de nodos

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

Grafo dirigidos y no dirigidos

A

Grafos dirigidos : tienen un sentido definido
Grafos no dirigidos : no tienen un sentido, va en los 2 sentidos

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

Multigrafo

A

Cuando hay más de un camino para llegar entre dos nodos / vertices

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

Grafo etiquetado/ponderado

A

Cuando tiene pesos en las aristas

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

Grafo conexo

A

Todos los Nodos conectados entre si por al menos un camino

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

Grafo. Grado de un vértice/nodo

A

N° de aristas incidentes

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

Orden de un grafo

A

N° de vertices

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

Grafos. manera de representarlos

A

Lista adyacencia
Matrices adyacencia

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

TAD.

A

Tipo abstracto de datos.
Modelo matemático para definir un tipo de dato/info. Esa info se define mediante sus primitivas( operaciones)

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

Estructura de datos

A

Concepto más concreto orientado a la implementación

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

Implementaciones estructura de datos

A

Lista ( secuencia)
Colas (queue)
Pila ( stack)
Priority queue (heap)
Árbol
Grafo
Array asociativo

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

Estructura datos
Estáticas y dinamicas

A

-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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Concepto tabla hash
Gran estructura de datos Estructura clave valor - clave : para indexar - valor: respecto de su clave. El valor que indexamos
26
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
27
Acceso a información en ficheros. Acceso secuencial
Ejemplo: cinta ( va siempre hacia adelante el almacenamiento de datos) Se añade sobre el final
28
Acceso a la información en ficheros Acceso directo
Acceso directo( a los registros) 2 formas - clave registro - función (claves)
29
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
30
Fichero isam
Fichero secuencial + indexado
31
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
32
Algoritmos Dijstra
Algoritmo camino mínimo entre dos nodos OSPF
33
Algoritmos Bellman- ford
Camino mínimo entre dos nodos RIP
34
Algoritmo Floyd warshall
Camino mínimo todos los pares de nodos Todos con todos
35
Algoritmo A*
Camino minimo
36
Algoritmo Prim
Recubrimiento minimo
37
Algoritmo kruskal
Recubrimiento minimo
38
Algoritmo tarjan
Grupos conexos. Quién está conectado con quién
39
Algoritmo ford- fulkerson
Camino para maximizar flujo
40
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
41
Ficheros audio Sin perdidas
FLAC - .flac
42
FICHERO .WAV
Contenedor audio .WAV, .wave
43
Concepto fichero .wma
Microsoft. Existen 4 codecs
44
Formatos de vídeo Contenedores
Mkv Avi Asf Ogg 3gp (para móviles) MP4 Mov Webm(basado en mkv)
45
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
46
Archivos imagen
JPG -compresión con pérdidas PNG - compresión sin perdidas Gif Tiff BMP Svg
47
Archivos open office
Odt - texto Ott - texto (plantilla) Ods - hoja cálculo Odp - presentación .....
48
Archivo PDF/A
PDF a largo plazo
49
Ficheros ofimática
Xls Doc /dot Docx/docm/dotx/dotm RTF ( texto enriquecido) Xlsx/xlsm/xltx/xlsb/ PPTX/pptm/Potx/potm Ppsx/ppsm
50
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
51
Fichero .msi
Instalable microsof
52
Archivo .pkg / .dmg
Instalable mac
53
Archivo .deb
Instalable Linux debían y derivados ubuntu
54
Archivo .rpm
Instalable Linux red hat y derivados de centos
55
Archivo .tar.gz
Comprimido básico linux
56
Archivo .vcf
Vcard file. Información de contactos
57
Archivo .p12/ pfx
Certificado x509 con su clave privada
58
Archivo .cer
Certificado x509 sin su clave privada
59
Archivo. Eml/ .msg
Formato correo
60
Archivo .mbox
Contenedor de mails
61
Archivo .pst y .ost
Buzones Outlook
62
Archivos .nsf
Buzones lotus
63
Archivo .apk
Instalable android
64
Archivos .ipa
Instalable ios
65
Archivo .swf
Fichero flash
66
Fichero .epub
Libro electrónico