B2-T3 Tipos abstractos y Estructuras de datos.TAD y Algoritmos Flashcards

1
Q

¿Qué es una Estructura de datos ?

A

Una forma de organizar los datos para que puedan usarse de manera eficiente.

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

Estructuras de datos primitivos

A

son estructuras de datos básicas proporcionadas por los lenguajes de programación para representar valores únicos: números enteros, números de punto flotante, caracteres y valores booleanos.

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

Estructuras de datos abstractas

A

son estructuras de datos de nivel superior que se construyen utilizando tipos de datos primitivos y proporcionan operaciones más complejas y especializadas.

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

Algoritmo

A

Un conjunto de instrucciones paso a paso para resolver un problema específico.

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

Complejidad temporal

A

Una medida de la cantidad de tiempo que tarda un algoritmo en ejecutarse, dependiendo de la cantidad de datos en los que está trabajando el algoritmo.

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

Complejidad espacial

A

Una medida de la cantidad de memoria que utiliza un algoritmo, dependiendo de la cantidad de datos en los que está trabajando el algoritmo.

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

Big O Notation

A

Notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor particular o infinito. Se utiliza para describir la complejidad temporal de un algoritmo.

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

Recursión

A

Una técnica de programación donde una función se llama a sí misma.

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

Divide y Vencerás

A

Un método para resolver problemas complejos dividiéndolos en subproblemas más pequeños y manejables, resolviendo los subproblemas y combinando las soluciones. A menudo utiliza las recursividad.

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

Fuerza Bruta

A

De manera sencilla y directa, el algoritmo consiste en probar todas las soluciones posibles y luego elegir la mejor.

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

BubbleSort( Ordenamiento de la burbuja)

A

Algoritmo estable. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Revisar varias veces toda la lista hasta que no se necesiten más intercambios.

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

Complejidad temporal del BubbleSort

A

O(n²)

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

CocktailSort (Ordenamiento de la Burbuja bidireccional)

A

Algoritmo estable. Mejora del BubbleSort. Ordena al mismo tiempo por los dos extremos del vector de manera que tras la primera iteración, tanto el menor como el mayor elemento estarán en sus posiciones finales, reduciendo el número de comparaciones finales.

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

Complejidad temporal del CocktailSort

A

O(n²)

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

Selection Sort (Ordenamiento por selección)

A

Algoritmo inestable. Revisa cada elemento de la lista hasta encontrar el valor más bajo, lo SELECCIONA y lo mueve el valor más bajo al frente de la parte no ordenada de la lista. Repasa la matriz nuevamente tantas veces como valores haya en la lista.

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

Complejidad temporal de Selection Sort

A

O(n²)

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

Insertion Sort (Ordenamiento por Insercion)

A

Algoritmo estable. Utiliza una parte de la matriz para contener los valores ordenados y la otra parte de la matriz para contener los valores que aún no están ordenados.
El algoritmo toma un valor a la vez de la parte no ordenada de la matriz y lo coloca en el lugar correcto en la parte ordenada de la matriz, hasta que la matriz esté ordenada.

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

Complejidad temporal de Insertion Sort

A

O(n²)

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

Binary Insertion Sort (Ordenación por inserción binaria)

A

Mejora del algoritmo de ordenamiento por inserción. Partiendo de una lista ya ordenada( la primera sería el primer elemento de la lista), se van introduciendo por búsquedas binarias elementos a la misma.

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

Quicksort

A

Algoritmo inestable. Toma una matriz de valores, elige uno de los valores como elemento ‘pivote’ y mueve los otros valores para que los valores más bajos estén a la izquierda del elemento pivote y los valores más altos a la derecha de él.

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

Complejidad temporal Quicksort

A

Promedio: O(n log n),
peor caso: O(n²)

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

Counting sort (Ordenamiento por cuentas)

A

Algoritmo estable. No comparativo. Ordena una matriz contando el número de veces que ocurre cada valor. Solo funciona con números enteros no negativos. Counting Sort es rápido cuando el rango de valores posibles k es menor que el número de valores n.

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

Complejidad temporal Counting sort

A

O(n+k)

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

Bucket sort o Bin Sort (Ordenamiento por casilleros)

A

Algoritmo estable. No comparativo. Distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero solo puede contener los elementos que cumplan unas determinadas condiciones, las cuales deben ser excluyentes entre sí. Luego cada casillero se ordena utilizando otro algoritmo o se llama recursivamente al método, para finalmente devolver los casilleros concatenados por orden.

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

Complejidad temporal Bucket sort

A

O(n)

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

Postman’s sort (algoritmo del cartero)

A

Variante del Bucket sort utilizada cuando los elementos a ordenar disponen de varias claves y/o subclaves, las cuales se utilizan para hacer varios ordenamientos sucesivos.

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

Complejidad temporal Postman’s sort

A

O(cn) siendo c el número de claves que se utilizan para clasificar.

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

Radix Sort (Ordenamiento Radix)

A

Algoritmo estable. El algoritmo ordena una matriz por dígitos individuales, comenzando con el dígito menos significativo (el que está más a la derecha).
Utiliza la base creando 10 depósitos (o contenedores) diferentes correspondientes al dígito que está enfocado, luego se vuelven a colocar en la matriz antes de pasar al siguiente dígito.
Es un algoritmo no comparativo que solo funciona con números enteros no negativos.

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

Complejidad temporal Radix Sort

A

O(n⋅k)

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

Cuando un algoritmo es estable?

A

Es un algoritmo que:
- mantiene el orden de los elementos con el mismo valor antes y después de la clasificación.
- mantiene el orden relativo que tenían originalmente los elementos con claves iguales.

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

Merge Sort (Ordenamiento por mezcla)

A

Algoritmo estable. Utiliza la técnica de divide y vencerás. Ordenamiento por mezcla. Ordena una matriz dividiéndola primero en matrices más pequeñas y luego reconstruyendo la matriz de la manera correcta para que esté ordenada.

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

Complejidad temporal de Merge Sort

A

O(n log n)

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

Binary tree sort (Ordenamiento con ábol binario)

A

El ordenamiento con árbol binario ordena sus elementos haciendo uso de un árbol binario de búsqueda. Se basa en ir construyendo poco a poco el árbol binario introduciendo cada uno de los elementos, los cuales quedarán ya ordenados. Después, se obtiene la lista de los elementos ordenados recorriendo el árbol en inorden.

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

Complejidad temporal Binary tree sort

A

O(n log n)

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

Algoritmo de búsqueda lineal

A

El algoritmo de búsqueda lineal busca en una matriz y devuelve el índice del valor que busca. Si llega al final de la matriz y no encuentra el valor, devuelve -1 para indicar que no se encontró el valor.

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

Complejidad temporal de algoritmo de búsqueda lineal

A

O(n)

37
Q

Algoritmo de búsqueda binaria

A

También conocida, como búsqueda de intervalo medio​ o búsqueda logarítmica, es un algoritmo de búsqueda que encuentra la posición de un valor en un lista ordenada.
Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.

38
Q

Complejidad temporal del algoritmo búsqueda binaria

A

O(log2n)
en el peor de los casos es O(log n)

39
Q

HeapSort (Ordenamiento por montículos)

A

Algoritmo no estable, no recursivo. Consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado.

40
Q

Complejidad temporal de HeapSort

A

O(nlogn)

41
Q

Listas enlazadas

A

Lista donde los nodos están enlazados entre sí. Cada nodo contiene datos y un puntero. La forma en que están vinculados es que cada nodo apunta al lugar de la memoria en el que se ubica el siguiente nodo.

42
Q

Singly linked lists( Listas enlazadas individualmente)

A

Tipo más simple de lista enlazada. Ocupa menos espacio en la memoria porque cada nodo tiene solo una dirección para el siguiente nodo.

43
Q

Doubly linked lists( Listas doblemente enlazadas)

A

Tiene nodos con direcciones tanto al nodo anterior como al siguiente y por lo tanto ocupa más memoria. Se usan si desea poder moverse hacia arriba y hacia abajo en la lista.

44
Q

Circular linked lists( Listas circulares enlazadas)

A

Lista simple o doblemente enlazada con el primer nodo, la “cabeza”, y el último nodo, la “cola”, conectados.

45
Q

Búsqueda lineal de listas enlazadas

A

Funciona igual que para matrices. Se recorre una lista de valores sin ordenar desde el nodo principal hasta que se encuentra el nodo con el valor específico. La complejidad del tiempo es O (n)

46
Q

Algoritmos Listas

A

Algoritmos que funcionan con un índice determinado (Countig Sort, Radix Sort, Quicksor, o algoritmo de Búsqueda Binaria) no se pueden utilizar en las listas enlazadas.

47
Q

Stack (pila)

A

Es una estructura de datos que puede almacenar gran cantidad de elementos. Organiza los elementos de manera que el último en entrar es el primero en salir (LIFO: Last In First Out.)

48
Q

Operaciones Básicas Stack

A

Push: Agrega un nuevo elemento a la pila.
Pop: Elimina y devuelve el elemento superior de la pila.
Peek: Devuelve el elemento superior de la pila.
isEmpty: comprueba si la pila está vacía.
Size: encuentra la cantidad de elementos en la pila.
Las pilas se pueden implementar mediante el uso de matrices o listas vinculadas.

49
Q

Queue (cola)

A

Es una estructura de datos que puede almacenar gran cantidad de elementos. Organiza los elementos de manera que el primero en llegar es el primero en salir ( FIFO: First In First Out.)

50
Q

Operaciones Básicas Queue

A

Enqueue: Adiciona un elemento en la cola
Dequeue: Elimina y retorna el primer elemento (front).
Peek: Retorna el primer elemento.
isEmpty: Chequea si la cola está vacía
Size: Encuentra el número de elementos en la cola.

51
Q

DEQUE (Double Ended QUEue) Bicolas doblemente terminadas

A

Son colas en donde los nodos se pueden añadir y quitar por ambos extremos
Bicolas de entrada restringida: Son aquellas donde la inserción solo se hace por el final, aunque podemos eliminar al inicio o al final.
Bicolas de salida restringida: Son aquellas donde solo se elimina por el final, aunque se puede insertar al inicio y al final.

52
Q

Colas de prioridad

A

Los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.
El método peek (find-max o find-min), devuelve el elemento de mayor prioridad pero no modifica la cola, se implementa con mucha frecuencia y casi siempre se ejecuta en tiempo O(1).

53
Q

Tabla hash

A

Estructura de datos diseñada para que sea rápido trabajar con ella (buscar, agregar y eliminar datos). Sus elementos se almacenan en contenedores de almacenamiento llamados depósitos.
Cuando dos elementos de la tabla tienen el mismo código hash, significa que pertenecen al mismo depósito y ocurre una colisón.

54
Q

Solución de colisiones en la tabla Hash.

A

Encadenamiento Separado o hashing abierto ( separate chaining or open hashing)

Open Addressing or closed hashing( direccionamiento abierto o hash cerrado)

55
Q

Encadenamiento Separado o hashing abierto

A

Permite “encadenar” más de un registro a las celdas de una tabla hash. Si dos registros se dirigen a la misma celda, ambos irán a esa celda como una lista vinculada.

56
Q

Direccionamiento abierto o hash cerrado

A

A las celdas de la tabla hash se les asigna uno de tres estados: ocupada, vacía o eliminada. Si se produce una colisión de hash, se sondeará la tabla para mover el registro a una celda alternativa que se indique como vacía.
Existen diferentes tipos de sondeo cuando se implementa este método: sondeo lineal, el doble hash y el sondeo cuadrático.

57
Q

Hash Map

A

Forma de estructura de datos de Hash Table que generalmente contiene una gran cantidad de entradas. Se utilizan para encontrar información detallada sobre algo.

58
Q

Árbol

A

Estructura de datos no lineal, se asemeja a las listas vinculadas en que cada nodo contiene datos y puede vincularse a otros nodos.
Un solo elemento puede tener múltiples elementos “siguientes” (ramificación en varias direcciones.

Se llama “árbol” porque parece un árbol, sólo que al revés.

59
Q

Binary Trees

A

Cada nodo tiene hasta dos hijos, el nodo hijo izquierdo y el nodo hijo derecho. Esta estructura es la base para tipos de árboles más complejos como Binary Search Trees y AVL Trees.

60
Q

Binary Search Trees

A

tipo de árbol binario donde, para cada nodo, el nodo secundario izquierdo tiene un valor más bajo y el nodo secundario derecho tiene un valor más alto.
su recorrido en inorden devuelve la lista de valores ordenados.
búsqueda eficiente O(h) donde h es a altura del árbol

61
Q

AVL Trees

A

se autoequilibra de modo que para cada nodo, la diferencia de altura entre los subárboles izquierdo y derecho sea como máximo uno. Este equilibrio se mantiene mediante rotaciones cuando se insertan o eliminan nodos.
la altura se mantiene al mínimo
busqueda, insercion y eliminación O(logn)

62
Q

Árboles B

A

Son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de BD y sistemas de archivos. Al igual que los árboles binarios de búsqueda, son árboles balanceados de búsqueda, pero cada nodo puede poseer más de dos hijos

63
Q

Árbol-B+

A

Toda la información se guarda en las hojas. Los nodos internos solo contienen claves y punteros.
Límite máximo y mínimo en el número de claves por nodo
Los nodos hoja del árbol están conectados entre sí a través de una lista enlazada (ordenada), aumentando el coste de inserción para mejorar la eficiencia en la búsqueda.

64
Q

Árbol-B*

A

Es una estructura de datos de árbol utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2.

65
Q

Tipos de árboles binarios:

A

Balanceado
Completo
Full
Perfecto

66
Q

Árbol Binario Balanceado

A

Tiene como máximo 1 de diferencia entre las alturas de sus subárboles izquierdo y derecho, para cada nodo del árbol.

67
Q

Árbol Binario Completo

A

Tiene todos los niveles llenos de nodos, excepto el último nivel, que también puede estar lleno, o llenarse de izquierda a derecha.

68
Q

Árbol Binario Full

A

Cada nodo tiene cero o dos hijos.

69
Q

Árbol Binario Perfecto

A

Tiene todos los nodos hoja en el mismo nivel, lo que significa que todos los niveles están llenos de nodos y todos los nodos internos tienen dos nodos secundarios.

70
Q

Nivel de un nodo

A

Se define por 1 + (el número de brazos entre el nodo y la raíz).

71
Q

Altura de un nodo

A

Es el número de brazos en el camino más largo entre ese nodo y una hoja.

72
Q

Profundidad

A

Es el número de brazos desde la raíz del árbol hasta un nodo.

73
Q

Grafos

A

Estructura de datos no lineal que consta de vértices (nodos) y aristas.

74
Q

Grafo ponderado

A

Un grafo ponderado es un grafo donde las aristas tienen valores. El valor de peso de una arista puede representar cosas como distancia, capacidad, tiempo o probabilidad.

75
Q

Grafo conexo

A

Es cuando todos los vértices están conectados a través de aristas de alguna manera. Un grafo que no está conectado es un grafo con subgrafos aislados (disjuntos) o vértices únicos aislados.

76
Q

Grafo dirigido o dígrafo.

A

Es cuando los bordes entre los pares de vértices tienen una dirección. La dirección de un borde puede representar cosas como jerarquía o flujo.

77
Q

Grafo ciclo o simplemente ciclo

A

Es un grafo que consiste en un camino simple cerrado, es decir, en el que no se repite ningún vértice, salvo el primero con el último.

78
Q

Un bucle o autobucle

A

Es una arista que comienza y termina en el mismo vértice. Un bucle es un ciclo que sólo consta de una arista.

79
Q

Matriz de adyacencia

A

Matriz cuadrada que se utiliza como una forma de representar relaciones entre cada par de nodos

80
Q

Grafos y el problema del camino más corto

A

Significa encontrar la ruta o camino más corto posible entre dos vértices (o nodos) en un grafo.
El algoritmo de Dijkstra y el algoritmo de Bellman-Ford encuentran el camino más corto desde un vértice inicial hasta todos los demás vértices.

81
Q

Algoritmo de Dijkstra

A

Solo trabaja con pesos de aristas positivos.
Encuentra el camino más corto desde un vértice a todos los demás vértices.
Lo hace seleccionando repetidamente el vértice no visitado más cercano y calculando la distancia a todos los vértices vecinos no visitados.

82
Q

Algoritmo de Bellman-Ford

A

Es más adecuado para encontrar los caminos más cortos en un gráfico dirigido, con uno o más pesos de borde negativos, desde el vértice de origen hasta todos los demás vértices.
Lo hace comprobando repetidamente todos los bordes del gráfico en busca de caminos más cortos, tantas veces como vértices hay en el gráfico (menos 1).

83
Q

El problema del árbol de expansión mínimo (MST)

A

Es la colección de aristas necesarias para conectar todos los vértices en un grafo no dirigido, con el peso total mínimo de arista.
El nombre Tree se debe a que es un grafo conectado, acíclico y no dirigido, que es la definición de un TAD de árbol.
Lo implementan el algoritmo de Prim y el algoritmo de Kruskal.

84
Q

Algoritmo de Prim

A

Encuentra el árbol de expansión mínimo (MST) en un gráfico conectado y no dirigido.
Para que funcione, todos los nodos deben estar conectados.

85
Q

Algoritmo de Kruskal.

A

Encuentra el árbol de expansión mínimo (MST), o bosque de expansión mínimo, en un gráfico no dirigido.
El MST (o MST) encontrado por el algoritmo de Kruskal es la colección de aristas que conectan todos los vértices (o tantos como sea posible) con el peso total mínimo de arista.

86
Q

Maximun Flow

A

El problema del flujo máximo consiste en encontrar el flujo máximo a través de un grafo dirigido, de un lugar del grafo a otro, d un vertice fuente a otro vertive destino. Cada arista en el gráfico se define con un flujo y una capacidad (flujo max).

87
Q

algoritmo Ford-Fulkerson

A

Funciona buscando una ruta con capacidad disponible desde la fuente hasta el sumidero (llamada ruta aumentada) y luego envía la mayor cantidad de flujo posible a través de esa ruta.

Continúa encontrando nuevos caminos para enviar más flujo hasta alcanzar el flujo máximo.

No especifica cómo encontrar el camino donde se pueda aumentar el flujo.

88
Q

algoritmo de Edmonds-Karp

A

muy similar al algoritmo de Ford-Fulkerson, excepto que el algoritmo de Edmonds-Karp utiliza Breadth First Search (BFS) para encontrar caminos aumentados para aumentar el flujo.