La relación de recurrencia que captura el tiempo óptimo del problema de la Torre de Hanoi con n discos es. (GATE CS 2012) (A) T(n) = 2T(n – 2) + 2 (B) T(n) = 2T(n – 1) + n (C) T(n) = 2T(n/2) + 1 (D) T(n) = 2T(n – 1) + 1 Respuesta: (D) … Continue reading «Algoritmos | Análisis de Algoritmos | Pregunta 3»
¿Cuáles de las siguientes afirmaciones son VERDADERAS? (1) El problema de determinar si existe un ciclo en un grafo no dirigido está en P. (2) El problema de determinar si existe un ciclo en un grafo no dirigido está en NP. (3) Si un problema A es NP-Completo, existe un algoritmo de tiempo polinomial no … Continue reading «Algoritmos | NP Completo | Pregunta 5»
Supongamos que ejecutamos el algoritmo de ruta más corta de fuente única de Dijkstra en el siguiente gráfico dirigido ponderado por borde con el vértice P como fuente. ¿En qué orden se incluyen los Nodes en el conjunto de vértices para los cuales se finalizan las distancias de camino más cortas? (GATE CS 2004) (A) … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 14 – Part 1»
Aquí están los dos procesos concurrentes P 1 , P 2 con sus respectivos códigos: Código P 1 : while (true) // infinite condition { A :____; printf(«%d», 1); printf(«%d», 1); B:____; } Código P2 : while (true) // infinite condition { C:____; printf(«%d», 0); printf(«%d», 0); D:____; } ¿Cuál debe ser la operación del … Continue reading «Prueba de algoritmos | Colocación de Sudo: Juego 1 | Pregunta 8»
5 trabajadores y 3 mujeres pueden terminar un trabajo en 10 días, 8 trabajadores y 12 mujeres pueden terminar el mismo trabajo en 5 días. ¿Cuántas trabajadoras (solamente) se requieren para terminar el mismo trabajo en un día? (A) 360 (B) 720 (C) 180 (D) 90 Respuesta: (C) Explicación: Prueba de esta pregunta Publicación traducida … Continue reading «Prueba de algoritmos | Colocación de Sudo: Juego 1 | Pregunta 4»
Un convoy de 40 autos ocupa un estacionamiento que contiene 6 filas de estacionamiento donde cada fila contiene 10 estacionamientos. Si el estacionamiento se lleva a cabo al azar, ¿cuál es la probabilidad de que el cuarto estacionamiento en la fila 4 esté vacío? (A) 1 (B) 1/2 (C) 1/3 (D) 0 Respuesta: (C) Explicación: … Continue reading «Prueba de algoritmos | Colocación de Sudo [1.5] | Pregunta 4»
¿Qué hace la siguiente expresión C? x = x & (x-1) (A) Establece todos los bits en 1 (B) Hace que x sea igual a 0 (C) Activa el bit activado más a la derecha (D) Activa el bit activado más a la izquierda Respuesta: (C) Explicación: La expresión simplemente desactiva el bit activado más … Continue reading «Algoritmos | Algoritmos de bits | Pregunta 3»
¿Cuál de los siguientes es cierto acerca de los algoritmos Kruskal y Prim MST? Suponga que Prim se implementa para la representación de listas de adyacencia mediante Binary Heap y Kruskal se implementa mediante unión por rango. (A) En el peor de los casos, la complejidad temporal de ambos algoritmos es la misma. (B) En … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 5»
¿Cuáles son las estructuras de datos apropiadas para los siguientes algoritmos? 1) Breadth First Search 2) Depth First Search 3) Prim’s Minimum Spanning Tree 4) Kruskal’ Minimum Spanning Tree … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12»
¿Cuál es la complejidad temporal en el peor de los casos de ordenación por inserción en la que la posición de los datos que se insertarán se calcula mediante la búsqueda binaria? (A) N (B) NlogN (C) N^2 (D) N(logN)^2 Respuesta: (C) Explicación: aplicar la búsqueda binaria para calcular la posición de los datos que … Continue reading «Algoritmos | Clasificación | Pregunta 12»