Se le da una lista de 5 enteros y estos enteros están en el rango de 1 a 6. No hay duplicados en la lista. Falta uno de los enteros en la lista. ¿Cuál de las siguientes expresiones daría el número que falta? ^ es un operador XOR bit a bit. ~ es un operador … Continue reading «Algoritmos | Buscando | Pregunta 6»
En la pregunta anterior, la corrección necesaria en el programa para que funcione correctamente es (GATE CS 2008) (A) Cambie la línea 6 a: if (Y[k] < x) i = k + 1; de lo contrario j = k-1; (B) Cambie la línea 6 a: si (Y[k] < x) i = k – 1; de … Continue reading «Algoritmos | Buscando | Pregunta 6 – Part 1»
Dada una array ordenada de enteros, ¿cuál puede ser la complejidad de tiempo mínima en el peor de los casos para encontrar el techo de un número x en una array determinada? El techo de un elemento x es el elemento más pequeño presente en la array que es mayor o igual que x. El … Continue reading «Algoritmos | Buscando | Pregunta 3»
Considere el siguiente programa en C que intenta ubicar un elemento x en una array Y[] mediante la búsqueda binaria. El programa es erróneo. (PUERTA CS 2008) 1. f(int Y[10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5. k = (i + j) /2; … Continue reading «Algoritmos | Buscando | Pregunta 4»
¿Cuál de las siguientes es la recurrencia correcta para el peor de los casos de búsqueda binaria? (A) T(n) = 2T(n/2) + O(1) y T(1) = T(0) = O(1) (B) T(n) = T(n-1) + O (1) y T(1) = T(0) = O(1) (C) T(n) = T(n/2) + O(1) y T(1) = T(0) = O( 1) … Continue reading «Algoritmos | Buscando | Pregunta 2»