Para los problemas X e Y, Y es NP-completo y X se reduce a Y en tiempo polinomial. ¿Cual de los siguientes es verdadero? (A) Si X se puede resolver en tiempo polinomial, entonces también se puede resolver Y (B) X es NP-completo (C) X es NP-difícil (D) X está en NP, pero no necesariamente … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 11»
¡El exponente de 11 en la descomposición en factores primos de 300! es (A) 27 (B) 28 (C) 29 (D) 30 Respuesta: (C) Explicación: Para obtener el exponente de 11, primero necesitamos obtener la figura 11 en nuestra serie => Por debajo de 11, no habrá factor de 11 11*12*13*14*……..22…….33……..44…………..55…….66…..77….88…99…110…121….132 ….. # # # # … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 23»
Para el gráfico ponderado no dirigido que se muestra a continuación, ¿cuál de las siguientes secuencias de aristas representa una ejecución correcta del algoritmo de Prim para construir un árbol de expansión mínimo? (A) (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h) (B) (c, e), (c, f), … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 43»
Cuando n = 2 2k para algún k ≥ 0, la relación de recurrencia T(n) = √(2) T(n/2) + √n, T(1) = 1 se evalúa como: (A) √(n) (log n + 1) (B) √(n) (log n ) (C) √(n) log √(n) (D) n log √(n) Respuesta: (A) Explicación: tenga en cuenta que la pregunta se … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 42»
Considere los siguientes dos autómatas finitos. M 1 acepta L 1 y M 2 acepta L 2 . ¿Cuál de las siguientes es VERDADERA? (A) L 1 = L 2 (B) L 1 ⊂ L 2 (C) L 1 ∩ L 2 ‘ = ∅ (D) L 1 ∪ L 2 ≠ L 1 Respuesta: … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 34»
Si usamos Radix Sort para ordenar n enteros en el rango (n k/2 ,n k ], para algún k>0 que sea independiente de n, ¿el tiempo necesario sería? (A) Θ(n) (B) Θ (kn) (C) Θ(nlogn) (D) Θ(n 2 ) Respuesta: (C) Explicación: Radix sort tiempo complejidad = O(wn) para n claves de tamaño de palabra= … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 41»
Considere el siguiente diagrama de estado y su realización por un flip flop JK El circuito combinacional genera J y K en términos de x, y y Q. Las expresiones booleanas para J y K son: (A) (x⊕y)’y x’⊕y’ (B) (x⊕y)’y x⊕y (C) x⊕y y (x⊕y)’ (D) x⊕yand x⊕y Respuesta: (D) Explicación: Cuestionario de esta … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 35»
¿Cuál es el número cromático de la siguiente gráfica? (A) 2 (B) 3 (C) 4 (D) 5 Respuesta: (B) Explicación: El número cromático de un gráfico es el menor número de colores necesarios para colorear los vértices de modo que no haya dos vértices adyacentes del mismo color. . En este gráfico, el número mínimo … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 3 – Part 10»
Considere una CPU donde todas las instrucciones requieren 7 ciclos de reloj para completar la ejecución. Hay 140 instrucciones en el conjunto de instrucciones. Se encuentra que se necesitan 125 señales de control para ser generadas por la unidad de control. Al diseñar la unidad de control microprogramada horizontal, se usa un formato de campo … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 37»
Considere los siguientes idiomas. L 1 = {a yo segundo j c k | yo = j, k ≥ 1} L 1 = {a yo segundo j | j = 2i, i ≥ 0} ¿Cuál de las siguientes es verdadera? (A) L 1 no es una CFL pero L 2 es (B) L 1 ∩ … Continue reading «PUERTA | Puerta TI 2008 | Pregunta 31»