Considere las siguientes tres afirmaciones I (n + k)^m = (n^m), donde k y m son constantes II 2^(n + 1) = 0(2^n) III 2^(2n + 1) = 0(2^n) ¿Cuáles de estas afirmaciones son correctas? (PUERTA CS 2003) (A) I y II (B) I y III (C) II y III (D) I, II y III … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 16»
Sea X un problema que pertenece a la clase NP. Entonces, ¿cuál de las siguientes es VERDADERA? (A) No existe un algoritmo de tiempo polinomial para X. (B) Si X se puede resolver de forma determinista en tiempo polinomial, entonces P = NP. (C) Si X es NP-duro, entonces es NP-completo. (D) X puede ser … Continue reading «Algoritmos | NP Completo | Pregunta 3»
En un gráfico ponderado, suponga que la ruta más corta desde un origen ‘s’ hasta un destino ‘t’ se calcula correctamente utilizando un algoritmo de ruta más corta. ¿Es verdadera la siguiente afirmación? Si aumentamos el peso de cada borde en 1, el camino más corto siempre permanece igual. (A) Sí (B) No Respuesta: (B) … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 8»
¿Cuáles de los siguientes son los pasos del modelo de cascada en orden? (A) Planificación, comunicación, modelado, construcción, implementación (B) Comunicación, planificación, modelado, construcción, implementación (C) Construcción, planificación, modelado, comunicación, implementación (D) Comunicación, construcción, modelado, planificación, implementación Respuesta: (B) Explicación: Consulte: https://www.slideshare.net/RupeshVaishnav/intoduction-to-software-engineering-part-2-70765085 (Diapositiva 17/62) Prueba de esta pregunta Comente a continuación si encuentra algo incorrecto … Continue reading «Prueba de algoritmos | Colocación de Sudo [1.5] | Pregunta 13»
Considere una array ordenada de n números. ¿Cuál sería la complejidad temporal del algoritmo más conocido para encontrar un par ‘a’ y ‘b’ tal que |ab| = k , siendo k un entero positivo. (A) O(n) (B) O(n log n) (C) O(n ^ 2) (D) O(log n) Respuesta: (A) Explicación: simplemente mantenga dos punteros al … Continue reading «PUERTA | Maqueta de puerta 2017 | Pregunta 23»
El problema de suma de subconjuntos se define de la siguiente manera. Dado un conjunto de n enteros positivos, S = {a1 ,a2 ,a3 ,…,an} y el entero positivo W, ¿existe un subconjunto de S cuyos elementos suman W? Un programa dinámico para resolver este problema utiliza una array booleana bidimensional X, con n filas … Continue reading «Algoritmos | Programación Dinámica | Pregunta 7 – Part 2»
Un grafo no dirigido G(V, E) contiene n ( n > 2 ) Nodes llamados v1 , v2 ,….vn. Dos Nodes vi, vj están conectados si y solo si 0 < |i – j| <= 2. A cada arista (vi, vj) se le asigna un peso i + j. A continuación se muestra un gráfico … Continue reading «Algoritmos | Árbol de expansión mínimo del gráfico | Pregunta 1»
Considere la siguiente función C. float f(float x, int y) { float p, s; int i; for (s=1, p=1, i=1; i < y; i ++) { p*= x/i; s+=p; } return s; } Para valores grandes de y, el valor de retorno de la función f se aproxima mejor (GATE CS 2003) (A) x^y (B) … Continue reading «Algoritmos | Varios | Pregunta 7»
Dados dos vértices en un gráfico s y t, ¿cuál de los dos recorridos (BFS y DFS) se puede usar para encontrar si hay un camino de s a t? (A) Solo BFS (B) Solo DFS (C) Tanto BFS como DFS (D) Ni BFS ni DFS Respuesta: (C) Explicación: Podemos usar ambos recorridos para encontrar … Continue reading «Algoritmos | Gráficos transversales | Pregunta 8»
Dada una array donde los números están en el rango de 1 a n 6 , ¿qué algoritmo de clasificación se puede usar para ordenar estos números en tiempo lineal? (A) No es posible clasificar en tiempo lineal (B) Clasificación Radix (C) Clasificación por conteo (D) Clasificación rápida Respuesta: (B) Explicación: Consulte Clasificación Radix para … Continue reading «Algoritmos | Clasificación | Pregunta 23 – Part 2»