GRE - Computer science test
Juan Camilo Muñoz Castelblanco
Cód. 257120
2. Es la (E) 0.5, ya que tiene una exacta representación en binario que es 0.1b, que al pasarlo a decimal es 1x2-1 = 0.5.
3. Es la (E) 10, ya que solo puede hacer de a dos preguntas, continuamente es decir cada pregunta delimita el problema a n/2, y así sucesivamente, de esto conocemos que las preguntas que hace son log2 1000 = 10, es decir que a lo máximo tendrá que hacer diez preguntas para encontrar la solución.
7. Es la (D), ya que haciendo el seguimiento de las instrucciones y
sustituyendo encontramos que:
Las entradas son k0=2 y m0=3
k1 = k0-m0
m1 = k1+m0
k2 = m1-k1
y las salidas serán k2 y m1
k2 = m1-k1
= (k0) - (k0-m0) = m0 = 3
m1 = k1+m0 = (k0-m0)
+ m0 = k0 = 2
Es decir que la función lo que hace es intercambiar las variables de
entrada, sin usar una variable auxiliar.
9. Es la (A), ya que para eliminar el último elemento de la lista, se debe
recorrerla toda, o pasar por todos los nodos, es decir que un algoritmo para
eliminar el último elemento tendrá una complejidad O(n).
10. Es la (D), en esta se plantea que la invariante de ciclo va ha ser pk=2k para cuando el programa se
encuentre en la k-ésima iteración es válido, ya que para k=0, p0=1
y p0=20 <=> p0=1; entonces suponemos
para la iteración k la invariante de ciclo es cierta (Hipótesis), y probamos
para k+1, pk+1=2k+1
= 2*2k =2*pk, es decir que para
k+1, es válido, entonces es también válida la hipótesis.
13. Es la (B), ya que el número de líneas esta regido por el factor i/j,
que se compara contra 0.001, tenemos que:
Obtenemos que para que continúe en el ciclo k<10.96, pero cuando sale es en el k=11, es decir que ha hecho 11 iteraciones e impresiones.
14. Es la (E), ya que la segunda variable que se imprime es sum y esta tiende a ser 4, se tiene que:
15. Es la (c), ya que {-6,-3,-2,-1,1,2,3,6}, es la
única terna que cumple la condición de
que tengan números que son comunes divisores de otros 2 números, por ejemplo el
0 no es común divisor ya que su división por cualquier número da infinito y el
4 no porque su común divisor es el 2, y ya esta contenido en la serie.
17. Es la (D), ya que de los 100seg, 40seg son secuenciales, de lo cual
quedan 60seg que se pueden ejecutar de forma paralela, para el caso que sean
dos computadoras, se va a demorar 40seg (fijos) + (60seg/2) = 70seg, y para el
caso que sean cuatro computadoras, se va a demorar 40seg (fijos) + (60seg/4) =
55seg.
20. Es la (D), ya que en un procedimiento P que es recursivo, y se asegura
su terminación, necesariamente debe manejar una variable local que va decrementando a medida que se llama a si mismo además debe
tener un segmento de código donde no se llame a si mismo y comience a devolver
el valor del procedimiento.
26. Es la (C), ya que el segmento de código III hace lo mismo que el
enunciado, tienen la misma precondición, el ciclo se comporta igual y tienen la
misma condición de salida. También sería igual si
i=1
while i<=N
do
begin V[i] = V[i] +1 ; i=i+1 end
27. Es la (E), ya que si x>10, se acaba el while,
y si x<10, va a salirse el programa por el if y
los resultados son los correspondientemente los siguientes:
El primero solo dice que se acabo sin ningún contratiempo el programa y se
tiene estos resultados, en el segundo caso, se acaba abruptamente teniendo como
resultado para i y j sus respectivas invariantes de ciclo para x>0.
63. Es la (E), N posiciones corre máximo un elemento del primer arreglo
ordenado, hacia el segundo, ya que si miramos un caso extremo en el que el
primer elemento del primer arreglo es menor que todos lo elementos del segundo
arreglo, el arreglo principal va a estar compuesto primero por el segundo
arreglo y luego por el primer arreglo, en el que el elemento que esta en la
posición N corresponde al elemento que estaba en la primera posición del primer
arreglo.