Tema3_Seccion1_EstructuraDatos Flashcards
¿Cuales son las primitivas del tipo abstracto de datos Pila?
- push
- pop
- top
- isEmpty
¿Qué otros nombres recibe el tipo abstracto de datos “Array Asociativo” ?
- Mapa o Correspondencia
- Diccionario
¿Qué es el grado de un nodo dentro de un arbol?
El numero de hijos directos que tiene ese nodo
¿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é 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é 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.
¿Que es la profundidad de un nodo?
Numero de aristas desde la raiz a ese nodo
Nombre dos tipos de arboles binarios
- ABB (Arbol binario de busqueda)
- Arbol de Fibonacci
¿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 cuatro tipos de arboles auto-balanceados
- AVL
- Rojo-Negro
- AA
- Splay
¿Qué es un arbol balanceado?
Aquel cuyo factor de equilibrio está en el rango [-1,0,1]
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
¿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
¿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 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 un arbol de recubrimiento minimo en un grafo
- Prim
- Kruskal
Nombre dos algoritmos para calcular el camino minimo entre dos nodos en un grafo
- Dijkstra
- Bellman-Ford
¿Para que sirve el algoritmo de Ford-Fulkerson?
Calcular camino en un grafo de tal forma que se maximiza el flujo
¿Que tipo de fichero es ISAM?
Secuencial + Indexado
¿Para que sirve el algoritmo de Tarjan en un grafo?
Para identificar grupos de vertices que están fuertemente conectados
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)
Nombre dos lenguajes de descripcion de pagina (orientados a imprimir)
- PostScript (ps)
- PCL (de HP)
¿Quien se encarga del estandar del formato PDF?
ISO
¿Que formato tienen los ficheros con extension .docx?
OOXML (Office Open XML) - ECMA 376 (Es un zip)
¿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 .svg?
Un grafico vectorial basado en xml
¿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 .eml?
Un mensaje de correo electronico
¿Que representa un archivo con extension .deb?
Un software instalable en la familia de Linux de Debian
¿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
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
¿Cuales son las tres principales formas de organizacion/acceso a un fichero?
Secuencial, Indexado y Directo
¿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
¿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)
¿Que tipo de formato es 3GP?
Formato Abierto de Contenedor creado por 3GPP para moviles
¿Con que otro nombre se conoce al formato AVC - Advanced Video Coding?
H.264 o MPEG4 Part 10
¿A que se refieren los formatos Vorbis y Opus?
Codecs de Audio con perdidas relacionados con el contenedor Ogg
¿Con que otro nombre se conoce al formato HEVC - High Efficiency Video Coding?
H.265 o MPEG-H Part 2
¿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 algoritmos son el de Johnson’s y el de Viterbi?
Otros algoritmos para calculo de camino minimo
¿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
