B2T3 EEDD

Question 1

TAD

Answer 1

Tipo Abstracto de Datos.
Modelo matemático para definir tipos de datos (primitivas)

Question 2

stack

Answer 2

Lista circular LIFO
push, pop, isEmpty, top

Question 3

queue

Answer 3

Lista circular FIFO
enQueue, deQueue, isEmpty, top

Question 4

lista

Answer 4

EEDD secuencia. Ordenados de manera consecutiva
isEmpty, insertarDelante, insertarDetras, head, tail

Question 5

Tabla Hash

Answer 5

Se añaden elementos sabiendo la posición que ocupa cada dato insertado.
Si está mal diseñado se producen colisiones.
Solución direcc. abierto/cerrado

Question 6

Montículo

Answer 6

Max-heap: la raíz el valor más alto del árbol
Min-heap: la raíz el valor más bajo del árbol

Question 7

Grado (árboles)

Answer 7

Número de hijos directos que tiene

Question 8

Orden (árboles)

Answer 8

Número máximo de hijos que puede tener un nodo

Question 9

Profundidad de nodo

Answer 9

Aristas de la raíz al nodo.
En raíz profundidad =0

Question 10

Altura de nodo

Answer 10

Trayectoria más larga del nodo a una hoja.
Altura en cada hoja = 0

Question 11

Peso

Answer 11

Número de nodos del árbol

Question 12

Factor de equilibrio

Answer 12

Diferencia de altura entre subárbol izquierdo y derecho.

Question 13

Tipos de árboles equilibrados (autobalanceados)

Answer 13

-AVL (rotaciones)
-AA
-Rojo-negro
-Splay
-Árbol B

Question 14

Recorridos en profundidad

Answer 14

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

Question 15

Árboles multicamino

Answer 15

-Árbol B: Cada nodo puede tener más de 2 hijos, orden M
Datos ordenados
Inserciones y borrados en tiempo log(n)
Cada nodo tiene máximo M hijos
Cada nodo tiene como mínimo M/2 hijos
-Árbol B+:
Nodos internos solo contienen claves y punteros
Los nodos hojas están enlazados entre sí
-Árbol b*
Garantiza densidad de ocupación 2/3

Question 16

Tipos de grafo

Answer 16

-Dirigidos
-No dirigidos
-Conexo: todos sus vértices conectados por 1 camino
-Multigrafo: más de una arista entre 2 vértices

Question 17

Orden del grafo

Answer 17

Número de vértices (nodos)

Question 18

Grado de un vértice

Answer 18

Número de arcos incidentes en el vértice

Question 19

Tipos de representación de grafos

Answer 19

-Matriz de adyacencia -> desperdicia memoria
-Lista de adyacencia

Question 20

Algoritmos árbol recubridor mínimo

Answer 20

Cubre todos los nodos con el menor coste posible.
Prim y Kruskal

Question 21

Algoritmos camino mínimo

Answer 21

-Dijsktra
-Bellman-Ford
-A*
-Johnson
-Viterbi

Question 22

Otros algoritmos

Answer 22

-Ford-Fulkerson: camino para maximizar flujo
-Tarjan: grupos conexos
-Floyd-Warshall: camino entre 2 vértices

Question 23

Tipos de acceso a ficheros

Answer 23

-Acceso secuencial:
Búsqueda desde el inicio
Borrado lógico
Se añade sobre el final
-Acceso directo(a los registros)
Clave del registro => posición en archivo
Función sobre la clave => posición en archivo
-Acceso indexado. Fichero datos + fichero índice.
Se busca la clave sobre el índice ordenado y nos da posición en archivo
-Caso híbrido => ISAM (ej. MyISAM en MySQL).
Indexado para índice, secuencial para datos

Question 24

Ordenación de ficheros (externa, no en memoria)

Answer 24

-Mezcla directa, haciendo particiones y ordenando por pares
-Mezcla natural, tiene en cuenta los tramos ya ordenados

Question 25

Tipos fichero imagen

Answer 25

JPEG, PNG, GIF, TIFF, BMP, SVG, webp

Question 26

Tipos fichero audio

Answer 26

MP3, WAV, FLAC, WMA, AC3, AAC, OPUS, VORBIS(.ogg)

Question 27

Contenedores vídeo

Answer 27

MKV, AVI, ASF, OFF, 3GP, MP4, MOV, webM, OGM

Question 28

Códecs vídeo

Answer 28

DIVX/XDIV, AVC(264), HEVC(265), VVC(266), AV1, VP8, VP9, MPEG-1, MPEG-2, MPEG-4, WMV, Theora

Question 29

Tipos ficheros extras

Answer 29

t/o = template, m = macro, b = binario xls, rtf, open office, PDF/A, PS(PostScript), PCL, fuentes(otf, otc, ttf, ttc, tte, woff, woff2