Federación de Computación de China 2007
1
Preguntas preliminares provinciales de la 13ª Olimpiada Nacional de Informática.
(Dos horas para mejorar el lenguaje del grupo C)
●●●Las respuestas a todas las preguntas del examen deben escribirse en la hoja de respuestas, no válida●●
a. Preguntas de un solo ítem de opción múltiple (* * 10 preguntas, cada pregunta vale 1,5 puntos, ** 15 puntos. Cada pregunta tiene una y sólo una respuesta correcta).
1. Entre los siguientes elementos, () no pertenece a la unidad central de procesamiento.
A. Controlador b. Unidad aritmética c. Registro d. Unidad lógica aritmética (ALU)
2. La estructura es principalmente ().
A. Árbol binario B. Árbol de múltiples ramas c. Tabla hash D. Árbol B e. Entre los siguientes elementos, solo () no es. Unidades comunes de capacidad de almacenamiento informático.
A. Bytes
El significado de 4.4. El código ASCII es ().
A. Código de conversión binario-decimal b. Código estándar americano para el intercambio de información c. Codificación binaria de números
D. Codificación binaria de caracteres de uso común
5. En lenguaje C, el valor de la expresión 23 | 2 ^ 5 es ().
A.23 B. 1 C.18 D.32 E.24
6 En lenguaje C, la expresión condicional correcta para juzgar si A es igual a 0 o B es. igual a 0 o C La fórmula es ().
¡A.! ((a!=0)||(b!=0)||(c!=0))
B.! ((a!= 0) amp; amp(b!= 0) amp; amp(c!=0))
C.! (a = = 0 ampb==0)||(c!=0)
D.(a = 0)amp;(b = 0)amp(c=0)
E.! ((a=0)||(b=0)||(c=0))
7. Hay tres pilares delgados numerados A, B y C en el suelo, con el pilar A comenzando. desde arriba se colocan 10 discos con el mismo diámetro y agujeros en el medio debajo.
Los subnúmeros son 1, 2 y 3. Si el pilar B
el registro de operación en la computadora es "dentro, adentro, afuera, adentro, adentro, afuera". , afuera, adentro, afuera, adentro, afuera, adentro, afuera, afuera, afuera”. Entonces, en el pilar C, desde abajo
El número de platos en la mesa es ().
A.2 4 3 6 5 7 b 2 4 1 2 5 7 c 2 4 3 1 7 6
D.2 4 3 6 7 5 E. 2 1. 4 3 7 5
8. El número octal correspondiente al número decimal 17,5625 es ().
A.21.5625
D.21.71 E. Las primeras cuatro respuestas son incorrectas.
9. El gráfico G de Euler se refiere a un gráfico que puede formar un bucle cerrado. Cada borde del gráfico G aparece exactamente una vez (es decir, un trazo) en este bucle cerrado.
Dibujado) . En la siguiente descripción, () no es necesariamente de Euler.
No hay vértices con grados impares en el gráfico g.
B. Un gráfico que contiene la navegación circular de Euler (la navegación circular de Euler se refiere a un camino cerrado que pasa por cada borde del gráfico exactamente una vez).
C. Un gráfico que contiene una traza cerrada de Euler (una traza de Euler se refiere a una ruta que pasa por cada borde del gráfico exactamente una vez).
Existe un bucle que pasa por cada vértice exactamente una vez.
E. El gráfico en sí es una traza cerrada
10. Un bucle que no puede ser terminado por su propio control se llama "bucle infinito".
Por ejemplo, en un programa en lenguaje C, la declaración " while(1)"
printf(" * ");" es un bucle infinito, que imprimirá signos * infinitamente durante el tiempo de ejecución. Lo siguiente sobre infinito En cuanto a los bucles, solo ()
es correcto
A. No existe ningún algoritmo que pueda determinar si algún programa y los datos de entrada correspondientes tendrán un bucle infinito. >
Ningún sistema de compilación realiza comprobaciones de bucles infinitos.
Algunos sistemas de compilación pueden detectar bucles infinitos.
C. entonces también debería poder verificar si hay bucles infinitos.
D. Los bucles infinitos son similares a los "puntos muertos" en los que se pueden detectar múltiples procesos, por lo que también se pueden detectar bucles infinitos.
Acerca de
E. Para un bucle infinito, solo podemos esperar hasta que ocurra y luego tratarlo en el sitio. No existe un método más proactivo. preguntas de opción múltiple (* * 10 preguntas, 1,5 puntos por cada pregunta, * * * 15 puntos. El número de respuestas correctas para cada pregunta es mayor o igual a 1. Hay opciones múltiples
o no puntos por menos opciones)
11. Supongamos que A = B = verdadero, C = D = falso, el valor de la siguiente expresión de operación lógica es verdadero (). (?A∧B. )∨(C∧D∨A) B? (((A∧B)∨C)∧D)
C.A∧(B∨C∨D)∨D .( A∧(D∨C ))∧B
12. La proposición "P→Q" se puede leer como P implica Q, donde P y Q son dos proposiciones independientes sólo cuando la proposición p es verdadera y la proposición q no es cierto.
El valor de la proposición "P→Q" es falso y las demás situaciones son verdaderas. La relación lógica equivalente con la proposición "P→Q" es
A.? Q B. P∧C? (P∨Q) D? (?Q∧P) 13. (2070) 16 (34) El resultado de 8 es (). 10
C.(100000000110)2d .(20214)8
14 Se sabe que el primer recorrido de raíz de un árbol binario con 7 nodos es 1 2 4 5 6 3. 7 (el número es el número del nodo, lo mismo a continuación), el segundo recorrido de raíz es 4 6 5 2 7 3 1, entonces el posible recorrido de raíz del árbol binario es (p>
A.4). 2 6 5 1 7 3 B. 4 2 5 6 1 3 7
C.4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3
p>15 Los datos redundantes se refieren a datos que se pueden derivar de otros datos, por ejemplo, las matemáticas, el chino y el inglés de los estudiantes se han almacenado en la base de datos.
Si todavía se almacenan tres materias. tema pueden considerarse datos redundantes. Los datos redundantes a menudo conducen a inconsistencia en los datos.
Por ejemplo, si se ingresan los cuatro datos anteriores y la puntuación total no es igual a la suma de los tres temas debido a errores operativos, se producirán conflictos. Abajo/abajo/abajo
Acerca de los datos redundantes, el correcto es ().
A. Todos los datos redundantes deben eliminarse de la base de datos.
B. En comparación con los sistemas de procesamiento de datos escritos en lenguajes de alto nivel, los sistemas escritos en bases de datos relacionales pueden eliminar más fácilmente los datos redundantes.
C. Para mejorar la eficiencia de las consultas, algunos datos redundantes se pueden conservar adecuadamente en la base de datos, pero se deben realizar comprobaciones de compatibilidad durante la actualización.
D. Las pruebas de compatibilidad reducirán la eficiencia, por lo que se pueden ignorar los datos redundantes en la base de datos.
16. Entre los siguientes software, la configuración regional recomendada para la competencia NOIP (revancha) es ().
A.gcc B. g
C.Turbo C D. free pascal
17 Los que aún pueden guardar datos después de un corte de energía son () .
A. Disco duro B. rom C. Memoria de vídeo D. RAM
18.
R. El lenguaje de alto nivel es más avanzado que el lenguaje ensamblador porque su programa se ejecuta de manera más eficiente.
B. Con la aparición de lenguajes de alto nivel como Pascal y C, el lenguaje de máquina y el lenguaje ensamblador se han retirado del escenario de la historia.
Los programas en lenguaje C de alto nivel son más fáciles de migrar de una computadora a otra que los programas en lenguaje ensamblador.
D.c es un lenguaje informático de alto nivel orientado a procesos.
19. Entre las siguientes afirmaciones sobre la complejidad del algoritmo, la correcta es ().
La complejidad temporal de un algoritmo se refiere al tiempo de ejecución cuando se implementa en una computadora.
bLa complejidad temporal de un algoritmo se refiere a la función entre el número de operaciones y el tamaño del problema para una o varias operaciones principales del algoritmo.
Relaciones numéricas
C. Si un problema es NPC, significa que no existe ningún algoritmo con complejidad de tiempo polinomial a la hora de resolver el problema.
Pero esto no ha sido ni confirmado ni desmentido teóricamente.
D. Si un problema es de nivel NP, entonces su conclusión es la misma que c.
20. En los últimos 20 años, muchos expertos en informática han defendido vigorosamente los algoritmos recursivos como una herramienta poderosa para resolver problemas más complejos. Mi
columna sobre algoritmos recursivos, la correcta es ().
A.FORTRAN77 es un lenguaje informático estándar de alto nivel formado alrededor de 1977. Prohíbe la recursividad en los programas. Una de las razones es este lado.
Los métodos pueden ocupar más espacio en la memoria.
B. En comparación con los algoritmos no recursivos, los algoritmos recursivos generalmente se ejecutan más rápido para resolver el mismo problema.
Para problemas más complejos, suele ser más fácil programar de forma recursiva que no recursiva.
d Para la función matemática estándar definida sin(x), la declaración "y = sin(sin(x));" en la aplicación es una confirmación.
Retirar
3. Resolución de problemas (***2 preguntas, 5 puntos cada una, * * * 10 puntos)
1. Dadas n bolas numeradas, los números son 1 y 2. ,. ..,n. No se permite colocar estas N bolas en R cajas idénticas.
Si hay cajas vacías, el número total de diferentes métodos de colocación se registra como S(n, r). , S(4,2)=7, los siete métodos de ubicación diferentes son los siguientes
{(1), (234)}, {(2), (134)}, {(3). , (124)}, {(4), (123)}, {(12), (34)}, {(13), (24)},
{(14), (23 )}. Cuando n = 7, r = 4, s (7, 4) = _ _ _ _ _ _
2, n personas forman un círculo en el patio de recreo, de 1 a n números en el sentido de las agujas del reloj. , y luego, comenzando por la primera persona, todos los demás le piden a la siguiente que abandone el patio de recreo. Obviamente, después de la primera ronda, todas las personas pares abandonan el patio de recreo, hazlo directamente.
Hay. solo queda una persona en el patio de recreo. Registre el número de esta persona como J(N), como J(5)=3, J(10)=5, y así sucesivamente. )=______________ .
(Pista: Analiza N=2m r, donde 0 ≤ r
Cuatro.
Puntajes de escritura del programa de lectura (***4 preguntas, 8 puntos cada una, 32 puntos***)
1.# include ltstdio.h gt
int main()
{int i, p[5], q[5], x, y = 20
for(I = 0; i lt=4; i)
scanf("d ", ampp[I]);
q[0]=(p[0] p[1]) (p[2] p[3] p[4])/ 7 ;
q[1]= p[0] p[1]/((p[2] p[3])/p[4]);
q[ 2 ]= p[0]* p[1]/p[2];
q[3]= q[0]* q[1];
q[4 ] = q[1] q[2] q[3];
x =(q[0] q[4] 2)-p[(q[3] 3) 4];
p>si(x gt; 10)
y =(q[1]* 100-q[3])/(p[p[4] 3]* 5);
p>Otros
y = 20 (q[2]* 100-q[3])/(p[p[4] 3]* 5);
printf("d, d\n ", x, y);
Devuelve 0
}
/*Nota: En este ejemplo , proporcione Ciertos datos de entrada pueden evitar que el denominador sea 0 o que el subíndice del elemento de la matriz se salga de los límites.
*/
Entrada: 6 6 5 5 3
Salida: _ _ _ _ _ _ _ _ _ _
2.# incluir ltstdio.h gt
diversión nula(int *a, int *b)
{ int * k
k = a = b = k; /p>
}
Principal( )
{int a=3, b=6, * x = ampa, * y = ampb
printf("No.1: d, d ", a, b
Diversión (amp one, ampb
printf("Nº 2: d, d\n ", a, b
}
Salida: _ _ _ _ _ _ _ _ _ _); _ _ _ _ _ _ _ _ _ _
3.#Contiene "math.h"
#Contiene "stdio.h"
Principal()
{ int a 1[51]= { 0 };
int i, j, t, t2, n = 50
for(I = 2 ; i lt= sqrt(n); i )
if(a1[i]==0)
{ T2 = n/I;
para ( j = 2;j lt= t2j )a 1[I * j]= 1;
}
t = 0;
for(I = 2 ;ilt= n;i)
if(a1[i]==0)
{printf("4d ",I);t ;
if(t 10 == 0)printf(" \ n ");
}
printf(" \ n "); p>
Salida: _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
__________________________________________
4.#Contiene "stdio.h"
char ch[]={'q','A','S','O','R','T' ,'E','X','A','M','P','L','E'};
int n = 12;
vacío shift(int k, int n)
{ char v;
int j;
v = ch[k]; >
mientras(j lt;=n)
{ if((j lt;n) amp; amp(ch[j] lt;ch[j 1]))j;
If (v ltch[j])
{ ch[j/2]= ch[j] * = 2;}
Otros
Retorno;
ch[j/2]= v;
}
}
Hpsrt no válido (no válido)
{ int k;
char tmp
for(k = n/2; k gt0; k -) shift (k, n); un montón*/
pri
ntf(" no . 1: ");
for(k = 1; k lt= n; k )putchar(ch[k]); ');
for(k = n;k gt0;k -)
{ tmp = ch[1]; ]= tmp;
shift(1,k-1);
}
}
main()
{ int k;
HP SRT();
printf("Nº 2: "); lt = n;k)putchar(ch[k]);
putchar(' \ n ');
}
Salida: _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_______________________________________________
Verbo (abreviatura de verbo) Programa de mejora (2 puntos por los primeros 5 espacios, 3 puntos por los últimos 6 espacios, *** 28 puntos).
1. (Código Gray)
El código Gray es el código binario de números decimales. El orden de codificación no coincide con el tamaño del número decimal correspondiente. Su característica es que existe sólo un bit binario de diferencia entre dos números decimales adyacentes y dos códigos Gray correspondientes. Además, sólo hay un dígito binario entre las cantidades máxima y mínima. Tomando como ejemplo un número binario de 4 dígitos, la codificación es la siguiente:
Código Gray digital decimal
0 0000 8 1100
1 0001 9 1101
2 0011 10 1111
3 0010 11 1110
4 0110 12 1010
5 0111 13 1011
6 0101 14 1001
7 0100 15 1000
Si piensas en cada bit binario como un interruptor, un número se convertirá en otro número adyacente, simplemente cambia un interruptor. Por lo tanto,
el código Gray se usa ampliamente en el procesamiento de señales, la conversión de digital a analógico y otros campos.
La tarea del siguiente programa es ingresar el número n (n
Emitir el código Gray correspondiente a m (***n bits, matriz gr[]).
Para completar el programa, debes analizar cuidadosamente las reglas de la tabla anterior, especialmente el número decimal que fija un determinado bit de código Gray de 0 a 1, o de 1 a 0.
# incluir ltstdio.h gt
main()
{intbound=1, m, n, I, j, b, p, gr[ 15];
printf("entrada n, m \ n ");
scanf("dd ", ampn amp; m); I = 1; i lt= n; i )bound =①;
If (m lt0 | | m gt=binding)
{printf("¡Error de datos!\n "
②;
}
b = 1;
para(I = 1; I lt= n; i )
{ p = 0; b = b * 2;
for(③; j lt= m; j )
Si (④)
p = 1-p;
gr[I] = p;
}
para(I = n; ⑤ )
printf("1d", gr[I]);/*El número 1 aparece en "1d", no la letra l */
printf("\n");< / p>
}
2. (Emisión postal continua) Un determinado país ha emitido N sellos de diferentes denominaciones y estipula que cada letra puede tener un máximo de M sellos. Aquí,
Bajo ciertas restricciones, para enviar por correo todos los costos de envío del conjunto entero continuo {1, 2, 3,..., valor máximo} y maximizar el valor máximo.
¿Cómo diseñar el valor nominal de cada sello? Por ejemplo, cuando n=5, m=4, el valor nominal se diseña como {1, 3, 11, 15, 32}, lo que puede hacer que Maxvalue alcance el valor máximo de 70 (en otras palabras, de 1 a 4 sellos de estas denominaciones pueden representar todos los franqueos que no excedan 70, pero ninguno.
El método indica que el franqueo es 71, pero si de 1 a 4 sellos de otras denominaciones pueden representar todos los franqueos que no excedan K., entonces k≤. 70) debe estar presente.
El siguiente es un programa que utiliza retroceso recursivo para resolver el problema del envío continuo. La matriz x[1:n] representa n denominaciones de sellos diferentes y especifica cada elemento.
Los números primos aumentan estrictamente por subíndice. La matriz bestx[1:n] almacena el valor del sello que maximiza el valor máximo (solución óptima).
La matriz y[maxl] se utiliza para registrar el número mínimo de sellos requeridos para varias tarifas postales que se pueden publicar con el valor nominal del sello seleccionado actualmente x[1:i]. Por favor, publique el programa
El prefacio está completo.
# incluir ltstdio.h gt
#define NN 20
#define maxint 30000
#define maxl 500 /*franqueo máximo */
int n, m, bestx[NN], x[NN], y[maxl], valor máximo = 0;
Resultado no válido()
{Resultado de salida: valor máximo y solución óptima: bestx[1:n](omitido)
}
anular el retroceso (int i, int r)
{ int j, k, z[maxl];
for(j = 0; j lt= ①; j)
if(y[j] lt; m )
for(k = 1; k lt= m-y[j]; k )
if(y[j] k lt;=y[ ② ])
y[③]= y[j] k;
mientras(y[r] lt; maxint)r;
if (i gtn)
{ if(r-1 gt; valor máximo)
{ valor máximo =④;
for(j = 1; j lt= n; j)
mejorx[j]= x[j];
}
Retorno;
}
for(k = 0 ; k ltmaxlk )
z[k]= y[k];
for(j =⑤;j lt= r;j )
{ x [ I]= j;
⑥;
for(k = 0; k ltmaxlk)
y[k]= z[k];
p>}
}
void main()
{ int j;
printf("entrada n, m :\ n ");
scanf("dd ", ampn amp; m);
for(j = 1; j ltmaxlj )
y [ j]= maxint;
y[0]= 0; x[0]= 0; x[1]= 1;
Retroceder (2, 1);
Resultado();
}
Respuesta:
1. Preguntas de opción múltiple: (65438 0,5 puntos cada una)
1.D 2. E3. D4. B5. A
6.B 7. D8. B9. D10. A
2. Preguntas indefinidas de opción múltiple (* * 10 preguntas, 1,5 puntos por cada pregunta, * * * 15 puntos. El número de respuestas correctas para cada pregunta es mayor o igual a 1. No Se otorgarán puntos por más o menos opciones).
11.ABC 12. 13 d.C. ABD14. ABD15. antes de Cristo
16.ABD 17. AB 18. CD 19. 20 a.C.
Corriente alterna (corriente alterna)
3. Resolución de problemas: (***2 preguntas, 5 puntos cada una, * * * 10 puntos)
1.350
2.289
IV. Programa de lectura y resultados de escritura (***4 preguntas, 8 puntos cada una, 32 puntos por ***)
1 129, 43
N° 2 1: 3, N° 6 2: 3, 6
3 2 3 5 7 11 13 17 19 23 29
31 37 41 43 47
4 No. 1: xtorseample
Segundo lugar: AAEELMOPRSTX
Programa de mejora de verbo (abreviatura de verbo) (2 puntos por los primeros 5 espacios, 3 puntos por los últimos 6 espacios, * * *28 puntos).
(Nota: Puede haber algunos métodos equivalentes para completar los espacios en blanco en el siguiente proceso. Cada provincia puede pedir a sus propios expertos que revisen en la computadora y no tiene que informar a Science y Comisión de Tecnología para su revisión.)
1 ①bound*2
②Return
③ j=0
④ (j b-( b / 2))=0
⑤ lt;= 1
2 ① x[i-2]*(m-1)
② j x[ i-1]*k
③ j x[i-1]*k (igual que 2)
④ r-1
⑤ x[i- 1] 1
⑥Retroceso (i 1, r)