Considere las siguientes funciones: f(n) = 2^n g(n) = n! h(n) = n^logn ¿Cuál de las siguientes afirmaciones sobre el comportamiento asintótico de f(n), g(n) y h(n) es verdadera? (A) f(n) = O(g(n)); g(n) = O(h(n)) (B) f(n) = (g(n)); g(n) = O(h(n)) (C) g(n) = O(f(n)); h(n) = O(f(n)) (D) h(n) = O(f(n)); g(n) … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 13»
Sea s una array ordenada de n enteros. Sea t(n) el tiempo que tarda el algoritmo más eficiente en determinar si hay dos elementos con una suma menor que 1000 en s. ¿Cuál de las siguientes afirmaciones es verdadera? (GATE CS 2000) a) t (n) es 0 (1) b) n < t (n) < n … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 17»
¿Cuál es el valor de retorno de la siguiente función para 484? ¿A qué se debe en general? bool fun(int n) { int sum = 0; for (int odd = 1; n > sum; odd = odd+2) sum = sum + odd; return (n == sum); } (A) Falso, comprueba si un número dado es … Continue reading «Algoritmos | Varios | Pregunta 15»
El espacio auxiliar del ordenamiento por inserción es O(1), ¿qué significa O(1)? (A) La memoria (espacio) requerida para procesar los datos no es constante. (B) Significa que la cantidad de memoria adicional que consume la ordenación por inserción no depende de la entrada. El algoritmo debe usar la misma cantidad de memoria para todas las … Continue reading «Algoritmos | Clasificación por inserción | Pregunta 5»
Encuentre el orden interno y posterior del árbol binario con el orden previo dado: 60, 40, 20, 10, 30, 33, 50, 44, 51, 90, 70, 65, 80, 110, 100, 95, 99, 120. (A) En orden: 110, 100, 99, 90, 80, 70, 65, 60, 51, 50, 44, 40, 33, 30, 20, 10. Posorden: 110, 120, 100, … Continue reading «Prueba de algoritmos | Colocación de Sudo: Juego 1 | Pregunta 7»
Debe clasificar 1 GB de datos con solo 100 MB de memoria principal disponible. ¿Qué técnica de clasificación será la más adecuada? (A) Ordenación en montón (B) Ordenación por fusión (C) Ordenación rápida (D) Ordenación por inserción Respuesta: (B) Explicación: Los datos se pueden ordenar usando una clasificación externa que utiliza la técnica de fusión. … Continue reading «Algoritmos | Clasificación | Pregunta 11»
¿Cuál es el otro nombre del algoritmo de Dijkstra? (A) problema de la ruta más corta de una sola fuente (B) problema de la ruta más corta de múltiples fuentes (C) problema de la ruta más corta de múltiples destinos (D) problema de la ruta más corta de un solo destino Respuesta: (A) Explicación: prueba … Continue reading «Prueba de algoritmos | Algoritmos codiciosos | Pregunta 8»
En la pregunta #2, ¿cuál de las siguientes representa la palabra “muerto” ? (A) 1011111100101 (B) 0100000011010 (C) Tanto A como B (D) Ninguno de estos Respuesta: (C) Explicación: El árbol de Huffman generado es: character code-word f 0 c 100 d 101 a 1100 b 1101 e 111 La palabra muerto se puede representar … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 4»
El recorrido de un gráfico es diferente del árbol porque (A) Puede haber un bucle en el gráfico, por lo que debemos mantener una marca visitada para cada vértice (B) El DFS de un gráfico usa la pila, pero en orden el recorrido de un árbol es recursivo (C) El BFS de un gráfico usa … Continue reading «Algoritmos | Gráficos transversales | Pregunta 2»
Considere el algoritmo Quicksort. Supongamos que existe un procedimiento para encontrar un elemento pivote que divide la lista en dos sublistas, cada una de las cuales contiene al menos una quinta parte de los elementos. Sea T(n) el número de comparaciones necesarias para clasificar n elementos. Entonces (A) T(n) <= 2T(n/5) + n (B) T(n) … Continue reading «Algoritmos | Clasificación | Pregunta 18»