Respuesta preliminar de Noip2009
Hoy por la tarde de 2:30 a 4:30 se llevarán a cabo las preliminares de la Olimpiada de Informática.
Como estoy esperando que salga el artículo en lenguaje C y no tengo nada que hacer ahora, analizaré las preguntas de opción múltiple y las partes de solución que se han publicado en lenguaje Pascal, porque el lenguaje C tiene las mismas preguntas. Si está interesado, puede echar un vistazo y discutir sus propias respuestas.
Resolver las preguntas y problemas de opción múltiple del grupo de popularización y del grupo de mejora.
Preguntas del examen preliminar por cada provincia en la XV Olimpiada Nacional de Informática.
(El lenguaje Pascal del grupo popular se completa en dos horas)
●●●Las respuestas a todas las preguntas del examen deben escribirse en la hoja de respuestas, lo cual no es válido●●
1. Preguntas de opción múltiple (***20 preguntas, 65438. Cada pregunta vale 0,5 puntos, * * * 30 puntos. Cada pregunta tiene una y sólo una respuesta correcta).
1. ¿Cuál de las siguientes afirmaciones sobre las máquinas de Turing es correcta?
a) La máquina de Turing es la computadora electrónica más antigua del mundo
b) Debido al uso extensivo de cintas, La máquina de Turing funciona muy lentamente.
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 alemanes durante la Segunda Guerra Mundial.
d) La máquina de Turing es sólo un modelo de cálculo teórico.
Opción de análisis d
a La primera computadora fue la máquina de Turing ENIAC B, que es un modelo de computadora. No tiene velocidad de funcionamiento, y mucho menos operación de cinta.
cLa máquina de Turing es una teoría propuesta por el británico Alan Turing.
Fue el propio Alan Turing quien jugó un papel importante en el descifrado del sistema criptográfico alemán durante la Segunda Guerra Mundial, no la máquina de Turing.
2. Respecto a la memoria del ordenador, ¿cuál de las siguientes afirmaciones es correcta?
a) La memoria de acceso aleatorio (RAM) se refiere a 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 una memoria con un tamaño de 1024*1024 bytes.
c) En rigor, la memoria del ordenador consta de tres partes: memoria principal, caché y registros.
d) Incluso en caso de un corte de energía, los datos en la memoria de uso general se pueden guardar durante más de 2 horas.
Selección de análisis b 1mb = 1024 kb = 1024 * 1024 b.
La RAM en A no está ubicada aleatoriamente, sino que se puede acceder a ella en cualquier momento. El llamado "acceso aleatorio" significa que cuando se lee o escribe una información en la memoria, el tiempo requerido no tiene nada que ver con la ubicación de la información.
La implementación física de cachés y registros en C está integrada en la CPU. Estas dos partes no pertenecen a ninguna de las cinco partes del sistema von Neumann.
No puedes mantener la posición D durante 2 segundos y luego perderla inmediatamente.
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 incluye controladores para dispositivos de entrada y salida de uso común, como teclado, mouse, tarjeta de sonido, tarjeta gráfica e impresora.
C) La BIOS generalmente la desarrollan los fabricantes de sistemas operativos.
D) BIOS puede proporcionar varias funciones de administración de archivos, como duplicación, copia, eliminación y mantenimiento de directorios.
De hecho, bios = sistema básico de entrada y salida. ¡Pero si se trata de software sigue siendo controvertido!
La BIOS en B solo almacena cierta información básica para el inicio del sistema, pero los controladores de estos dispositivos no se almacenan.
La BIOS del elemento C generalmente la producen fabricantes de un solo chip, los más famosos de los cuales son tres en la provincia de Taiwán.
En el ítem D, la BIOS del firmware tiene estas funciones.
4. Las siguientes afirmaciones sobre la CPU son correctas:
A) La CPU se llama unidad central de procesamiento (CPU).
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 Corporation.
Analizar y seleccionar CPU = unidad central de procesamiento
En el ítem B, la CPU solo puede ejecutar instrucciones de máquina, que es código binario.
En el elemento C, el número de dígitos solo puede indicar la longitud de la palabra procesada. Las instrucciones de hardware del sistema son diferentes, por lo que es difícil decir quién es más rápido.
En el punto D, el microprocesador fue inventado por primera vez por Intel, mientras que la CPU se implementó anteriormente mediante tubos de electrones y transistores.
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 en un byte de espacio de almacenamiento.
c) El último esquema de codificación ASCII extendido incluye codificación de caracteres chinos y otros idiomas europeos.
D) El código ASCII fue desarrollado y promovido por los británicos.
El análisis y selección del código B ASCII se guarda en un byte y el código binario de ocho bits es 0 ~ 127.
El elemento A no tiene correspondencia con el teclado.
Elemento C, el código ASCII extendido utiliza dos bytes y el código de caracteres chinos no es el contenido del ASCII extendido.
Artículo D, Código de intercambio de información estándar americano, Estados Unidos
6 El siguiente software no es un sistema operativo de computadora:
A) Windows B) Linux. C) OS/ 2 D) WPS
D WPS = Análisis y selección de sistema de procesamiento de textos (Kingsoft Word Processing System)
b es un sistema Linux de código abierto y C es un Sistema Apple.
7. Respecto a 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 un 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 gratuita y legal.
Opción de análisis C El principal protocolo de Internet es TCP/IP. TCP es el protocolo de transferencia de archivos en la capa de transporte e IP es el protocolo de Internet en la capa de red.
IPv6 en a es una actualización de IPv4.
Debe haber una IP en B y el nombre de dominio es fácil de recordar.
La piratería es ilegal en D.
8. Respecto al lenguaje HTML, ¿cuál de las siguientes afirmaciones es correcta?
A) HTML realiza la codificación unificada de información de texto, gráficos, sonido e incluso vídeo.
B) HTML se llama 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.
B HTML (Hypertext Markup Language), es decir, Hypertext Markup Language, es el lenguaje principal de los documentos web.
El texto, los gráficos, el sonido y el vídeo tienen sus propios códigos, pero no están unificados.
El Flash en C está hecho por el software Flash de Adobe.
D es un lenguaje de marcado, similar al scripting, pero no un lenguaje de programación de alto nivel.
9. ¿Cuál de las siguientes afirmaciones es cierta sobre los lenguajes de programación?
a) Los programas anotados son generalmente más lentos que los programas no anotados.
b) Los programas desarrollados en lenguajes de alto nivel no pueden utilizarse en sistemas de hardware de bajo nivel (como máquinas herramienta de control automático) o teléfonos móviles de gama baja.
c) En comparación con los lenguajes de bajo nivel, los lenguajes de alto nivel son más fáciles de implementar el trasplante multiplataforma.
d) Ninguna de las afirmaciones anteriores es correcta.
Esta opción apareció en la pregunta real antes de elegir C, y analizaba las características de los lenguajes de alto nivel.
Durante el proceso de compilación, los comentarios serán ignorados y no afectarán la ejecución del programa.
b Los lenguajes de alto nivel pueden usar hardware subyacente y compilarse para generar código de destino, que se puede ejecutar en el sistema de hardware.
10. Supongamos que el código ASCII de la letra A mayúscula es 65 (decimal), y el código ASCII decimal de la letra J mayúscula es:
A) 71 B) 72. C) 73 D) arriba Ninguna.
Análisis y selección D 64 9=74
El número octal correspondiente a 11 y la fracción decimal 125.125 es
a) 100.1 B) 175.175 C) 175.1 D )100.175
Opción de análisis c
Dividir la parte entera por 8 para obtener el resto. El resultado se escribe a la inversa multiplicando la parte decimal por 8 para obtener el número entero. en orden positivo.
12. Hay seis elementos FEDCBA de izquierda a derecha. Algunos elementos se extraerán de la pila durante el proceso de apilamiento. ¿Cuál de las siguientes no es una secuencia de pila legal?
a)EDC fab B)deca BF C)CDF EBA D)BCD AEF
Opción de análisis c
Tenga en cuenta que el orden de apilamiento es f ~ a.
Cuando el CD sale de la pila, la parte superior de la pila es E y F no puede salir, por lo que C es ilegal.
13. La expresión sufijo de la expresión a*(b c)-d es
a)ABCD * -B)ABC * D-C)ABC * D-D)- * ABCD
Opción de análisis b
Se utiliza principalmente para probar el recorrido del árbol y es necesario comprender las expresiones de prefijo, infijo y sufijo.
Construya un árbol binario, los operandos son nodos hoja y los operadores son nodos no hoja. Las expresiones infijas se pueden obtener mediante recorrido en orden.
14. Un árbol binario no vacío con n nodos de rama (nodos no hoja) El número máximo de nodos hoja es:
a)2n 1 B)2n-1. C) n-1D)n 1
Opción de análisis d
Probar las propiedades del árbol binario: N0=N2 1, es decir, el número de nodos hoja es 1 mayor que el número de nodos binarios.
15. La complejidad del algoritmo de clasificación rápida en el peor de los casos es:
a)O(log2n)B)O(n)C)O(nlog2n)D)O(N2). )
Se analiza la complejidad temporal del peor caso al seleccionar D. El número seleccionado cada vez es el número más marginal.
16. Otra lista de secuencia que consta de 4000 números enteros. Suponga que los elementos de la lista se han organizado en orden ascendente y utilice la búsqueda binaria para localizar un elemento. El número máximo de comparaciones necesarias para determinar si el elemento que busca está presente:
A) 11 veces B) 12 veces C) 13 veces D) 14 veces.
Opción de análisis b
2^11-1=2047 2^12-1=4095 2047 lt; 4000 lt4095 La altura del árbol viejo es 12.
17. El algoritmo de clasificación es estable, lo que significa que la posición relativa de los registros con el mismo código clave no cambiará antes y después de la clasificación. ¿Cuál de los siguientes algoritmos de clasificación es inestable?
a) Ordenación por burbujas b) Ordenación por inserción c) Ordenación por combinación d) Ordenación rápida
Opción de análisis d
La programación rápida hará que las posiciones izquierda y derecha de los datos a intercambiar.
Si bien otras especies se pueden programar, la estabilidad se puede lograr prestando atención a las condiciones límite.
18. Dado un gráfico dirigido con n vértices, si el gráfico está fuertemente conectado (todos los vértices tienen caminos hacia otros vértices), ¿cuántas aristas dirigidas tiene este gráfico?
a)n B)n 1 C)n-1D)n *(n-1)
Analizar opción a
Formar un nodo donde todos los nodos son El círculo dirigido (anillo) de arriba.
19. El sitio web oficial de la Olimpiada Nacional de Informática de EE. UU. proporciona información y recursos relevantes para profesores y estudiantes que participan en la Olimpiada de Informática.
¿Cuál es la dirección del sitio web oficial de la Olimpiada Nacional de Informática?
A) / D) /
D)/
Analiza y elige C sitio web oficial
Dos. Preguntas de opción múltiple indefinidas (* *10 preguntas, 1,5 puntos por cada pregunta, **15 puntos, el número de respuestas correctas por cada pregunta no es inferior a 1. No se otorgarán puntos por más o menos opciones).
1. ¿Cuál de las siguientes afirmaciones sobre la CPU es correcta?
A) La CPU se denomina unidad central de procesamiento (CPU).
B)La CPU puede ejecutar lenguaje de máquina directamente.
C)La CPU fue inventada por primera vez por Intel Corporation.
d) A la misma frecuencia principal, una CPU de 32 bits funciona dos veces más rápido que una CPU de 16 bits.
Análisis y selección
Parte C, el microprocesador fue inventado por primera vez por Intel, y la CPU se implementó anteriormente mediante tubos de electrones y transistores. En el elemento D, el número de dígitos solo puede indicar la longitud de la palabra procesada. Las instrucciones de hardware del sistema son diferentes, por lo que es difícil decir quién es más rápido.
2. ¿Cuál de las siguientes afirmaciones sobre la memoria de la computadora es correcta?
a) La memoria de acceso aleatorio (RAM) se refiere a la cantidad de memoria asignada al programa cada vez que se ejecuta. Las ubicaciones de la memoria son aleatorias e indefinidas.
b) Las computadoras personales generales solo pueden almacenar/recuperar unidades de almacenamiento específicas al mismo tiempo.
c) En rigor, la memoria del ordenador consta de tres partes: memoria principal, caché y registros.
D) 1 MB de memoria generalmente se refiere a 1024*1024 bytes de memoria.
El análisis y selección de BD son generalmente operaciones seriales en bytes. 1 MB = 1024 KB = 1024 * 1024 b
La RAM en A no está ubicada aleatoriamente, pero se puede acceder a ella en cualquier momento. El llamado "acceso aleatorio" significa que cuando se lee o escribe una información en la memoria, el tiempo requerido no tiene nada que ver con la ubicación de la información.
La implementación física de cachés y registros en C está integrada en la CPU. Estas dos partes no pertenecen a ninguna de las cinco partes del sistema von Neumann.
3.¿Cuáles son las siguientes afirmaciones sobre los sistemas operativos?
Los sistemas operativos multitarea están diseñados para gestionar sistemas informáticos con arquitecturas multinúcleo o multi-CPU.
B. Bajo la gestión del sistema operativo, un programa completo puede almacenarse parcialmente en la memoria mientras se está ejecutando.
C. El sistema de tiempo compartido permite que varios usuarios disfruten de la potencia informática de un host. Para garantizar que cada usuario reciba una respuesta oportuna, generalmente se adopta una estrategia de programación de rotación de tiempo compartido.
D. Para facilitar el desarrollo de aplicaciones de capa superior, los sistemas operativos son gratuitos y de código abierto.
Análisis y selección de BC
Los sistemas multitarea pueden tener una arquitectura de CPU única y las PC comunes son multitarea.
No todos los sistemas operativos D son gratuitos y de código abierto.
4. Respecto a las redes informáticas, ¿cuál de las siguientes afirmaciones es correcta?
a) Los protocolos de red tienen muchas capas, principalmente porque las nuevas tecnologías deben ser compatibles con las implementaciones antiguas.
b) El estándar IPv6 utilizado por la nueva generación de Internet es una actualización y complemento del estándar IPv5.
C)TCP/IP es el conjunto de protocolos básicos de Internet, que incluye TCP, IP y otros protocolos de comunicación entre la red y la capa de transporte.
d) Cada servidor de Internet normalmente necesita utilizar una dirección IP única; de lo contrario, debe registrar un nombre de dominio fijo para indicar su dirección.
Opción de análisis c
La estratificación del protocolo de red no es por compatibilidad, sino que se basa en el modelo de estratificación de la red.
El nuevo IPv6 es una actualización de IPv4.
d Incluso si registras un nombre de dominio, debes tener una dirección IP.
5. ¿Cuál de las siguientes afirmaciones sobre HTML es correcta?
A) A) El nombre completo de HTML es Lenguaje de Marcado de Hipertexto, que implementa texto, gráficos, sonidos e incluso Unificado. codificación de información de vídeo.
B) HTML no solo contiene la descripción de la información del contenido de la página web, sino que también contiene la definición de la información del formato de la página web.
c) Los hipervínculos en páginas web solo pueden apuntar a recursos de red externos. Los enlaces entre páginas web de este sitio web se logran mediante la configuración de etiquetas.
d) Al hacer clic en un hipervínculo en una página web, esencialmente se solicitan recursos de red o servicios de red basados en el localizador uniforme de recursos (URL) implícito en el enlace.
Análisis y Selección
Respuesta: No todos los códigos son uniformes.
Esta página también puede utilizar hipervínculos.
6. Si la matriz de adyacencia de un gráfico ponderado G con tres vértices se almacena como {{0, 1, 1} {1, 0, 1 } }, entonces se supone que los vértices en el el almacenamiento específico está en orden: v1.
a) La gráfica es una gráfica dirigida.
b) La gráfica es fuertemente conexa.
c) La suma de los grados de entrada de todos los vértices del gráfico menos la suma de los grados de salida de todos los vértices es igual a 1.
d) La secuencia de vértices atravesada por el recorrido en profundidad a partir de v1 es la misma que la secuencia de vértices atravesada por el recorrido en anchura.
Análisis y Selección
Puedes dibujar este gráfico dirigido. La matriz es asimétrica cuando se almacena, por lo que es un gráfico dirigido.
La suma de c grados es igual a la caja de grados.
7. En una lista enlazada individualmente circular no vacía con un puntero de cola (la lista de punteros de lista apunta al nodo de cola), cada nodo apunta al siguiente nodo y el puntero está en el siguiente campo. . Supongamos que ya tiene más de dos nodos. ¿Cuál de las siguientes afirmaciones es correcta?
a) Si p apunta a un nuevo nodo a insertar, entonces la secuencia de sentencias para insertar un elemento en el encabezado es:
p ^.next: =clist^. Next; clist^. Next: = p;
b) Si p apunta a un nuevo nodo a insertar, la secuencia de instrucciones para insertar un elemento al final es :
p^. Siguiente: = clistclist^. Siguiente: = p;
c) La secuencia de declaraciones para eliminar el nodo principal es:
p. : = clist^. Continuar hacia abajo; clist^.next: = clist^.next^ Siguiente; eliminación
d) La secuencia de instrucciones para eliminar el nodo de cola es:
p: = clist ;clist:=clist^.Next;Disposición (p);
Análisis y Selección
b debe ser p.next:= clist.next; clist^.Siguiente: = p;
En D, necesitas encontrar el último elemento del puntero de cola en un bucle para eliminarlo.
8. El rango de direcciones de la tabla hash es 0-10 y la función hash es H(K)=K mod 11. El método de detección lineal de dirección abierta se utiliza para manejar conflictos y la secuencia de palabras clave 26, 25, 72, 38, 8, 18, 59 se almacena en la tabla hash. El orden de estos elementos en la tabla hash no está definido. Suponiendo que la tabla hash anterior está vacía, la posible dirección de almacenamiento del elemento 59 en la tabla hash es:
A)5 B)7 C)9 D)10
Hash ABCD Análisis para evitar conflictos en la selección de funciones
Calcule cada valor hash 26 25 72 38 8 18 59
5 4 6 5 8 7 4
Esto hace que el Orden 5: 25, 59 se hace posible...
El orden es 7: 25, 26, 38, 59...
El orden es 9: 25, 26, 38, 18, 59...
Orden de 10:...59
El orden anterior no es único.
9. El algoritmo de clasificación es estable, lo que significa que la posición relativa de los registros con la misma clave no cambiará antes y después de la clasificación. ¿Cuál de los siguientes algoritmos de clasificación es estable?
a) Ordenación por inserción b) Ordenación por base c) Ordenación por fusión d) Ordenación por burbuja
Analizar y seleccionar ABCD
Al programar, siempre y cuando usted controle el límites, se puede lograr una clasificación estable.
10. Al participar en la serie NOI, están estrictamente prohibidos los siguientes comportamientos:
a) Traer herramientas de escritura, relojes y diccionarios electrónicos sin funciones de comunicación al lugar de la competencia.
b) En la prueba en línea, las posibles respuestas se calculan manualmente y las respuestas se envían directamente al programa para obtener puntuaciones.
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.
Análisis y selección de BCD
Esto es una violación de la disciplina. A veces A está bien. El examen aquí es NOI, no NOIP.
Tres. Resolución de problemas (***2 preguntas, 5 puntos por cada espacio en blanco, * * * 10 puntos)
1. La clasificación topológica se refiere a organizar todos los vértices del gráfico acíclico dirigido G en una secuencia lineal, como por ejemplo. que Para cualquier par de vértices U y V en el gráfico, si
Análisis 432
se puede permutar y combinar. Primero determine el orden de 12346 y luego inserte 7. Hay dos posiciones para elegir. Luego inserte 5 y podrá seleccionar 6 posiciones. Finalmente, al colocar 89, considere dos situaciones: si 89 está junto, hay 8 posiciones para elegir; si 89 no está junto, elija dos de las ocho posiciones.
C(2,1)×C(6,1)×[C(8,1) C(8,2)]=2×6×(8 28)=432
2. Hay cuatro denominaciones de monedas en un determinado país: 1, 7, 7 2, 7 3 * *. Si un producto de 10.015 yuanes se va a pagar en efectivo, al menos _ _ _ _ _ monedas deben circular durante la transacción. Se supone que el número de monedas diferentes entre el comprador y el vendedor no está limitado, y el cambio. está permitido.
Análisis 35
El número hexadecimal de 10015 es 41125, que es 4×7 1=29 hojas de 7 con 3 denominaciones, 1 hoja de 7 con 2 denominaciones, 2 hojas con 7 denominaciones, 5 1 valor nominal.
Porque puede ser infinito y cambiante, y requiere una cantidad mínima de circulación. De esta forma, el número A mayor o igual a 4 en hexadecimal se sustituye por el método de 7-a, de manera que se pueda alcanzar el valor mínimo.
Aquí sólo 5, 1, 2 y 5 de 29 son mayores que 4, por lo que utilizamos números grandes y el método de variación de 7-5 para calcular. De esta forma, el número total es 29 1 2 (1 7-5)=35.
Al ser C, no hay programa de análisis y lectura ni partes de mejora. Jaja~~