¿Cuál es el peso de un árbol de expansión mínimo del siguiente gráfico? (A) 29 (B) 31 (C) 38 (D) 41 Respuesta: (B) Explicación: (a,c), (a,d), (d,b), (b,g), (g, h), (h,f), (h,i), (i,j), (i,e) = 31 Antecedentes requeridos: árbol de expansión mínimo ( Prims / Kruskal ) En este tipo de preguntas, siempre utilice el … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 90 – Part 6»
Sea S una pila de tamaño n ≥ 1. Comenzando con la pila vacía, supongamos que empujamos los primeros n números naturales en secuencia y luego realizamos n operaciones pop. Suponga que las operaciones Push y pop toman X segundos cada una, y que transcurren Y segundos entre el final de una de esas operaciones … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 64»
Suponga que los números 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 se insertan en ese orden en un árbol de búsqueda binario inicialmente vacío. El árbol de búsqueda binario utiliza el orden habitual de los números naturales. ¿Cuál es la secuencia transversal en orden del árbol resultante? (A) 7 5 1 0 … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 19»
Considere el siguiente programa en lenguaje ensamblador para un procesador hipotético. A, B y C son registros de 8 bits. Los significados de varias instrucciones se muestran como comentarios. MOV B, # 0 ; B ← 0 MOV C, # 8 ; C ← 8 Z : CMP C, # 0 ; … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 48»
Sea ∑ = (a, b, c, d, e) un alfabeto. Definimos un esquema de codificación de la siguiente manera: g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11. ¿Cuál de los siguientes números es el codificando h de una secuencia de strings no vacía? (A) 2 7 3 7 … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 90 – Part 2»
Sea G = ({S}, {a, b} R, S) una gramática libre de contexto donde el conjunto de reglas R es S → a S b | SS | ε ¿Cuál de las siguientes afirmaciones es verdadera? (A) G no es ambiguo (B) Existen x, y, ∈ L (G) tales que xy ∉ L(G) (C) Existe … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 90 – Part 7»
Considere el NFA M que se muestra a continuación. Sea L el lenguaje aceptado por M. Sea L1 el lenguaje aceptado por NFA M1, obtenido al cambiar el estado de aceptación de M a un estado de no aceptación y al cambiar el estado de no aceptación de M a estados de aceptación. Cuál de … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 55»
Se requiere una estructura de datos para almacenar un conjunto de enteros de modo que cada una de las siguientes operaciones se pueda realizar en (log n) tiempo, donde n es el número de elementos en el conjunto. o Delection of the smallest element o Insertion of an element if it is not already present … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 63»
Considere el siguiente programa en lenguaje ensamblador para un procesador hipotético. A, B y C son registros de 8 bits. Los significados de varias instrucciones se muestran como comentarios. MOV B, # 0 ; B ← 0 MOV C, # 8 ; C ← 8 Z : CMP C, # 0 ; comparar C con … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 49»
Defina los idiomas L0 y L1 de la siguiente manera: L0 = {< M, w, 0 > | M halts on w} L1 = {< M, w, 1 > | M does not halts on w} Aquí < M, w, i > es un triplete, cuya primera componente. M es una codificación de una máquina … Continue reading «PUERTA | PUERTA-CS-2003 | Pregunta 54»