Considere la siguiente recurrencia. T(n) = T( ) + ¿Cuál es el valor de la recurrencia? (A) (B) (B) (B) (A) A (B) B (C) C (D) D Respuesta: (A) Explicación: Cambio de variables: sea m = lg n. La recurrencia se convierte en S(m) = S(m/2) + theta(lgm). Se aplica el caso 2 del … Continue reading «Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 11»
Un conjunto X se puede representar mediante un arreglo x[n] de la siguiente manera: Considere el siguiente algoritmo en el que x, y y z son arrays booleanas de tamaño n: algorithm zzz(x[] , y[], z []) { int i; for (i=O; i<n; ++i) z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i]) } El … Continue reading «Algoritmos | Varios | Pregunta 13 – Part 1»
¿Cuál de los siguientes algoritmos se puede usar para calcular eficientemente las rutas más cortas de fuente única en un gráfico acíclico dirigido? (A) Dijkstra (B) Bellman-Ford (C) Clasificación topológica (D) Componente fuertemente conectado Respuesta: (C) Explicación: Usando la clasificación topológica, podemos encontrar las rutas más cortas de fuente única en tiempo O(V+E), que es … Continue reading «Algoritmos | Graficar las rutas más cortas | Pregunta 10»
Dada una array no ordenada. La array tiene esta propiedad de que cada elemento en la array está a una distancia máxima de k de su posición en la array ordenada, donde k es un número entero positivo más pequeño que el tamaño de la array. ¿Qué algoritmo de clasificación se puede modificar fácilmente para … Continue reading «Algoritmos | Clasificación | Pregunta 5»
Una empresa de redes utiliza una técnica de compresión para codificar el mensaje antes de transmitirlo por la red. Supongamos que el mensaje contiene los siguientes caracteres con su frecuencia: character Frequency a 5 b 9 c 12 d 13 e 16 f 45 Nota: Cada carácter en el mensaje de entrada ocupa 1 byte. … Continue reading «Algoritmos | Algoritmos codiciosos | Pregunta 3 – Part 1»
En un sprint de 100 metros, Usain Bolt vence a Tyson Gay por 1 metro. En otro sprint de 200 m, Tyson Gay vence a Asafa Powell por 4 metros. ¿Por cuántos metros ganará Bolt a Powell en una carrera larga de 1 KM? (A) 28 metros (B) 298 metros (C) 32 metros (D) 29,8 … Continue reading «Prueba de algoritmos | Colocación de Sudo: Juego 1 | Pregunta 2»
El caso promedio ocurre en el Algoritmo de búsqueda lineal cuando: (A) El elemento que se busca está en algún punto medio de la array (B) El elemento que se busca no está en la array (C) El elemento que se busca está en el último de la array (D) El elemento a buscar está … Continue reading «CGU-NET | UGC NET CS 2015 junio – II | Pregunta 24»
¿Cuál es el valor de retorno de la siguiente función para arr[] = {9, 12, 2, 11, 2, 2, 10, 9, 12, 10, 9, 11, 2} y n es el tamaño de esta array. int fun(int arr[], int n) { int x = arr[0]; for (int i = 1; i < n; i++) x = … Continue reading «Algoritmos | Algoritmos de bits | Pregunta 1»
Considere el siguiente programa en C int main() { int x, y, m, n; scanf («%d %d», &x, &y); /* x > 0 and y > 0 */ m = x; n = y; while (m != n) { if(m>n) m = m – n; else n = n – m; } printf(«%d», n); } … Continue reading «Algoritmos | Divide y vencerás | Pregunta 2»
Se le da una array con elementos enteros pares. Usted y algún otro jugador se turnan para elegir números. Cada jugador puede elegir el elemento más a la izquierda o el número más a la derecha. Encuentre la puntuación máxima posible (suma de los números elegidos) por usted. Por ejemplo: si la array es 5 … Continue reading «Algoritmos | Varios | Pregunta 14»