¿Cuál es el número de intercambios necesarios para clasificar n elementos utilizando la clasificación por selección, en el peor de los casos? (A) (n) (B) (n log n) (C) (n^2 ) (D) (n^2 log n) (A) Theta(n) (B) Theta(nLogn) (C) Theta (n*n) (D) Theta(n*nLogn) Respuesta: (A) Explicación: Aquí está el algoritmo de clasificación de selección … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 10»
El siguiente DFA acepta el conjunto de todas las strings sobre {0,1} que (A) comienzan con 0 o 1 (B) terminan con 0 (C) terminan con 00 (D) contienen la substring 00. Respuesta: (C) Explicación: si las strings que comienzan con 0 y 1 son 01 y 11 respectivamente, entonces el DFA no los acepta … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 60 – Part 8»
Al abrir una conexión TCP, el número de secuencia inicial debe derivarse utilizando un reloj de hora del día (ToD) que sigue funcionando incluso cuando el host está inactivo. Los 32 bits de orden inferior del contador del reloj ToD se utilizarán para los números de secuencia iniciales. El contador del reloj se incrementa una … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 60 – Part 10»
Sea L = L1∩L2, donde L1 y L2 son idiomas como se define a continuación: L1 = { | m, n >= 0 } L2 = { | i, j, k >= 0 } Entonces L es (A) No recursivo (B) Regular (C) Libre de contexto pero no regular (D) Enumerable recursivamente pero no libre de contexto. … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 60 – Part 2»
El tiempo de ejecución de un algoritmo está representado por la siguiente relación de recurrencia: if n <= 3 then T(n) = n else T(n) = T(n/3) + cn ¿Cuál de los siguientes representa la complejidad temporal del algoritmo? <pre> (A) (n) (B) (n log n) (C) (n^2) (D) (n^2log n) </pre> (A) A (B) … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 35»
Los siguientes valores clave se insertan en un árbol B+ en el que el orden de los Nodes internos es 3 y el de los Nodes hoja es 2, en la secuencia que se indica a continuación. El orden de los Nodes internos es el número máximo de punteros de árbol en cada Node, y … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 44»
¿Cuál de los siguientes idiomas sobre el alfabeto {0,1} se describe mediante la expresión regular: (0+1)*0(0+1)*0(0+1)* ? (A) El conjunto de todas las strings que contienen la substring 00. (B) El conjunto de todas las strings que contienen como máximo dos 0. (C) El conjunto de todas las strings que contienen al menos dos 0. … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 14»
S -> aSa|bSb|a|b; El lenguaje generado por la gramática anterior sobre el alfabeto {a,b} es el conjunto de (A) Todos los palíndromos (B) Todos los palíndromos de longitud impar. (C) Strings que comienzan y terminan con el mismo símbolo (D) Todos los palíndromos de longitud par Respuesta: (B) Explicación: El posible palíndromo generado por la … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 11»
Considere un conjunto de caché asociativo de 4 vías (inicialmente vacío) con un total de 16 bloques de caché. La memoria principal consta de 256 bloques y la solicitud de bloques de memoria es en el siguiente orden: 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155. … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 29»
Considere un sistema de disco con 100 cilindros. Las requests para acceder a los cilindros ocurren en la siguiente secuencia: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Suponiendo que la cabeza está actualmente en el cilindro 50, ¿cuál es el tiempo necesario para satisfacer todas las requests si se tarda 1 ms … Continue reading «PUERTA | PUERTA-CS-2009 | Pregunta 31»