Algoritmos y EEDD Flashcards
¿En que consiste la técnica de Backtracking?
Técnica de diseño de algoritmo basada en explorar todo el árbol de posibles soluciones (prueba y error)
¿Qué requisito tiene el algoritmo de la búsqueda binaria y que complejidad computacional tiene?
Que los datos esten ordenados (array, arbol…)
0(log n)
Ordene, de mas eficiente a menos, estas complejidades: n!, nlogn, n^2, 2^n
n log (n), n^2, 2^n, n!
¿En que consiste cada iteración del algoritmo Radix-Sort?
En distribuir en las colas o urnas, los números según un determinado digito (unidades, decenas, centenas… o al reves)
De una definición de la propiedad de estabilidad en los algoritmos de ordenación
Mantiene el orden relativo original para claves iguales
¿En que consiste el algoritmo de inserción binaria?
Mediante búsqueda binaria obtenemos el lugar donde inserta el elemento a ordenar en cada iteración
El algoritmo de ordenación BubleSort siempre presenta una complejidad 0(n^2)?
No, en el mejor de los casos seria O(n) – se da cuenta si los datos ya están ordenados
¿Qué requisito necesita cualquier función recursiva?
Una condición de parada (CASO BASE)
¿Cómo explicaría el mecanismo que se produce en una llamada a la función?
Cuando se llama a una función, se introducen en la pila los siguientes datos:
a) Parámetros de entrada
b) Variables locales
c) Dirección de retorno
D) valor de retorno
¿Qué es la complejidad espacial?
Representa la cantidad de espacio adicional (a los datos de entrada) que necesita el algoritmo
¿En que consiste un max-heap?
Un árbol binario (montículo) cuya raíz es el elemento mayor de todos los del árbol. Esta propiedad se cumple en cualquier nivel,
¿A que TAD pertenecen las primitivas push y pop?
TAD pila (LIFO)
¿En que consiste una colisión en una taba Hash?
Una colisión se da cuando aplicando el algoritmo de Hash a las distintas keys dan el mismo resultado (índice de la tabla)
Definición de altura y profundidad de un nodo
Altura: numero de aristas desde ese nodo hasta el nodo hoja mas alejado
Profundidad: numero de aristas desde ese nodo hasta la raíz
Definición de grado de un nodo y el orden del árbol
Grado: numero de hijos que tiene un nodo en un momento determinado, limitado por el orden del árbol.
Orden: numero máximo de hijos que puede tener cualquier nodo
¿En que consiste un árbol AVL?
es un árbol que mantiene automáticamente un factor de equilibrio entre 0, +1 o -1 (autobalanceable)
¿Para que sirve el algoritmo de Kruskal?
Algoritmo que sirve para generar un árbol de recubrimiento mínimo (árbol que conecta a todos los nodos con coste global mínimo)
¿En que consiste el grado de un vértice de un grafo?
numero de aristas incidentes
¿Para que sirve el algoritmo de Dijkstra?
Algoritmo que sirve para calcular el camino mínimo de un nodo al resto (caso particular seria entre dos nodos)
¿Cuáles son dos características de los arboles B+?
nodos hoja están entrelazados, nodos internos solo contienen claves y punteros
