Tema3_Seccion1_EstructuraDatos Flashcards
(62 cards)
¿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
