B2-T3_EEDD Flashcards
¿Cuáles son las primitivas del tipo abstracto de datos Pila?
- PUSH: introducir dato (apilar)
- POP: desapilar
- TOP o PEEK: ojear el elmento de la cima.
- isEmpty: esta o no vacía.
- CONSTRUCTOR: crear la pila.
NOTA: en una pila se colocan y extraen datos por el mismo sitio, a diferencia de una cola (queue).
La pila puede implementarse mediante: Matriz o Lista Enlazada.
¿Qué diferencia existen entre una estructura de datos y un tipo abstracto de datos?
- El TAD es un modelo matemático: List (secencia), Set (MultiSet: con repetidos), Queue, Stack, Tree, Graph, Associative Array (Tabla Hash) y Priority Queue (Heap).
- Mientras que las estructuras de datos se encargan de implementar los TAD: array, listas enalzadas, árbol rojo-negro, monticulo, tabla hash…
¿Qué otros nombres recibe el tipo abstracto de datos “Array Asociativo”?
- Mapa o Correspondencia.
- Diccionario.
NOTA: Su índice es una cadena (array) en lugar de números.
Se implementa con una tabla hash (clave/valor).
Las búsquedas de hacen a través de la clave, pues están asociadas con el elemento en cuestión.
¿Qué problema 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 una función hash mal diseñada, que de la misma entrada para dos datos) estas se sitúen en la misma posición dentro de la tabla.
SOLUCIÓN: encadenar con una lista enlazada todos los objetos colisionados en esa entrada=>pero, ralentizaría sus busquedas.
NOTA: a menor sea la tabla se produciran mayor número de colisiones.
¿En qué consiste un montículo max-heap?
En una estructura de datos de tipo árbol en la cual el valor del nodo raiz es mayor o menor que todos los que tiene por debajo: MAX-HEAP o MIN-HEAP.
FUNCIONAMIENTO: se va extrayendo la raiz y reconstruyendo el monticulo para sustituir dicha raiz.
NOTA: el moticulo sirve para implementar una Cola con Prioridad.
El moticulo se puede estructurar tanto con una árbol como con un array.
¿Qué es el grado de un nodo dentro de un árbol?
El número de hijos REALES que tiene ese nodo. Esta limitado por el ORDEN del árbol.
(Ej: un árbol binario no puede haber + de 2 hijos por nodo=>el máximo grado es 2=que el orden)
¿Qué es la profundidad (depth) de un nodo?
Número de aristas o saltos desde la raíz hasta ese nodo.
(Ej: el depth de la raíz siempre será “0”, porque no tiene ninguna arista que le llegue desde arriba)
¿Qué es la altura (height) de un nodo?
Número de aristas o saltos desde el último nodo hasta el nodo en cuestión.
(Ej: el height del últino nodo hoja siempre será “0”, porque no tiene ninguna arista que le llegue desde abajo)
Cita los 3 tipos de recorridos de árboles:
- PREorden (RID)
- INorden (IRD)
- POSTorden (IDR)
Nombre dos tipos de árboles binarios:
- ABB (Arbol binario de busqueda): recurrido INorden (los valores menores que la raiz a la izquierda y los mayores a la derecha).
- Arbol de FIBONACCI (caso particular de AVL=tipo de árbol balanceado por rotaciones).
¿Qué es un árbol balanceado? ¿Y tipos?
Aquel cuyo factor de equilibrio (FE) está en el rango [-1,0,1]. Tipos:
- AVL (rotaciones)
- AA
- ROJO-NEGRO (algunos nodos rojos y otros negros)
- SPLAY (=achaflanar)
- Árbol B: árbol multicamino (en un mismo nodo hay varias claves o caminos).
En un árbol B+, ¿que contienen los nodos internos (NO hojas)?
Sólo las claves para poder navegar en las búsquedas.
NOTA: los nodos hoja son los que contienen los datos y estan enlazados entre sí (agilizando el recorrido).
¿Que se persigue en un árbol B*?
Que haya un buen porcentaje de ocupación en los nodos. Son árboles muy densos.
Ej: 2/3
Nombre las dos formas fundamentales de implementar un grafo:
- Matriz de adyacencia (nº de columnas/filas = nº de vertices=>representan el ORDEN del grafo: con un “1” o “0” se indica si los valores estan conectados o no).
- Lista de adyacencia (Array de vertices + Listas enlazadas en cada posicion del array=>es un array con tantas casillas como vértices indique el ORDEN del grafo y en cada casilla hay una Lista Enlazada para indicar a que nodo se conecta, es decir, es un ARRAY de LISTAS ENLAZADAS).
¿Cómo se llama a un grafo que tiene valores numéricos en las aristas?
Ponderado.
¿Qué 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.
¿Diferencia entre un grafo Dirigido (digrafo) o No Dirigido?
En el DIRIGIDO o DIGRAFO, vamos de un nodo a otro, pero NO al revés. En cambio, el NO DIRIGIDO iría en ambos sentidos.
¿Qué es el ORDEN del GRAFO?
Es el número de vertices que tiene.
¿Qué es el GRADO de un VERTICE?
Es el número de arcos (aristas) que inciden en dicho vertice (entrantes o salientes).
¿Qué es un grafo?
Es un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos.
NOTA: se pueden respresentar tanto en LISTAS DE ADYACENCIA (array+lista enlazada), como en MATRICES DE ADYACENCIA (nº de filas=nº de columnas).
¿Qué es un multigrafo?
Aquel que tiene más de una arista entre dos mismos vértices.
Nombre los algoritmos para calcular el camino minimo entre dos nodos en un GRAFO:
- DIJKSTRA (Estado-Enlace: ISIS y OSPF)
- BELLMAN-FORD (Vector distancia: RIP y IGRP->EIGRP)
- FLOYD (a diferencia de los demás, este te da TODOS los caminos minimos entre un punto y sus destinos=>todos con todos)
- A*
Nombre dos algoritmos para calcular un árbol de recubrimiento mínimo en un grafo:
- Prim
- Kruskal
*Recubrimiento mínimo: trazo que toca todos los puntos, pero la suma de pesos sea la mínima (parecido a STP).
¿Para qué sirve el algoritmo de Ford-Fulkerson?
Calcular camino en un grafo de tal forma que se maximiza el flujo entre dos nodos.
¿Para qué sirve el algoritmo de Tarjan en un grafo?
Para identificar grupos de vértices que están fuertemente conectados entre sí.
¿Qué tipo de fichero es ISAM?
Secuencial + Indexado, es decir, fijamos un índice, pero la zona de datos se trata secuancialmente.
Ej: MyISAM, que, junto a InnoDB, es uno de los motores de almacenamiento más populares de MySQL.
Nombre dos tipos de ordenación externa de ficheros (NO se almacenan en el disco duro):
- Mezcla directa: particiona->fusiona, particiona->fusiona, …
- Mezcla natural: (es el más avanzado) en lugar de particionar automaticamente, primero comprueba que ya hayan trozos ordenados y los mantiene. Resultando grupos ordenados de tamaños diferentes, no como en la directa.
Nombre cinco extensiones de archivo que se corresponden con contenedores multimedia (VIDEO):
- avi (Audio Video Interleave=intercalados)
- mkv (estandar abierto)
- asf
- mov (Apple)
- ogg
- 3gp: para móviles.
- WebM: basado em mkv.
¿Qué es FLAC?
Un formato/codec libre de audio sin perdidas (Free Lossless Audio Codec).
¿Qué es ID3 en el formato MP3?
Una etiqueta con metadatos que nos permite saber de ese audio el autor, album, etc (para catalogarlo).
¿Qué formato tienen los ficheros con extensión .docx?
Formato: OOXML (Office Open XML).
Estandar: ECMA 376.
(Es un zip con varios XMLs)
¿Quién se encarga del estándar del formato PDF?
ISO
Nombre dos lenguajes de descripción de página (orientados a imprimir):
- PostScript (PS)
- PCL (de HP)
¿Que representa un archivo con extensión .dmg?
Una aplicación instalable en MacOS
¿Que representa un archivo con extensión .p12?
Un certificado digital (x509) CON clave privada, al igual que .pfx.
* .p12: FIREFOX
* .pfx: Internet Explorer
