Preguntas preliminares de la prueba de la 15ª Liga Olimpiada Nacional de Informática Juvenil
(El lenguaje Pascal del grupo popular se puede completar en dos horas)
● ● Respuestas a todas las pruebas las preguntas deben estar escritas No es válido escribir en la hoja de respuestas o en el examen ●●
1. Preguntas de opción múltiple (***20 preguntas, cada pregunta tiene 1,5 puntos, ***30 puntos. Cada pregunta tiene una y solo una respuesta correcta).
1. es correcto:
A) La máquina de Turing fue la primera computadora electrónica del mundo.
B) Las máquinas de Turing son lentas debido al uso intensivo de operaciones con cinta.
C) La máquina de Turing fue inventada por el británico Turing y jugó un papel importante en el descifrado de los códigos del ejército alemán durante la Segunda Guerra Mundial.
D) La máquina de Turing es sólo un modelo informático teórico.
2. ¿Cuál de las siguientes afirmaciones sobre la memoria de la computadora es correcta?
A) La memoria de acceso aleatorio (RAM) significa la memoria asignada al programa cada vez que se ejecuta. La ubicación es aleatoria e incierta.
B) 1 MB de memoria generalmente se refiere a 1024*1024 bytes de memoria.
C) En rigor, la memoria de la computadora incluye tres partes: memoria principal (memoria), caché (caché) y registro (registro).
D) Generalmente, los datos en la memoria se pueden retener durante más de 2 horas incluso cuando la alimentación está apagada.
3. ¿Cuál de las siguientes afirmaciones sobre BIOS es correcta?
A) BIOS es la abreviatura de software básico de sistema de entrada y salida de computadora.
B) La BIOS contiene controladores para dispositivos de entrada y salida comunes como teclados, ratones, tarjetas de sonido, tarjetas gráficas, impresoras, etc.
C) La BIOS generalmente la desarrollan los fabricantes de sistemas operativos.
D) BIOS puede proporcionar varias funciones de administración de archivos, como copia, duplicación, eliminación y mantenimiento de directorios.
4. ¿Cuál de las siguientes afirmaciones sobre CPU es correcta?
A) CPU significa unidad central de procesamiento (o unidad central de procesamiento).
B) La CPU puede ejecutar lenguaje ensamblador directamente.
C) A la misma frecuencia principal, una CPU de 32 bits funciona dos veces más rápido que una CPU de 16 bits.
D) La CPU fue inventada por primera vez por Intel.
5. Respecto a ASCII, cuál de las siguientes afirmaciones es correcta:
A) El código ASCII es el código único para todas las teclas del teclado.
B) Un código ASCII se puede almacenar utilizando un byte de espacio de memoria.
C) El último esquema de codificación ASCII ampliado incluye codificación de caracteres chinos y otros idiomas europeos.
D) El código ASCII fue desarrollado y promovido por los británicos.
6. ¿Cuál de los siguientes software no es un sistema operativo de computadora:
A) Windows B) Linux C) OS/2 D) WPS
7 Sobre Internet, cuál de las siguientes afirmaciones es correcta:
A) El estándar IPv6 utilizado por la nueva generación de Internet es una actualización y complemento del estándar IPv5.
B) Si el servidor de Internet tiene un nombre de dominio, ya no necesita una dirección IP.
C) El protocolo básico de Internet es el protocolo TCP/IP.
D) Todo el software y los recursos de datos descargables en Internet se pueden utilizar de forma legal y gratuita.
8. ¿Cuál de las siguientes afirmaciones sobre HTML es correcta?
A) HTML realiza la codificación unificada de texto, gráficos, sonido e incluso información de vídeo.
B) HTML significa Lenguaje de marcado de hipertexto.
C) Las animaciones Flash muy utilizadas en Internet están escritas en HTML.
D) HTML también es un lenguaje de programación de alto nivel.
9. Respecto a los lenguajes de programación, ¿cuál de las siguientes afirmaciones es correcta?
A) Un programa con comentarios generalmente se ejecutará más lento que el mismo programa sin comentarios.
B) Los programas desarrollados en lenguajes de alto nivel no se pueden utilizar en sistemas de hardware de bajo nivel (como máquinas herramienta automáticas) ni en teléfonos móviles de gama baja.
C) Los lenguajes de alto nivel son más fáciles de trasplantar entre plataformas que los lenguajes de bajo nivel.
D) Ninguna de las afirmaciones anteriores es correcta.
10. Se sabe que el código ASCII de la letra mayúscula A es 65 (decimal), entonces el código ASCII decimal de la letra J mayúscula es:
A) 71 B. ) 72 C) 73 D ) Ninguno de los anteriores
11. El número octal correspondiente a la fracción decimal 125.125 es
A) 100.1 B) 175.175 C) 175.1 D) 100.175
12. Sí Los seis elementos FEDCBA se insertan en la pila secuencialmente de izquierda a derecha. Durante el proceso de inserción, los elementos se extraerán de la pila. ¿Cuál de las siguientes no puede ser una secuencia pop legal?
A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF
13. La expresión sufijo de la expresión a*(b c)-d es:
A) abcd* - B) abc *d- C) abc* d- D) - *abcd
14. Un árbol binario no vacío que contiene n nodos de rama (nodos que no son hoja), que El número máximo de nodos hoja es:
A) 2n 1 B) 2n-1 C) n-1 D) n 1
15. la complejidad es:
A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)
16 Hay 4000 números enteros. formado supone que los elementos de la tabla se han organizado en orden ascendente y se utiliza una búsqueda binaria para localizar un elemento. Luego se necesitan como máximo varias comparaciones para determinar si el elemento que busca existe:
A) 11 veces B) 12 veces C) 13 veces D) 14 veces
17. Algoritmo de clasificación Estable significa que la posición relativa de los registros con el mismo código clave no cambia antes y después de la clasificación. ¿Cuál de los siguientes algoritmos de clasificación es inestable?
A) Clasificación por burbujas B) Clasificación por inserción C) Combinación. ordenar D) Ordenación rápida
18 Dado un gráfico dirigido con n vértices, si el gráfico está fuertemente conectado (hay caminos desde todos los vértices a otros vértices), entonces, ¿cuántos gráficos dirigidos hay en el gráfico? ? ¿lado?
A) n B) n 1 C) n-1 D) n*(n-1)
19. la competencia de informática Profesores y estudiantes brindan información y recursos relevantes La URL del sitio web oficial de la Olimpiada Nacional de Informática es:
A) / D) /
20. proceso de participación en las competencias de la serie NOI, cuál de los siguientes comportamientos no está estrictamente prohibido:
A) Traer instrumentos de escritura, relojes y diccionarios electrónicos sin funciones de comunicación a la arena.
B) Obtenga puntos en pruebas en línea calculando manualmente las posibles respuestas y generando las respuestas directamente en el programa.
C) Obtener ideas para la resolución de problemas a través de búsquedas en Internet.
D) Inicie múltiples procesos en el programa enviado para mejorar la eficiencia de ejecución del programa.
2. Resolución de problemas (***2 preguntas, 5 puntos por cada espacio en blanco, 10 puntos por ***)
1. Xiao Chen actualmente tiene 2 tareas A y B para completar. Cada tarea tiene varios pasos de la siguiente manera: A=a1-gt; a2-gt; b5. En cualquier momento, Xiao Chen solo puede concentrarse en un paso de una determinada tarea. Pero si lo desea, puede cambiar a otra tarea después de completar el paso actual de la tarea en cuestión, continuando desde el primer paso inacabado de la última tarea. El orden de los pasos en cada tarea no se puede alterar, por ejemplo...a2-gt; b2-gt; a3-gt... es legal, y... a2-gt; ; b2... es ilegal. Xiao Chen comenzó desde el paso b1 de la tarea B. Después de terminar un determinado paso de una determinada tarea, dejó de trabajar y se fue a casa a comer. Cuando regresó, solo recordó que había completado toda la tarea A y se olvidó de todo lo demás. Intente calcular la posible secuencia de pasos de la tarea que Xiao Chen realizó antes de comer.
2． Existe el siguiente programa:
1. a:=1;
2.b:=a;
3. /p>
4. e:=a d;
5. c:=2*d;
6. >7. g:=a*f c;
Ahora necesitamos distribuir este programa a varias (suficientes) PC conectadas por cables para su ejecución en paralelo. Cada PC ejecuta algunas de las declaraciones y puede comunicarse con otras PC a través de cables en cualquier momento para intercambiar algunos resultados intermedios. Se supone que cada PC puede ejecutar una declaración por unidad de tiempo y no se cuenta el tiempo dedicado a la comunicación. Entonces este programa se puede ejecutar en la unidad de tiempo más rápido. Nota: Otras PC solo pueden hacer referencia a cualquier resultado intermedio si se ha obtenido en una determinada PC. Por ejemplo, si las declaraciones 4 y 6 se asignan a dos PC para su ejecución, entonces la declaración 6 debe ejecutarse después de la declaración 4 porque la declaración 6 debe hacer referencia al resultado del cálculo de la declaración 4.
3. Lee el programa y escribe los resultados (***4 preguntas, 8 puntos cada una, total 32 puntos)
1.
var
a, b: entero;
función trabajo(a, b: entero): entero
comienzo
p> p>si un mod b lt;gt; 0 entonces
trabajo ：= trabajo(b, a mod b)
más
trabajo ： = b;
fin
comenzar
leer(a, b
escribir(trabajo(a, b); )) ;
fin.
Entrada: 20 12
Salida: _______
2.
var
a, b: matriz[0..2] de entero
i, j, tmp: entero
para i ：= 0 a 2 hacer
read(b[i]);
para i ：= 0 a 2 hacer
comenzar
a[i] ：= 0
for j ：= 0 a hacer
comenzar
inc(a[i], b[j]);
inc(b[a[i] mod 3], a[j]);
fin;
fin;
tmp := 1
para i := 0 a 2 hacer
comenzar
a[ i] ：= a[i] mod 10;
b[i] ：= b[i] mod 10
tmp ：= tmp * (a[i] b[ i]);
fin;
writeln(tmp);
fin.
Entrada: 2 3 5
Salida:_______
3.
const c = 2009;
var
n, p, s, i, j, t: entero
comenzar<; /p>
leer(n, p);
s:= 0; t:= 1;
para i:= 1 a n hacer
comenzar
t:= t * p mod c;
for j:= 1 to i do
s:= (s t) mod c;
fin;
writeln(s);
end.
Entrada: 11 2
Salida:
4.
var
a: cadena;
n: entero;
procedimiento getnext(var str: cadena);
var
l, i, j, k: entero;
temp: char
comenzar
l := yo
ength(str);
k:= l - 1;
mientras (kgt;=1) y (str[k]gt;str[k 1]) hacen
dec(k);
i ：= k 1;
mientras (ilt; =l) y (str[i]gt; str[k]) hacer
inc(i);
temp:= str[k];
str[k]:= str[i-1];
p>
str[i-1]:= temp;
for i:= l downto k 1 do
for j:= k 1 to i - 1 hacer
si str[j] gt; str[j 1] entonces
comenzar
temp:= str[j];
str [j]:= str[j 1];
str[j 1]:= temp;
fin;
fin;
comenzar
leer(a);
leer(n
mientras n gt; p> comenzar
getnext(a);
dec(n);
finalizar
escribir(a); p>
fin.
Entrada: NOIP 3
Salida:
IV. Mejorar el procedimiento (los primeros 8 espacios en blanco, 3 puntos por cada espacio en blanco, los últimos 2 espacios en blanco, 2 puntos por cada espacio en blanco, ***28 puntos)
1. (La suma máxima de subsegmentos consecutivos) da una matriz (el número de elementos no es más de 100), y los elementos de la matriz son todos enteros negativos, enteros positivos y 0. Busque un subarreglo continuo en la matriz para que la suma de todos los elementos contenidos en este subarreglo sea la más grande. Bajo la premisa de que la suma es la más grande, la submatriz también debe contener la mayor cantidad de elementos y generar la suma máxima y el. continuo El número de elementos en el subarreglo. Por ejemplo, cuando la secuencia numérica es 4, se generan -5, 3, 2, 4, 9 y 3; cuando la secuencia numérica es 1 2 3 -5 0 7 8, 16 y 7.
var
a: matriz[1..100] de entero;
n, i, ans, len, tmp, beg: entero;
p>
comenzar
leer(n);
para i ：= 1 a n hacer
leer(a[i ]);
p>tmp := 0;
ans := 0;
len := 0; = ① ;
for i ：= 1 to n do
comenzar
si tmp a[i] gt entonces
comenzar
ans:= tmp a[i];
len:= i - beg;
fin
else if (② ) y (i - ruego gt ; len) entonces
len:= i - ruego;
si tmp a[i] ③ entonces
comenzar
suplicar: = ④;
tmp: = 0;
finalizar
más
end;
writeln(ans, ' ', len);
end.
2. n*m tablero de ajedrez, ¿cuántos métodos de colocación diferentes existen para requerir que k reyes no se ataquen entre sí? Supongamos que el rey está colocado en la celda (x, y) y el área de ataque del rey es: (x-1, y-1), (x-1, y), (x-1, y 1), (x, y -1), (x, y 1), (x 1, y-1), (x 1, y), (x 1, y 1). Lea tres números n, m, k y genere la respuesta. El problema se resuelve mediante el método de retroceso. Las filas del tablero de ajedrez están numeradas del 0 al n-1 y las columnas del 0 al m-1.
var
n, m, k, ans: entero;
hash: matriz[0..4, 0..4] de entero;
procedimiento trabajo(x, y, tot: entero);
var
i, j: entero;
comenzar
si tot = k entonces
comenzar
inc(ans);
salir;
finalizar;
repetir
mientras hash[x, y] lt; gt; 0 hacer
comenzar
inc(y);
si y = m entonces
comienza
inc(x);
y:= ①;
final;
final p>
si x = n entonces
salir;
final
for i ：= x - 1 a x; 1 hacer
si (i gt; = 0) y (i lt; n) entonces
for j ：= y - 1 to y 1 hacer
si (j gt; = 0) y (j lt； m) entonces
② ；
③ ；
para i ：= x - 1 a x 1 hacer
si (i gt; = 0) y (i lt; n) entonces
for j ：= y - 1 to y 1 hacer
si (j gt; = 0) y (j lt; m) entonces
④;
inc(y);
si y = m entonces
comienzo
inc(x);
y:= 0;
fin;
si x = n luego
salir;
hasta que sea falso;
finalizar
comenzar
leer(n, m). , k);
p>ans:= 0;
fillchar(hash, tamaño de(hash),
;
writeln(ans);
fin.