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
