En la siguiente función C, sea n >= m. int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m, n); } ¿Cuántas llamadas recursivas realiza esta función? (A) (logn) (B) (n) (C) (loglogn) (D) (sqrt(n)) (A) A (B) B (C) C (D) D Respuesta: (A) Explicación: El código anterior es la implementación … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 14»
El problema 3-SAT y 2-SAT son (A) ambos en P (B) ambos NP completos (C) NP-completos y en P respectivamente (D) indecidibles y NP-completos respectivamente Respuesta: (C) Explicación: El problema booleano de satisfacibilidad (SAT) es un problema de decisión, cuya instancia es una expresión booleana escrita usando solo AND, OR, NOT, variables y paréntesis. El … Continue reading «Algoritmos | NP Completo | Pregunta 4»
¿La siguiente afirmación es verdadera o falsa? If we make following changes to Dijkstra, then it can be used to find the longest simple path, assume that the graph is acyclic. 1) Initialize all distances as minus infinite instead of plus infinite. 2) Modify the relax condition in Dijkstra’s algorithm to update distance of an … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 9»
Una tubería de drenaje tarda media hora en drenar completamente un tanque cuando se usa sola. Cuando se utiliza junto con un tubo de llenado, se necesitan 30 minutos para llenar completamente el tanque. ¿Cuánto tardará el tubo de llenado en llenar completamente el tanque cuando se usa solo? (A) 10 min (B) 12 min … Continue reading «Prueba de algoritmos | Colocación de Sudo [1.5] | Pregunta 1 – Part 1»
Considere la array A[]= {6,4,8,1,3} aplique la ordenación por inserción para ordenar la array. Considere que el costo asociado con cada clasificación es de 25 rupias, ¿cuál es el costo total de la clasificación por inserción cuando el elemento 1 alcanza la primera posición de la array? (A) 50 (B) 25 (C) 75 (D) 100 … Continue reading «Algoritmos | Clasificación por inserción | Pregunta 4»
¿Cuál es el rendimiento promedio de casos para Comb Sort? (Nota: ‘i’ en las opciones es el número si se incrementa) (A) Ω(n 2 / i) (B) Ω(n 2 / 2 i ) (C) Ω(n 2 / 4 i ) (D) Ω(n 2 / 3 i ) Respuesta: (B) Explicación: Cuestionario de esta pregunta Publicación … Continue reading «Algoritmos | ordenar con peine | Pregunta 1»
#include<stdio.h> void crazy(int n,int a,int b) { if (n <= 0) return; crazy(n-1, a, b+n); printf(«%d %d %d\n»,n,a,b); crazy(n-1, b, a+n); } int main() { crazy(3,4,5); return 0; } (A) 1 4 10 2 4 8 1 8 6 3 4 5 1 5 9 2 5 7 1 7 7 (B) 3 4 … Continue reading «Algoritmos | Recursividad | Pregunta 9 – Part 1»
¿Cuál es la complejidad temporal de la codificación Huffman? (A) O(N) (B) O(NlogN) (C) O(N(logN)^2) (D) O(N^2) Respuesta: (B) Explicación: O(nlogn) donde n es el número de caracteres únicos. Si hay n Nodes, extractMin() se llama 2*(n – 1) veces. extractMin() toma el tiempo O(logn) ya que llama minHeapify(). Entonces, la complejidad general es O … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 3»
¿La siguiente declaración es verdadera/falsa? Si un DFS de un gráfico dirigido contiene un borde posterior, cualquier otro DFS del mismo gráfico también contendrá al menos un borde posterior. Fuente: http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-s2009-sol.pdf (A) Verdadero (B) Falso Respuesta: (A) Explicación: Un borde posterior significa un ciclo en el gráfico . Entonces, si hay un ciclo, todos los … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 1»
En la ordenación rápida, para ordenar n elementos, el elemento más pequeño (n/4) se selecciona como pivote utilizando un algoritmo de tiempo O(n). ¿Cuál es la complejidad de tiempo en el peor de los casos del tipo rápido? (A) (n) (B) (nLogn) (C) (n^2) (D) (n^2 log n) (A) A (B) B (C) C (D) … Continue reading «Algoritmos | Clasificación | Pregunta 17»