En una evaluación ascendente de una definición dirigida por la sintaxis, los atributos heredados pueden (A) evaluarse siempre (B) evaluarse solo si la definición tiene atributos L (C) evaluarse solo si la definición tiene atributos sintetizados (D) nunca ser evaluado Respuesta: (B) Explicación: Una definición dirigida por la sintaxis (SDD) se llama S Attributed si … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 18»
La raíz cúbica de un número natural n se define como el mayor número natural m tal que m 3 ≤ n. La complejidad de calcular la raíz cúbica de n (n se representa en notación binaria) es: (A) O(n) pero no O(n 0.5 ) (B) O(n 0.5 ) pero no O((log n) k ) … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 66»
Considere el conjunto {a, b, c} con operadores binarios + y × definidos de la siguiente manera: + a b C × a b C a b a C a a b C b a b C b b C a C a C b C C C b Por ejemplo, a + c = … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 38»
Considere tres elementos de datos D1, D2 y D3 y el siguiente programa de ejecución de transacciones T1, T2 y T3. En el diagrama, R(D) y W(D) indican las acciones de lectura y escritura del elemento de datos D, respectivamente. ¿Cuál de las siguientes afirmaciones es correcta? (A) El horario es serializable como T2; T3; … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 90 – Part 1»
Considere el conjunto ∑* de todas las strings sobre el alfabeto ∑ = {0, 1}. ∑* con el operador de concatenación para strings (A) no forma un grupo (B) forma un grupo no conmutativo (C) no tiene un elemento de identidad correcto (D) forma un grupo si se elimina la string vacía de ∑* Respuesta: … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 7 – Part 1»
¿Cuál de los siguientes es suficiente para convertir una gramática CFG arbitraria en una gramática LL(1)? (A) Eliminar la recursión por la izquierda sola (B) Factorizar solo la gramática (C) Eliminar la recursividad por la izquierda y factorizar la gramática (D) Ninguno de estos Respuesta: (D) Explicación: Eliminar la recursividad por la izquierda y factorizar … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 16»
Se ha pedido a Ram y Shyam que demuestren que cierto problema Π es NP-completo. Ram muestra una reducción de tiempo polinomial del problema 3-SAT a Π, y Shyam muestra una reducción de tiempo polinomial de Π a 3-SAT. ¿Cuál de los siguientes se puede inferir de estas reducciones? (A) Π es NP-duro pero no … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 12»
En un montón con n elementos con el elemento más pequeño en la raíz, el séptimo elemento más pequeño se puede encontrar en el tiempo (A) Θ(n log n) (B) Θ(n) (C) Θ(log n) (D) Θ(1) Respuesta: (D) Explicación: Para encontrar el k-ésimo elemento más pequeño, primero tenemos que extraer 6 elementos del montón y … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 23»