BLOQUE 2 - TEMA 3 - Tipos abstractos y estructuras de datos. Organizaciones de ficheros.Algoritmos. Organización de ficheros Flashcards
Cual es la politica de acceso de una pila? (stack)
LIFO - Last in, first out
en las pilas, vamos ‘amontonando’ los datos, por tanto los ultimos que metemos, son los primeros que sacamos, ya que vamos ‘vaciando’ el montón
Como se almacenan los datos en una tabla hash?
Almacena pares de clave-valor
notas tabla hash: La tabla de Hash guarda la información en elementos que se le conocen como “slots” o “buckets” . Cada slot puede tener varias implementaciones, aunque la más común es una lista enlazada
Si tenemos un arbol con este aspecto… cual es el grado del nodo 50?
50 / \ 30 70 / \ / \ 20 40 60 80
2
el grado es el numero de hijos que tenemos
Nota: nivel 0 (soy la raíz) grado 2 (tengo dos hijos)
Si tenemos un arbol con este aspecto… cual es el grado del nodo 30?
50 / \ 30 70 / \ / \ 20 40 60 80
2
el grado es el numero de hijos que tenemos
Si tenemos un arbol con este aspecto… cual es el nivel de 50?
50 / \ 30 70 / \ / \ 20 40 60 80
0
El nivel de un nodo es la distancia desde la raíz al nodo (similar a la profundidad).
Si tenemos un arbol con este aspecto… cual es el nivel de 70?
50 / \ 30 70 / \ / \ 20 40 60 80
1
El nivel de un nodo es la distancia desde la raíz al nodo (similar a la profundidad).
Si tenemos un arbol con este aspecto… cual es el nivel de 60?
50 / \ 30 70 / \ / \ 20 40 60 80
2
El nivel de un nodo es la distancia desde la raíz al nodo (similar a la profundidad).
Si tenemos un arbol con este aspecto… cual es la profundidad de 40?
50 / \ 30 70 / \ / \
20 40 60 80
2
La profundidad de un nodo es la longitud del camino desde la raíz hasta ese nodo.
PROFUNDIDAD = NIVEL
Que es el orden de un nodo?
El orden de un árbol es el número máximo de hijos que puede tener un nodo.
Para un árbol binario, el orden es 2.
Dado el siguiente arbol… cual seria la ruta si hacemos un PREORDEN?
F
/ \
B G
/ \ \
A D i
/ \ \
C E H
F-B-A-D-C-E-G-I-H
(RID) > raiz, izquierda, derecha
nota: (raiz, izquierda, derecha) Vamos desplazando la R, fijarse, empezando por PREORDEN (Rid), luego INORDEN (iRd), luego POSTORDEN (idR)
Dado el siguiente arbol… cual seria la ruta si hacemos un INORDEN?
F
/ \
B G
/ \ \
A D i
/ \ \
C E H
A-B-C-D-E-F-G-I-H
(IRD) > izquierda, raiz, derecha
nota: (raiz, izquierda, derecha) Vamos desplazando la R, fijarse, empezando por PREORDEN (Rid), luego INORDEN (iRd), luego POSTORDEN (idR)
Dado el siguiente arbol… cual seria la ruta si hacemos un POSTORDEN?
F
/ \
B G
/ \ \
A D i
/ \ \
C E H
A-C-E-D-B-H-I-G-F
(IDR) > izquierda, derecha, raiz
nota: (raiz, izquierda, derecha) Vamos desplazando la R, fijarse, empezando por PREORDEN (Rid), luego INORDEN (iRd), luego POSTORDEN (idR)
Que es un arbol binario?
Es un arbol en que cada nodo tiene como máximo dos hijos
Que es un arbol Equilibrado ? (auto-balanceable)
Aquel en que la diferencia de alturas de los subárboles izquierdo y derecho correspondiente a cualquier nodo del árbol no es superior a 1 (FE es -1, 0, 1)
Que es un arbol B?
A diferencia de los árboles binarios, los nodos en un árbol B pueden tener más de dos hijo, PERO todos los nodos hoja están al mismo nivel, lo que mantiene el árbol equilibrado
de qué orden es este grafo?
A —- B
| |
C —- D
Es de orden 4
nota: El orden de un grafo es el número o cantidad de vértices que tenga
Si hablamos de algoritmos de ordenación, en que consiste el QuickSort?
Algoritmo de ordenación eficiente que utiliza la técnica de divide y vencerás para particionar la lista en sublistas menores y mayores alrededor de un pivote, ordenando recursivamente cada sublista. NO es un algoritmo estable
Pasos:
- selecciona un pivote
- Reordena la lista, de modo que a la izquierda quedan los
menores del pivote y a la derecha los mayores
- Aplica nuevamente Quicksort (pivote + particion) de manera recursiva
- Combinar los resultados
Hablando de tecnicas de organizacion de ficheros por parte de los sistemas operativos, nombra algunos algoritmos de planificacion para acceder a los ficheros
- FCFS: first come first serve
- SSTF: shortest seek time first (selecciona el que la cabeza del disco está mas cerca, osea el que va a tardar menos en encontrar)
- SCAN: la cabeza del disco va a un lado y cuando llega al final vuelve. va haciendo barridos
- C-SCAN: igual que scan pero la aguja no vuelve sino que va dando vueltas
(tambien está el look y el c-look)
Recorrido IN ORDEN de este arbol
M
/ \
L Q
/ \ \
K N R
/ \ \
O P S
K, L, O, N, P, M, Q, R, S
Que es un monticulo (heap) ?
Un montículo (heap) es una estructura de datos especializada que se utiliza para gestionar un conjunto de elementos de manera que el más grande (o más pequeño, dependiendo del tipo de montículo) siempre esté accesible rápidamente.
Que diferencia hay entre los recorridos preorden, inorden, y postorden ?
1) Preorder:
Visita el nodo raíz primero
Luego recorre el subárbol izquierdo
Finalmente, recorre el subárbol derecho
Orden: Raíz, Izquierda, Derecha
Ejemplo: Dado el árbol [A, B, D, E, C, F], el recorrido preorden sería A, B, D, E, C, F
2) Inorder
Recorre el subárbol izquierdo primero
Luego visita el nodo raíz
Finalmente, recorre el subárbol derecho
Orden: Izquierda, Raíz, Derecha
Ejemplo: Dado el árbol [D, B, E, A, F, C], el recorrido inorden sería D, B, E, A, F, C
3) Postorden (Postorder):
Recorre el subárbol izquierdo primero
Luego recorre el subárbol derecho
Finalmente, visita el nodo raíz
Orden: Izquierda, Derecha, Raíz
Ejemplo: Dado el árbol [D, E, B, F, C, A], el recorrido postorden sería D, E, B, F, C, A
En relación con los algoritmos de búsqueda. ¿Qué es un árbol recubridor mínimo?
Es un subconjunto de las aristas que conecta todos los vértices sin ciclos y con el costo total más bajo posible
En relación con los algoritmos de búsqueda. ¿Qué es un camino mínimo entre dos vértices en un árbol ponderado?
La ruta de menor coste entre dos vértices específicos
En relación con los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo de PRIM? (T)
Para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas
¿Cómo se llama el algoritmo de búsqueda de la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas? (T)
Algoritmo de PRIM
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo de búsqueda de KRUSKAL?
Para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo
¿Cómo se llama el algoritmo de búsqueda de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado?
Algoritmo de KRUSKAL
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo DIJKSTRA?
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista. No admite pesos negativos.
¿Cómo se llama el algoritmo de la teoría de grafos que determina el camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista?
Algoritmo de Dijkstra
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo de BELLMAN-FORD? (T)
Determina el camino más corto desde un único origen en un grafo dirigido o no dirigido. Admite que alguna de las aristas sea negativa
¿Cómo se llama el algoritmo de búsqueda de la teoría de grafos que determina el camino más corto desde un único origen en un grafo dirigido o no dirigido. Admite que alguna de las aristas sea negativa?
Algoritmo de BELLMAN-FORD
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo FLOYD-WARSHALL? (T)
Determina el camino mínimo en grafos dirigidos ponderados. Encuentra el camino entre todos los pares de vértices en una única ejecución
¿Cómo se llama el algoritmo de búsqueda de la teoría de grafos que determina el camino mínimo en grafos dirigidos ponderados en una única ejecución?
Algoritmo de FLOYD-WARSHALL
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el Algoritmo A*?
Encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo
¿Cómo se llama el algoritmo de búsqueda de la teoría de grafos que encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo?
Algoritmo A*
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo JOHNSON?
Encuentra el camino más corto entre todos los pares de vértices de un grafo dirigido disperso
¿Cómo se llama el algoritmo de búsqueda, según la teoría de grafos, que encuentra el camino más corto entre todos los pares de vértices de un grafo dirigido disperso?
Algoritmo de JOHNSON
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo FORD-FULKERSON?
Para encontrar el flujo máximo en una red de flujo
¿Cómo se llama el algoritmo de búsqueda de la teoría de grafos que sirve para encontrar el flujo máximo en una red de flujo? (T)
Algoritmo de FORD-FULKERSON
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo TARJAN?
Para encontrar componentes fuertemente conexos en un grafo dirigido
¿Cómo se llama el algoritmo de búsqueda de la teoría de grafos que sirve para encontrar componentes fuertemente conexos en un grafo dirigido?
Algoritmo de TARJAN
Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo VITERBI? (T)
Permite hallar la secuencia más probable de estados ocultos
¿Cómo se llama el algoritmo de búsqueda de la teoría de grafos que permite hallar la secuencia más probable de estados ocultos?
Algoritmo de VITERBI
Nombra algoritmos de búsqueda de la teoría de grafos
PRIM
KRUSKAL
DIJKSTRA
BELLMAN-FORD
FLOYD-WARSHALL
Algoritmo A*
JOHNSON
FORD-FULKERSON
TARJAN
VITERBI
