ESTRUCTURA DE DATOS Flashcards
¿Cuales son las primitivas del tipo abstracto de datos Pila?
push
pop
top
isEmpty
¿Qué diferencia existen entre una estructura de datos y un tipo abstracto de datos?
El TAD es un modelo matematico (especificación), mientras que la estructura de datos es una implementación
¿Qué otros nombres recibe el tipo abstracto de datos “Array Asociativo” ?
Mapa o Correspondencia
Diccionario
¿Qué poblema o deficiencia nos encontramos en una tabla Hash a la hora de ir registrando nuestros pares (clave,valor) ?
Que pueden dar colisiones, es decir, que para dos claves diferentes (debido a la funcion hash) estas se situen en la misma posicion dentro de la tabla.
¿En que consiste un monticulo max-heap?
En una estructura de datos de tipo arbol en la cual el valor de un nodo es mayor que todos los que tiene por debajo (max-heap)
¿Qué es el grado de un nodo dentro de un arbol?
El numero de hijos directos que tiene ese nodo
¿Que es la profundidad de un nodo?
Numero de aristas desde la raiz a ese nodo
¿Que es la altura de un nodo?
La trayectoria más larga desde ese nodo a una hoja
¿Que tipo de recorrido en un arbol es el llamado Postorden?
Un recorrido en profundidad en el que cual primero se visita el subarbol Izquierdo, luego el subarbol Derecho y por ultimo la Raiz (IDR)
Nombre dos tipos de arboles binarios
ABB (Arbol binario de busqueda)
Arbol de Fibonacci
¿Qué es un arbol balanceado?
Aquel cuyo factor de equilibrio está en el rango [-1,0,1]
Nombre cuatro tipos de arboles auto-balanceados
AVL
Rojo-Negro
AA
Splay
En un arbol B+, ¿que contienen los nodos internos (no hojas)?
Solo las claves para poder navegar en las busquedas
¿Que se persigue en un arbol B* ?
Que haya un buen porcentaje de ocupacion en los nodos? Ej. 2/3
¿Qué peculiaridad tienen los nodos hoja (claves+datos) en un arbol B+?
Están enlazados entre si
Nombre las dos formas fundamentales de implementar un grafo
Matriz de adyacencia (nº de columnas/filas = nº de vertices)
Lista de adyacencia (Array de vertices + Listas enlazadas en cada posicion del array)
¿Como se llama a un grafo que tiene valores númericos en las aristas?
ponderado
¿Que es un grafo conexo? ¿y completo?
Conexo -→ Que todos sus vértices están conectados por un camino
Completo -→ Si cada par de vértices están conectados por una arista
¿Que es el orden de un grafo?
El numero de vertices que tiene
¿Que es un multigrafo?
Aquel que tiene mas de una arista entre dos mismos vertices
Nombre dos algoritmos para calcular el camino minimo entre dos nodos en un grafo
Dijkstra
Bellman-Ford
Nombre dos algoritmos para calcular un arbol de recubrimiento minimo en un grafo
Prim
Kruskal
¿Para que sirve el algoritmo de Ford-Fulkerson?
Calcular camino en un grafo de tal forma que se maximiza el flujo
¿Para que sirve el algoritmo de Tarjan en un grafo?
Para identificar grupos de vertices que están fuertemente conectados
¿Que tipo de fichero es ISAM?
Secuencial + Indexado
Nombre dos tipos de ordenacion externa (de ficheros)
Mezcla directa
Mezcla natural
Nombre cinco extensiones de archivo que se corresponden con contenedores multimedia
avi
mkv
asf
mov
ogg
3gp
WebM
¿Que es FLAC?
Un formato/codec libre de audio sin perdidas (Free Lossless Audio Codec)
¿Que es ID3 en el formato MP3?
Una etiqueta con metadatos que nos permite saber de ese audio el autor, album, etc (para catalogarlos)
¿Que formato tienen los ficheros con extension .docx?
OOXML (Office Open XML) - ECMA 376 (Es un zip)
¿Quien se encarga del estandar del formato PDF?
ISO
Nombre dos lenguajes de descripcion de pagina (orientados a imprimir)
PostScript (ps)
PCL (de HP)
¿Que representa un archivo con extension .dmg?
Una aplicación instalable en MacOS
¿Que representa un archivo con extension .p12?
Un certificado digital con clave privada
¿Que representa un archivo con extension .eml?
Un mensaje de correo electronico
¿Que representa un archivo con extension .pst?
Un buzon de correo de outlook
¿Que representa un archivo con extension .nsf?
Un buzon de correo de Lotus Notes
¿Que representa un archivo con extension .rpm?
Una package de software instalable en la familia de Linux de RedHat
¿Que representa un archivo con extension .deb?
Un software instalable en la familia de Linux de Debian
¿Que representa un archivo con extension .svg?
Un grafico vectorial basado en xml
En un fichero binario, ¿que se conoce como signature o magic number?
A los primeros bytes del fichero que nos sirven para identificar de que tipo se trata
¿Que es un arbol binario lleno?
Aquel en el cada nodo tiene 0 o 2 hijos
¿Que determina el orden de un arbol?
El numero maximo de hijos que PUEDE tener un nodo de dicho arbol
¿Que es el grado de un arbol?
El mayor de los grados de entre todos los nodos
¿Que tipo de recorrido en un arbol es el llamado Inorden?
Un recorrido en profundidad en el que cual primero se visita el subarbol Izquierdo, luego la Raiz y por ultimo el subarbol Derecho (IRD)
NOTA: Sobre un Arbol Binario de Busqueda produce una salida de datos ordenados ascendentemente
¿Que tipo de recorrido en un arbol es el llamado Preorden?
Un recorrido en profundidad en el que cual primero se visita la Raiz, luego el subarbol Izquierdo y por ultimo el subarbol Derecho (RID)
¿Que representa el grado de un vertice en un grafo?
El numero de aristas incidentes
¿Cuales son las tres principales formas de organizacion/acceso a un fichero?
Secuencial, Indexado y Directo
¿Que representa un archivo con extension .webp?
Formato de imagen de Google (soporta modelo con y sin perdidas)
¿A que se refieren los formatos VP8 y VP9?
Codecs de Video de Google
¿Que tipo de formato es Ogg?
Formato Abierto de Contenedor
¿Que tipo de formato es MKV?
Formato Abierto de Contenedor
¿Que tipo de formato es WebM?
Formato Abierto de Contenedor creado por Google
NOTA: Sirve para contener VP8/VP9/AV1 (video) y Vorbis/Opus (audio)
¿A que se refieren los formatos Vorbis y Opus?
H.264 o MPEG4 Part 10
¿Cual es el resultado del algoritmo de Dijkstra?
El camino minimo entre un vertice origen y el resto de nodos
¿Cual es el resultado del algoritmo de Floyd–Warshall?
El camino minimo entre todos los vertices
¿Que tipo de formato es 3GP?
Formato Abierto de Contenedor creado por 3GPP para moviles
¿Que tipo de algoritmos son el de Johnson’s y el de Viterbi?
Otros algoritmos para calculo de camino minimo
¿Con que otro nombre se conoce al formato AVC - Advanced Video Coding?
H.264 o MPEG4 Part 10
¿Con que otro nombre se conoce al formato HEVC - High Efficiency Video Coding?
H.265 o MPEG-H Part 2
¿Que algoritmo de ordenación externa se aprovecha de que haya tiras de datos ya ordenadas?
Mezcla Natural
¿Qué tipo de Algoritmo es el A*?
Un algoritmo voraz para calculo del camino mínimo entre un vértice origen y otro dado de un grafo
