BLOQUE 2 - TEMA 3 - Tipos abstractos y estructuras de datos. Organizaciones de ficheros.Algoritmos. Organización de ficheros Flashcards

1
Q

Cual es la politica de acceso de una pila? (stack)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Como se almacenan los datos en una tabla hash?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Si tenemos un arbol con este aspecto… cual es el grado del nodo 50?

     50
/              \ 30              70 / \               / \ 20 40     60  80
A

2

el grado es el numero de hijos que tenemos

Nota: nivel 0 (soy la raíz) grado 2 (tengo dos hijos)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Si tenemos un arbol con este aspecto… cual es el grado del nodo 30?

     50
/              \ 30              70 / \               / \ 20 40     60  80
A

2
el grado es el numero de hijos que tenemos

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Si tenemos un arbol con este aspecto… cual es el nivel de 50?

     50
/              \ 30              70 / \               / \ 20 40     60  80
A

0

El nivel de un nodo es la distancia desde la raíz al nodo (similar a la profundidad).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Si tenemos un arbol con este aspecto… cual es el nivel de 70?

     50
/              \ 30              70 / \               / \ 20 40     60  80
A

1

El nivel de un nodo es la distancia desde la raíz al nodo (similar a la profundidad).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Si tenemos un arbol con este aspecto… cual es el nivel de 60?

     50
/              \ 30              70 / \               / \ 20 40     60  80
A

2

El nivel de un nodo es la distancia desde la raíz al nodo (similar a la profundidad).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Si tenemos un arbol con este aspecto… cual es la profundidad de 40?

     50
   /     \
30      70

/ \       / \

20 40 60 80

A

2

La profundidad de un nodo es la longitud del camino desde la raíz hasta ese nodo.

PROFUNDIDAD = NIVEL

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Que es el orden de un nodo?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Dado el siguiente arbol… cual seria la ruta si hacemos un PREORDEN?

                      F
              /              \
             B              G
          /      \               \
       A        D               i 
              /      \             \
             C       E            H
A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Dado el siguiente arbol… cual seria la ruta si hacemos un INORDEN?

                      F
              /              \
             B              G
          /      \               \
       A        D               i 
              /      \             \
             C       E            H
A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Dado el siguiente arbol… cual seria la ruta si hacemos un POSTORDEN?

                      F
              /              \
             B              G
          /      \               \
       A        D               i 
              /      \             \
             C       E            H
A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Que es un arbol binario?

A

Es un arbol en que cada nodo tiene como máximo dos hijos

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Que es un arbol Equilibrado ? (auto-balanceable)

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Que es un arbol B?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

de qué orden es este grafo?

A —- B
| |
C —- D

A

Es de orden 4

nota: El orden de un grafo es el número o cantidad de vértices que tenga

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Si hablamos de algoritmos de ordenación, en que consiste el QuickSort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Hablando de tecnicas de organizacion de ficheros por parte de los sistemas operativos, nombra algunos algoritmos de planificacion para acceder a los ficheros

A
  • 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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Recorrido IN ORDEN de este arbol

                     M
              /              \
             L              Q
          /      \               \
       K        N               R 
              /      \             \
             O       P            S
A

K, L, O, N, P, M, Q, R, S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Que es un monticulo (heap) ?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Que diferencia hay entre los recorridos preorden, inorden, y postorden ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

En relación con los algoritmos de búsqueda. ¿Qué es un árbol recubridor mínimo?

A

Es un subconjunto de las aristas que conecta todos los vértices sin ciclos y con el costo total más bajo posible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

En relación con los algoritmos de búsqueda. ¿Qué es un camino mínimo entre dos vértices en un árbol ponderado?

A

La ruta de menor coste entre dos vértices específicos

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

En relación con los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo de PRIM?

A

Para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

¿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?

A

Algoritmo de PRIM

26
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo de búsqueda de KRUSKAL?

A

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

27
Q

¿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?

A

Algoritmo de KRUSKAL

28
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo DIJKSTRA?

A

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.

29
Q

¿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?

A

Algoritmo de Dijkstra

30
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo de BELLMAN-FORD?

A

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

31
Q

¿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?

A

Algoritmo de BELLMAN-FORD

32
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo FLOYD-WARSHALL?

A

Determina el camino mínimo en grafos dirigidos ponderados. Encuentra el camino entre todos los pares de vértices en una única ejecución

33
Q

¿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?

A

Algoritmo de FLOYD-WARSHALL

34
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el Algoritmo A*?

A

Encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo

35
Q

¿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?

A

Algoritmo A*

36
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo JOHNSON?

A

Encuentra el camino más corto entre todos los pares de vértices de un grafo dirigido disperso

37
Q

¿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?

A

Algoritmo de JOHNSON

38
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo FORD-FULKERSON?

A

Para encontrar el flujo máximo en una red de flujo

39
Q

¿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?

A

Algoritmo de FORD-FULKERSON

40
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo TARJAN?

A

Para encontrar componentes fuertemente conexos en un grafo dirigido

41
Q

¿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?

A

Algoritmo de TARJAN

42
Q

Según los algoritmos de búsqueda de la teoría de grafos, ¿en qué consiste el algoritmo VITERBI?

A

Permite hallar la secuencia más probable de estados ocultos

43
Q

¿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?

A

Algoritmo de VITERBI

44
Q

Nombra algoritmos de búsqueda de la teoría de grafos

A

PRIM

KRUSKAL

DIJKSTRA

BELLMAN-FORD

FLOYD-WARSHALL

Algoritmo A*

JOHNSON

FORD-FULKERSON

TARJAN

VITERBI

45
Q

Algoritmos de ordenación, nombra alguno

A

Burbuja
Quick Sort
Selection
HeapSort
Inserción
ShellSort
Merge sorts
Bucket sort o Bin Sort
Radix Sort

46
Q

¿Cómo funciona el algoritmo de ordenación Burbuja o Bubble Sort?

A

Algoritmo natural que recorre repetidamente la lista, comparando pares de elementos adyacentes y los intercambia si están en el orden incorrecto

47
Q

¿En qué consiste el algoritmo de ordenación de Inserción?

A

Comienza con una lista vacía y toma elementos de la lista original uno por uno.
Para cada nuevo elemento, encuentra su posición correcta en la lista ordenada y lo inserta allí, desplazando los elementos más grandes si es necesario

48
Q

¿En qué consiste el algoritmo de ordenación Shell o ShellSort?

A

Permite intercambiar elementos que están lejos unos de otros para reducir la cantidad de desplazamientos necesarios para ordenar la lista. Algoritmo estable

49
Q

¿En qué consiste el algoritmo de ordenación MergeSort?

A

Algoritmo de ordenación eficiente que también utiliza la técnica de divide y vencerás.
Divide la lista en mitades, ordena cada mitad y luego las combina para formar una lista ordenada.

Funcionamiento:
1. División
2. Recursión
3. Combinación (Merge)

50
Q

¿En qué consiste el algoritmo de ordenación HeapSort o Montículos?

A

Funcionamiento:
1. Construcción de Montículos: Se reorganiza el array para que cumpla con las propiedades del montículo (máximo o mínimo)
2. Se aplica el proceso de heapify para restaurar las propiedades del montículo en la raíz. Este proceso se repite hasta que todos los elementos estén ordenados

51
Q

¿En qué consiste el algoritmo de ordenación de Selección?

A

Funcionamiento:
1. Buscar el mínimo: Encuentra el elemento más pequeño en la parte desordenada del array.
2. Intercambiar: Intercambia este elemento con el primer elemento de la parte desordenada.
3. Repetir el algoritmo

52
Q

¿En qué consiste el algoritmo de ordenación RadixSort?

A

Funcionamiento:
1. Los elementos se agrupan en “bandejas” (buckets), seleccionando con qué dígito empezar a ordenar
2. Se selecciona el elemento menos significativo y se le añade a su bucket correspondiente
3. Sacar elementos de las cubetas en orden
4. Se selecciona el segundo elemento menos significativo y se le añade a su bucket correspondiente
5. Sacar elementos de las cubetas en orden y ya queda ordenado

53
Q

¿En qué consiste el algoritmo de ordenación BucketSort?

A

Funcionamiento:
1. Metemos los números en cubetas o buckets con el reparto que consideremos, por ejemplo en bloques de 10 números.
2. Ordenamos cada cubeta o bucket con el algoritmo que consideremos
3. Extraemos los números en orden

54
Q

Tipos de grafos

A

Dirigidos ó digrafo: aquel en el que todas sus aristas tienen sentido o dirección

No dirigidos: las aristas representan relaciones simétricas y no tienen un sentido definido. Todas sus aristas son bidireccionales.

Conexo: es posible llegar desde cualquier nodo del grafo a cualquier otro nodo a través de una secuencia de aristas (conexiones) sin importar cuán larga sea esa secuencia.

Multigrafo: más de una arista entre vértices

Etiquetado/ponderado: las aristas tienen un valor o peso asociado

Completo: cada par de vértices está conectado por una arista.

54
Q

¿Cuál de las siguientes opciones NO es una característica de la asignación de espacio de almacenamiento enlazada?

a) Los bloques de un fichero son nodos de una lista enlazada.

b) Genera fragmentación externa.

c) Ineficiencia con el acceso directo.

d) Cada bloque contiene un indicador del siguiente bloque con datos del fichero.

A

B

Genera fragmentación externa.

La asignación enlazada genera fragmentación interna, no externa

55
Q

¿Qué formato de archivo de imagen soporta animaciones y tiene una paleta de colores limitada a 256?

a) .jpg
b) .png
c) .gif
d) .bmp

A

C

gif

56
Q

¿Cuál de las siguientes afirmaciones sobre los árboles B es FALSA?

a) Son árboles autoequilibrados.

b) Los nodos pueden tener más de dos hijos.

c) Se utilizan comúnmente en sistemas de bases de datos y sistemas de archivos.

d) La búsqueda de elementos en un árbol B tiene una complejidad temporal de O(n) en el peor de los casos.

A

D

La búsqueda de elementos en un árbol B tiene una complejidad temporal de O(n) en el peor de los casos.

nota: La búsqueda, inserción y borrado en un árbol B tienen una complejidad temporal de O(log(n))

57
Q

En un arbol, que es ….

  • nodo hoja
  • grado
  • orden
  • nivel
  • profundidad
  • altura de un nodo
  • anchura
A
  • nodo hoja: nodo que no tiene descendientes
  • grado: numero de hijos
  • orden. numero maximo teorico de hijos posibles
  • nivel: num de ramas que hay que recorrer hasta raiz
  • profundidad: igual que nivel
  • altura de un nodo: numero total de nodos hijos
  • anchura: el ancho del arbol

nota: remember que el nivel empieza por 0

58
Q

Dado este arbol… dime del nodo 4 su nivel, profundidad, altura y anchura

1
/ \
2 3
/
4

A
  • Nivel y profundidad es 2 (0,1, 2)
  • Altura es 0 (es el ultimo)
  • Anchura es 2, OJO que la anchura se mide a nivel de arbol, no de nodo. Se diria la anchura es 2 a nivel 1
59
Q

Dado este arbol… dime del nodo 1 su nivel, profundidad , altura y anchura

1
/ \
2 3
/
4

A
  • Nivel y profundidad es 0
  • Altura es 2
  • Anchura es 2, OJO que la anchura se mide a nivel de arbol, no de nodo. Se diria la anchura es 2 a nivel 1