PROGRAMACION AVANZADA - ALGORITMIA

ALGORITMIA. HASHING.

¿En qué consiste la técnica del hashing?. Una vez buscado el elemento de forma aleatoria, cambiarle la posición. Comprimir datos para que ocupen menos espacio. Transformar una clave o dato en una posición dentro de una tabla o estructura de almacenamiento. Buscar elementos de forma aleatoria.

En la técnica hashing no es necesario que los elementos se encuentren con una estructura lineal. Verdadero. Falso.

En las técnicas de hashing, cuando dos llaves tienen el mismo valor hash, esto se llama: Dispersión. Distribución. Colisión. Rehashing.

En la exploración lineal, las concentraciones de claves no tienen ningún impacto en la eficiencia de la búsqueda, y siempre es ideal tener una tabla hash cuyo tamaño sea exactamente igual al número de elementos que queremos insertar. Verdadero. Falso.

Algunas de las posibles funciones hash son: Dividir por cero. Multiplicador. Truncamiento. Aritmética modular. Doblamiento.

El factor de carga de una tabla hash es el cociente entre el tamaño de la tabla y el número de elementos en ella, y su valor puede ser mayor que 1. Verdadero. Falso.

Queremos insertar el H(e)=3, en el hipotético caso te encuentras una colisión utiliza la alternativa cuadrática. ¿ En qué posición colocaremos el valor "e" en la siguiente tabla?. 8. 7. 4. 3.

La redispersión o rehashing se aplica únicamente cuando la ocupación de la tabla supera el 50% y nunca se considera acortar o reducir el tamaño de la tabla hash independientemente del porcentaje de ocupación. Verdadero. Falso.

En el contexto de exploración lineal en tablas hash, si un índice determinado por la función hash está ocupado. ¿Qué acción se toma para resolver la colisión?. Se elimina el elemento existente y se coloca el nuevo elemento. Se devuelve al índice inicial de la tabla. Se detiene la inserción y se devuelve un error. Se pasa al siguiente índice y se repite el proceso hasta encontrar un índice libre.

El encadenamiento en tablas hash se refiere a la técnica donde, para gestionar colisiones, cada posición de la tabla tiene asociada una lista enlazada en la que se insertan elementos cuya clave hash les asigna la misma posición. Verdadero. Falso.

ALGORITMIA. BACKTRACKING, BRANCH & BOUND.

El backtracking es una técnica que busca soluciones que satisfacen ciertas restricciones. Aunque puede ser utilizado para encontrar la mejor solución basada en una función objetivo en problemas de optimización, también puede ser usado para simplemente encontrar una solución que cumpla con las restricciones en problemas de decisión. Verdadero. Falso.

Estás utilizando Branch & Bound para encontrar la secuencia óptima de trabajos a realizar en una máquina que minimice el tiempo total de procesamiento. A medida que exploras cada posible secuencia, llegas a un punto donde el tiempo acumulado de una secuencia parcial ya excede el tiempo de una solución previamente encontrada. En términos de Branch & Bound, ¿Qué haces en este punto?. Continúa explorando todos los trabajos restantes para esa secuencia, porque cada secuencia es única. Descarta la secuencia actual y retrocede para probar otra alternativa, ya que no es prometedora. Marca el nodo actual como nodo solución, porque ha alcanzado una secuencia completa. Revisa las restricciones del problema para ver si se pueden cambiar.

El backtracking no es muy eficiente ya que se basa en el método prueba y error. Verdadero. Falso.

¿De qué factor/es depende la eficiencia del backtracking ?. El número de nodos del árbol de búsqueda que se visitan para conseguir la solución. El coste de la función de solución completa o ver si la solución es aceptable hasta el momento. Siempre hay muchas soluciones y se puede escoger la que se realice de manera más rápida. Depende del factor de carga.

El árbol de búsqueda es el algoritmo de vuelta atrás que proporciona una manera sistemática de generar todas las posibles soluciones siempre que se puedan resolver por etapas, lo que se asemeja mucho a una búsqueda combinatoria. Verdadero. Falso.

¿Qué estructura de datos es comúnmente asociada con el backtracking debido a su naturaleza recursiva?. Lista enlazada. Árbol de búsqueda. Hash map. Gráfico dirigido.

En backtracking, una vez que se encuentra una solución válida, el algoritmo se detiene y no explora más ramas del árbol de búsqueda. Verdadero. Falso.

¿Cuál de las siguientes afirmaciones sobre el backtracking es cierta?. Se utiliza exclusivamente para problemas de optimización. Una vez encontrada una solución, el algoritmo se detiene. Explora todas las posibles soluciones a un problema hasta encontrar la correcta o determinar que no hay solución. Es un algoritmo determinista que siempre tiene un tiempo de ejecución constante.

¿Cómo contribuye Branch and Bound a la eficiencia en la solución de problemas?. Proporciona un método heurístico para aproximarse a la solución. Reduce el espacio de búsqueda al descartar soluciones subóptimas. Divide el problema en subproblemas más pequeños y los resuelve individualmente. Soluciona el problema en tiempo polinómico.

En la técnica de Branch and Bound, si una cota inferior de una solución parcial es mayor que la cota superior de la mejor solución conocida, esa rama se descarta. Verdadero. Falso.

ALGORITMIA. ALGORITMOS DE ORDENACION.

Dado el siguiente vector: Utilizando el algoritmo QuickSort, si seleccionamos 5 como el pivote inicial. ¿Cuál de las siguientes afirmaciones es correcta después de la primera partición?. Todos los números a la izquierda de 5 son menores que 5, y todos los números a la derecha son mayores. El pivote 5 se coloca al principio del vector después de la partición. El vector se transforma en 1,2,3,4,5,6,7. El vector se transforma en 4,5,3,2,6,1,7.

El algoritmo QuickSort siempre divide el vector en dos subvectores de igual tamaño cuando elige un pivote. Verdadero. Falso.

Queremos aplicar el método QuickSort en el vector que hay a continuación. El proceso finaliza cuando la "i" y la "j" se cruzan. Teniendo en cuenta que el pivote es el 3, marca la opción correcta. 2134576. 2164573. 3214576. 1237564.

Una de las estrategias para mejorar el rendimiento promedio del QuickSort es siempre usar el primer elemento del vector como pivote. Verdadero. Falso.

¿Cuál de los siguientes algoritmos compara elementos separados por un espacio de varias posiciones permitiendo un "paso más grande" hacia su posición esperada?. QuickSort. Método Shell. Bucket Sort. Árbol de búsquedas.

En el Bucket sort, si todos los elementos se agrupan en el mismo cubo, la complejidad temporal pasa a depender del algoritmo de ordenación por inserción y puede llegar a ser O(n^2) en el peor caso. Verdadero. Falso.

En el algoritmo de ordenación QuickSort, ¿qué estrategia utiliza para clasificar rápidamente los elementos?. Método Shell. Bucket Sort. Divide y vencerás. Multiplicar por dos.

QuickSort es un algoritmo que solo funciona bien para conjuntos de datos pequeños. Verdadero. Falso.

¿Cuál es el orden "in-order" de recorrido de un árbol binario de búsqueda para obtener la lista ordenada de elementos?. Raíz, Izquierda, Derecha. Derecha, Raíz, Izquierda. Raíz, Derecha, Izquierda. Izquierda, Raíz, Derecha.

Un árbol binario de búsqueda (ABB) asegura que todos los elementos almacenados en el subárbol derecho de cualquier nodo son menores que el elemento almacenado en ese nodo. Verdadero. Falso.

ALGORITMIA. ALGORITMOS DE BÚSQUEDA.

El algoritmo Knuth - Morris - Pratt (KMP) se concentra en estudiar principalmente: La secuencia S. El patrón P. Ambos, la secuencia y el patrón. Ninguno de los anteriores.

Los algoritmos de búsqueda son técnicas utilizadas para encontrar información específica en un conjunto de datos. Verdadero. Falso.

Algoritmo de búsqueda donde se compara el patrón de derecha a izquierda. Algoritmo Boyer-Moore. Algoritmo Knuth-Morris-Pratt (KMP). Algoritmo de fuerza bruta. Algoritmo In-Orden.

Los algoritmos KMP utilizan la información que tiene del patrón justo antes del momento del fallo. Verdadero. Falso.

El algoritmo Boyer Moore (BM) compara caracteres: De izquierda a derecha. Solo el primer y último carácter. De manera aleatoria. De derecha a izquierda.

El algoritmo BM funciona particularmente bien para patrones de búsqueda largos y puede ser sublineal. Verdadero. Falso.

¿Cuál de los siguientes algoritmos de búsqueda se utiliza mejor para buscar un elemento en una lista no ordenada?. Búsqueda secuencial. Búsqueda binaria. Algoritmo de Boyer Moore. Algoritmo de Knuth-Morris-Pratt.

La búsqueda binaria funciona de manera eficiente en listas no ordenadas. Verdadero. Falso.

¿Qué algoritmo busca ocurrencias de una "palabra" W dentro de una "cadena de texto" S evitando reexaminar caracteres previamente emparejados?. Algoritmo Knuth - Morris - Pratt (KMP). Algoritmo de búsqueda directa. Algoritmo Boyer Moore (BM). Ninguno de los anteriores.

La búsqueda secuencial es un algoritmo de búsqueda que funciona de manera eficiente en listas ordenadas. Verdadero. Falso.