b2t3 - Árboles y Estructura de datos Flashcards
Qué es un Tipo Abstracto de Datos (TAD) y en qué se diferencia de una estructura de datos?
Modelo matemático para definir tipos de datos (primitivas = comportamientos)
La estructura de datos es la implementación de un TAD
Qué primitivas tiene el TAD pila (stack)?
Qué otras operaciones se pueden ver?
Qué concepto maneja?
push y pop.
A veces, menos oficialmente se usa peek o top, que es consultar el último campo de la pila, pero sin sacarlo, sólo consulta.
size → Consultar el tamaño
empty → devuelve true si está vacía y false si no
Concepto LIFO
Qué primitivas tiene el TAD cola(queue)?
Qué otras operaciones se pueden ver?
Qué concepto maneja?
queue y dequeue
A veces, menos oficialmente se usa top, que es consultar el último campo de la cola, pero sin sacarlo, sólo consulta.
size → Consultar el tamaño
isEmpty → devuelve true si está vacía y false si no
Concepto FIFO
Qué primitivas tiene el TAD lista ?
insertarDeltante y insertarDetrás,
head → te da el primer elemento
tail → te da todos los elementos menos el head
isEmpty → devuelve true si está vacía y false si no
Qué implementaciones tienen las siguientes TAD? (no demasiado preguntable)
List (secuencia)
set / multiset
Queue / Double queue
Priority Queue (heap)
Tree
Graph
Associative Array (diccionario, mapa) (clave valor)
List (secuencia) → Array, Lista enlazada
set / multiset → Array, Rojo-negro, tabla hash
Queue / Double queue → Array, Lista enlazada / lista doblemente enlazada
Stack → Array, Lista enlazada
Priority Queue (heap) → Montículo (propiedad)
Tree
Graph → Matriz, Array de Listas enlazadas
Associative Array (diccionario, mapa) (clave valor) → Tabla hash
Cómo es la función hash que se usa en las tablas hash para generar la key?
[valor a guardar] mod 250 → Esto da como resultado el resto de dividir el valor / 250.
Qué es el concepto de colisión en una tabla hash?
Cuando se cargan más de 250 elementos en la tabla hash y por tanto varios elementos pueden dar el mismo resultado de” [valor elemento] mod 250” y por tanto la misma key
Qué es un MONTÍCULO?
Estructura basada en árbol, que cumple la propiedad del montículo:
max heap → el nodo raiz es el mayor de todo el árbol. Igualmente, cada nodo es el mayor de sus nodos hijos.
min heap → el nodo raiz es el menor de todo el árbol. Igualmente, cada nodo es el menor de sus nodos hijos.
Si se implementa con un árbol binario se llama montículo binario
Explica los siguientes concetos de los ÁRBOLES
Raíz
Rama
Hoja
Nivel
Profundidad
Altura del árbol
Altura de un nodo
Peso
Orden
Grado
Árbol binario
Árbol binario lleno
Árbol binario perfecto
Raíz → Nodo sin padres
Rama → Los nodos que tienen al menos un hijo y no son la raíz
Hoja → Nodo sin hijos
Nivel → El nivel vertical donde está el nodo, o los saltos desde la raíz. La raíz en casi todos los sitios se dice que es 0 y en otros 1
Peso → Nº de nodos del árbol
Altura del árbol → nº de saltos (aristas) en la trayectoria más larga de la raiz nodo hasta una hoja
Altura de un nodo → la trayectoria más larga del nodo hasta una hoja (ojo, las hojas son altura =0, aunque no sea la hoja a más profunidad!)
Profundidad → Nº de saltos (aristas) desde el nodo hasta la raíz
Orden → Nº máximo teórico de hijos que puede tener un nodo potencialmente, aunque no los tenga. En árbol binario el orden es 2
Grado → Nº de nodos hijos máximo concreto que tiene uno de los nodos del árbol
Árbol binario → Árbol donde el nº máximo de hijos de un nodo es 2, es decir, es de orden 2
Árbol binario lleno → Árbol binario en el que la raíz y todas las ramas tiene 2 hijos. Otra forma de decirlo es que todos los nodos salvo la raíz tiene 2 o 0 hijos
Árbol binario perfecto → Árbol binario donde todas las hojas están al mismo nivel
En los árboles, qué es el FE o Factor de equilibrio?
Factor de equilibrio (FE) → diferencia de altura entre el subárbol izquierdo y el derecho de -1, 0 o +1
Qué tipos de árboles equilibrados o autobalanceables más importantes hay?
AVL (rotación)
AA
Rojo-Negro
Splay
Árbol B
Con qué concepto se consigue el equilibrio en los árboles AVL (balanceables o equilibrados)?
Con la rotación de nodos
Qué tipos de árboles binarios más importantes hay?
Árbol binario de búsqueda → Recorrido In Orden (IRD) → elementos ordenados
Árbol de Fibonacci → caso particular de AVL
Qué tipos de recorridos de árboles en profundidad hay?
RID → Pre Orden
IRD → In Orden
IDR → Post Orden
(La raiz es la que se mueve en las siglas, como truco nemotécnico)
Cuál es la lógica para aplicar los recorridos en profundidad PreOrden, InOrden y PostOrden?
Se visita (escribe) lo que indican las siglas, siempre que no se pueda navegar más. Es decir que cuando al ir a I o D, ese nodo tiene hijos, se aplica de nuevo las siglas del algoritmo a ese nuevo subárbol. “Se aplica el algoritmo recursivamente a cada subárbol”
Cómo se pueden identificar dado un recorrido si es PreOrden, InOrden y PostOrden?
En PreOrden, la raíz es la primera, en Post-Orden es la última. En InOrden quedará ni el primero ni el último
En una pregunta de examen te pueden dar dos recorridos (uno será siempre el InOrden) y tener que sacar el tercero. Cómo es la lógica deductiva?
https://youtu.be/cGlNehp57Y0
- Identificar la raiz: En PreOrden, la raíz es la primera, en Post-Orden es la última. En InOrden quedará ni el primero ni el último.
- Identificar subárbol izquierdo y derecho de esa raíz: En InOrden, todo lo de la izquierda de la R es el subárbol izquierdo y todo lo de la derecha de R es el subárbol derecho
- Volver a identificar la raíz de cada subárbol: del subconjunto de nodos de cada subárbol, la raíz será la primera o la última en el PreOrden o PostOrden respectivamente.
- Volver a identificar los subárboles izquierdo y derecho de cada raíz
- … así recursivamente hasta terminar
En una pregunta de algortimos de pseudocódigo puede ser resolver qué parámetro hay que pasarle a una función recursiva para que salga un resultado determinado.
HACER EJECERCICIO ÚLTIMO EXAMEN PARA PRACTICAR
Para resolverla, hacer la siguiente estrategia:
- Seleccionar una de las posibles respuestas y usarla para probar con ella a ver si da el resultado
- Dibujar el árbol de llamadas, pero sólo una rama hasta el final
- Usar los resultados de las iteraciones de la primera rama cuando se repitan en otras ramas, para ahorrarnos dibujarlos otra vez ya que van a dar lo mismo y ya sabemos el resultado
Para resolverla, hacer la siguiente estrategia:
- Seleccionar una de las posibles respuestas y usarla para probar con ella a ver si da el resultado
- Dibujar el árbol de llamadas, pero sólo una rama hasta el final
- Usar los resultados de las iteraciones de la primera rama cuando se repitan en otras ramas, para ahorrarnos dibujarlos otra vez ya que van a dar lo mismo y ya sabemos el resultado
Cómo funciona el tipo de recorrido en profundidad de árboles Pre-Orden (RID)?
Completar———–
Se visita cada nodo al caer en él
1º Se empieza a navegar por la Raíz, y se
2º Subárbol izquierdo (siempre que se pueda ir a la izquierda, se va)
3º Subárbol derecho
Cómo funciona el tipo de recorrido en profundidad de árboles In-Orden (IRD)?
Se visita (imprime) cada nodo sólo cuando no se puede seguir navegando en esa dirección
1º Cuando no se pueda bajar más, se coge ese subárbol se visita primero I, luego la R de ese árbol, y luego D
2º Se sube un paso arriba, y se coge el siguiente subárbol por arriba. Ahora en este se visita R (porque I ya se ha visitado en el paso 1) y luego R
3º Así sucesivamente
Cómo funciona el tipo de recorrido en profundidad de árboles Post-Orden (IDR)?
Completar
Explicación de recorridos RID, IRD, IDR
https://en.wikipedia.org/wiki/Tree_traversal
https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/
https://en.wikipedia.org/wiki/Tree_traversal
https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/
Qué es un Árbol B?
Un árbol multicamino, en el que en cada nodo, en vez de un dato, hay más de uno.
Cada nodo puede tener n hijos
Qué tipos de un Árbol B hay y en qué consisten?
Árbol B → Árbol multimcamino. Cada nodo puede tener n hijos
Árbol B+ → Los nodos hoja están enlazados entre si y los datos solo están en los nodos hoja (en resto de nodos contiene claves)
Árbol B* → garantiza una ocupación de ⅔
Explica los siguientes concetos de los GRAFOS
Vértice
Arista
Arco
Dirigido / no dirigido
Grafo conexo
Multigrafo
Etiquetado o ponderado
Orden del grafo
Vértice → Nodo
Arista → Línea entre dos nodos
Arco → Relación entre dos nodos, se expresa (nodo a, nodo b)
No dirigido / Dirigido → Si se puede navegar entre dos nodos en los dos sentidos o solo en un sentido
Grafo conexo → Sin ciclos
Multigrafo → más de una arista entre dos vértices (más de un camino entre dos nodos)
Etiquetado o ponderado → Peso numérico en las aristas
Orden del grafo → Nº de vértices
Grado de un vértice → Nª de arcos incidentes
Con qué estructuras de datos se pueden representar los GRAFOS?
- Listas de adyacencia (array de vértices + listas enlazadas)
- Matrices de adyacencia (desperdicia memoria) → Se ponen todos los vértices en los dos ejes de una matriz y se marca en cada cruce con 1/0 si están enlazados o no en cada sentido
Qué 3 algoritmos de encontrar el camino mínimo en grafos se usan en protocolos TCP/IP de encaminamiento de routers?
Dijkstra (OSPF)
Bellman-Ford (RIP)
Floyd-Warshall (es como Dijkstra, pero en lugar de devolver el camino mínimo entre 2 nodos dados, devuelve todos los caminos mínimos del grafo)
A*
Qué significa un algoritmo de recubrimiento mínimo? Qué algoritmos hay? Utilizados por los algoritmos de Spanning Tree de switches
Recorrer todos los nodos de un grafo de la forma más rápida
Kruskal (en grafo conexo y ponderado)
PRIM
Para qué sirven los algoritmos de de grafos TARJAN y FORD-FULKERSON?
TARJAN → Grupos conexos (permite determinar los componentes fuertemente conectados de un grafo dirigido)
FORD-FULKERSON → Caminos para maximizar el flujo
Qué tres tipos de accesos a ficheros hay?
- Secuencial (las cintas por ejemplo)
- Acceso directo
- Por la clave del registro que sea la posición en el archivo
- Aplicando una función sobre la clave que te de la posición en el archivo
- Acceso indexado (hay un fichero con los datos + fichero de índice)
- Se busca la clave sobre el índice ordenado y esto te da la posición en el archivo
Qué dos tipos de ordenación externa sobre ficheros hay, cuando no se ordenaban en memoria?
- Mezcla directa
- Mezcla natural
Cómo se identificaría un fichero binario como JPG,GIF, …
Por el magic number o signature: n digitos por el que empieza el fichero binario que indica el formato del fichero
Cómo interpreta un navegador el tipo de información que le llega?
Con el mimetipe : tipo/subtipo
- image/gif
- text/xml
- text/html
- application/javascript
- video/mpeg
- application/pdf
- image/svg+xml
Indica características de los siguientes tipos de ficheros de imagen (compresión, colores, transparencia, animación)
JPG/JPEG
WebP
PNG
GIF
TIFF
BMP
SVG
JPG/JPEG (Joint Photographic Expert Group) → Compresión con pérdida → Existen variantes sin pérdida
WebP -> Compresión con pérdida y transparencia como GIF. Es de Google
PNG (Portable Network Graphics) → Compresión sin pérdida / Transparencias / True Color 24bits / No animación / Compresión deflación sin pérdida
GIF (Graphic Interchange Format) → 256 colores / animación y transparencia / compresión LZW sin pérdida)
TIFF (Tagged Image File Format) → Compresión sin pérdida multipágina
BMP (Windows Bitmap) → Compresión RLE (Run Lenght Encoding) sin pérdida
SVG (Scalable Vector Graphics) → en html5 se incrusta en html de forma nativa / mimetipe image/svg+xml
Falta las preguntas de la ficha de tipos de fichero de audio y vídeo, codecs, …. Dani lo va a ampliar y a hacer una ficha nueva
Cuál es la diferencia entre codec y contenedor? Algunos ejemplos de cada
El códec es el formato en el que está codificada la información de audio o vídeo (mp3, wma, wav …
El contenedor es el que contiene la pista de audio y/o video (.avi, .mov, mpg,.asf, .mkv …)
Qué es mp3, qué tipo de compresión tiene y para qué vale su etiqueta ID3?
mp3 = mpeg-(1/2) audio layer III
(mpeg = moving picture experts group)
Compresión con pérdida
ID3 → etiqueta con la información de autor, título, etc… que se usa para su catalogación
Lista los principales tipos de fichero de audio
mp3 (mpeg-1(o 2) layer III)
wav (sin compresión)
wma (windows media audio)
ac3 → dolby
FLAC (Free Lossless audio codec)
Lista los principales tipos de contenedor de fichero de video
- avi (audio video interface) → es de microsoft
- mov → es de apple, extensión QT (reproductor quicktime)
- .mpg → usa los codecs MPEG-1 (VHS-CD), MPEG2 (DVD), MPEG-4 (HD, deriva en xvid)
- asf
- mkv
Qué es formato docx, xlsx, pptx, etc .. y a partir de qué año lo adoptó Microsoft?
Es el formato OOXML (Office Open XML) recogido en el estandar ECMA 376 para esos tipos de ficheros.
Es un fichero zip que dentro tiene varios xml
Microsoft cambió a partir de 2007
Indica qué significa los siguientes formatos de archivos de Microsoft
doc
dot
docx
docm
dotx
dotm
rtf
xlsx
xlsm
xltx
xlsb
pptx
pptm
potx
potm
ppsx
ppsm
doc → word
dot → plantilla para word
docx → word formato ooxml
docm → macro word
dotx → plantilla para word formato ooxml
dotm → plantilla con macro para word
rtf → texto enriquecido
xlsx → excel formato ooxml
xlsm → macro para excel
xltx → excel con plantilla formato ooxml
xlsb → libro binario de excel
pptx → power point
pptm → power point con macros visual basic
potx → plantilla para power point formato ooxml
potm → plantilla para power point con macro
ppsx → power point solo diapositivas
ppsm → diapositivas con macro
Indica qué significa los siguientes formatos de archivos de Open Office
ODT
OTT
ODS
ODP
ODG
ODC
ODF
ODI
ODM
ODB
ODT → open document text → texto
OTT → plantilla de texto
ODS → spreadsheet → hoja de cálculo
ODP → presentation → presentación
ODG → gráphics → dibujo
ODC → charts → gráficas
ODF → formula
ODI → image
ODM → documento maestro
ODB → database
Qué iso es el estandar de PDF?
Qué es PDF/A?
ISO 32000-1:2008
Para guardado a largo plazo de documentos electrónicos. Elimina algunas características como audio, vídeo, cifrado, … para que siga siendo compatible y no se rompa)
Qué es el formato PS?
Un archivo PS es una imagen guardada en el lenguaje PostScript. Puede contener gráficos de vector, gráficos de trama, y el texto, e impreso por una impresora PostScript sin ser abierto en una aplicación.
Qué es el formato PCL?
PCL (Printing Control Language) es un lenguaje de descripción de páginas (Page Description Language – PDL) que fue desarrollado por Hewlett-Packard para impresoras láser. Fue creado en 1980 como alternativa más simple, rápida y económica para las impresoras láser basadas en el lenguaje PostScript.
Indica qué son los siguientes tipos de ficheros variados
exe
msi
dmg / pkg
deb
rpm
tar.gz
vcf
p12/ptx
cer
eml/msg
mbox
pst/ost
nsf
apk
csv
swf
epub
aab
exe → ejecutable de microsoft
msi (microsoft installer) → instalable de microsoft
dmg / pkg → instalable de mac
deb → instalable de linux debian y derivados como ubuntu
rpm → instalable de redhat y derivados como centos
tar.gz → comprimido básico de linux
vcf → vcard file
p12/ptx → certificado 509 con su clave privada
cer → certificado 509 sin su clave privada
eml/msg → formato de un correo, eml es la rfc2822
mbox → contenedor de mails, es la rfc 4155
pst/ost → buzones de outlook
nsf → buzones de lotus
apk → instalable android
csv → texto formateado con puntos y coma
swf → fichero con película flash
epub → libro electrónico
aab → publicación android que se abstrae de la plataforma
A qué corresponde esta definción?
Conjunto de reglas que, aplicada sistemáticamente a unos datos de entrada apropiados, resuelven un problema en un número finito de pasos elementales
Algoritmo
Qué tipo de algoritmo son las búsquedas binarias, ya sea sobre un array ordenado o un árbol binario de búsqueda, etc … es decir donde la búsqueda consiste en ir descartando mitades cada vez?
Algoritmo → logn
Qué tipo de algoritmo son las búsquedas en listas no ordenadas, es decir que se usan bucles para recorrerla?
Algoritmo → n
Qué tipo de algoritmo son las búsquedas en listas no ordenadas que tienen dos bucles anidados?
Algoritmo → n^2
Por ejemplo, el bubble sort, selection sort, insertio sort …
En el análisis de algoritmos se usa la notación “Big O notation” ¿en qué consiste?
Analiza la complejidad espacial y temporal, mediante un cota superior asintótica
Técnicas de diseño de algoritmos: en qué consisten?
- Divide y vencerás
- Voraces
- Probabilísticos
- Backtracking
- Ramificación y poda
- Programación dinámica
- Divide y vencerás → como las búsquedas binarias (T(n/2))
- Voraces → (opción óptima en cada paso. Dijkstra, Prim, Kruskal
- Probabilísticos → Las Vegas, Montecarlo
- Backtracking → Explora todo el árbol de soluciones
- Ramificación y poda → Optimiza las anteriores poniendo marcas para no pasar varias veces por el mismo sitio
- Programación dinámica → (bottom-up + memorización): Después de hacer un divide y vencerás, combina subproblemas óptimos. En lugar de ser top-down, es bottom-up. Se empieza con problemas pequeños y se van combinando. Además memoriza la resolución de problemas, por si vuelven a surgir no volver a resolverlos
Ordena de más eficientes a menos los siguientes algoritmos
O(n^c)
O(c^n)
O(n^2)
O(1)
O(nlogn)
O(logn)
O(n)
O(1)
O(logn)
O(n)
O(nlogn)
O(n^2)
O(n^c)
O(c^n)
Qué tres medios de expresión de logaritmos hay?
Diagramas de flujo (ISO)
Pseudocódigo
Sistemas formales (matemáticos)
En qué consistena alto nivel los siguientes tipos de algoritmos de ordenación?
Exchange sort
Selection sort
Insertion sort
Merge sort
Distribution sort
Exchange sorts → Intercambiar elementos. Burbuja, QuickSort, Cocktail o burbuja bidireccional
Selection sorts → Para cada posición, va a buscar qué elemento corresponde y lo selecciona. Heap Sort. Selection Sort
Insertion sorts → Para cada elemento, mira en qué posición tendría que ir y lo inserta. ShellSort (inserción con pasos más grandes para encontrar el sitio de Xi). Insertion Sort
Merge sorts → Merge sort
Distribution sort → distribuye entre distintas clasificaciones. Bucket sort o Bin sort, Radix sort
En qué consiste el algoritmo de ordenación de tipo Exchange, BURBUJA?
Qué complejidad Big O tiene?
O(n^2), salvo que ya esté ordenado o todos los elementos sean iguales, que sería (O(n))
Va desplazando el nº más grande que nos encontramos a base de comparaciones e intercambios hasta el final o su posición. Hará una pasada por cada elemento desordenado.
En qué consiste el algoritmo de ordenación de tipo Insertion, INSERCIÓN?
Qué complejidad Big O tiene?
O(n^2)
Por cada elemento (Xi) busca la posición que le corresponde, desplaza los elementos necesarios para hacerle el hueco y lo inserta
En qué consiste el algoritmo de ordenación de tipo Insertion, INSERCIÓN DIRECTA?
Qué complejidad Big O tiene?
O(n^2)
Por cada elemento (Xi) busca la posición que le corresponde, desplaza los elementos necesarios para hacerle el hueco y lo inserta
En qué consiste el algoritmo de ordenación de tipo Exchange, QUICK SORT?
Qué complejidad Big O tiene?
O(n log n), aunque en el caso peor, si el pivote se selecciona en un extremo, es peor, es O(n^2)
Fija un pivote y por cada elemento, compara con el pivote y lo inserta en uno de los lados.
Después repite la operación en cada uno de los dos segmentos, fijando nuevos pivotes, hasta que el array queda ordenado
En qué consiste el algoritmo de ordenación de tipo Merge, MERGE SORT?
Qué complejidad Big O tiene?
O(n log n)
- Se divide la lista en sublistas hasta llegar al caso trivial (recursividad)
- Mezcla (mergea) dos sublistas para obtener una lista ordenada
En qué consiste el algoritmo de ordenación de tipo Merge, HEAP SORT o MONTÍCULO?
Qué complejidad Big O tiene?
O(n log n)
Consiste en meter todos los elementos del array en un montículo MAX y luego realizar N veces llamada a eliminar_max(). Entre llamada y llamada hay que reconstruir el montículo
En qué consiste el algoritmo de ordenación de tipo Selection, SELECTION?
Qué complejidad Big O tiene?
O(n^2)
Se busca el minimo y se pone en la 1º posición
Luego se busca el mínimo a partir del 1er elemento para la 2º posición y así sucesivamente
En qué consiste el algoritmo de ordenación de tipo Distribution, RADIX SORT?
Qué complejidad Big O tiene?
O(n*k)
Hay dos versiones
LSD (usa el dígito menos significativo)
MSD (esa el dígito más significativo)
Hay unas colas o buckets del 0 al 9, y inserta los elementos en cada una analizando que el último dígito de cada uno sea igual al nº de cola
Después los saca y los vuelve a meter pero analizando el penúltimo dígito. Al meterlos de nuevo los mete ordenados.
Así sucesivamente
En qué consiste el algoritmo de ordenación de tipo Distribution, BUCKET SORT o BIN SORT?
Qué complejidad Big O tiene?
O(n)
Hay unos buckets con rangos de números, y inserta los elementos en cada uno según a qué rango corresponda.
Luego te dice que ordenes cada bucket con otro algoritmo que quieras
Qué es un algoritmo de ordenación natural?
Es aquel que cuando se le da una secuencia ya ordenada, tardará la menor cantidad de tiempo posible.
