(Se necesitan dos horas para mejorar el lenguaje del grupo C)
●●●Las respuestas a todas las preguntas del examen deben escribirse en la hoja de respuestas, lo cual no es válido●●
a.Preguntas de opción múltiple (* *10 preguntas, cada pregunta vale 1,5 puntos, **15 puntos. Cada pregunta tiene una y sólo una opción correcta.)
1. , 10101 () = 1100110.
a .1011 B . 1101 c 1010d .
2. es hexadecimal().
A.66b.5a.c.50d. Depende del ordenador concreto.
3. La imagen de la derecha es un árbol binario y su recorrido de preorden es ().
A.ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF
4.
A. Disco duro b. Caché c. Memoria d. Unidad central de procesamiento (CPU)
5.
A. Lista enlazada b. Cola c. Pila d. Tabla hash
6. a ().
A. El espacio de memoria teórico que ocupa el programa cuando se está ejecutando.
B. Espacio de matriz teóricamente ocupado cuando el programa se está ejecutando
C. Espacio de disco duro teóricamente ocupado cuando el programa se está ejecutando
D. archivo fuente del programa Espacio teórico en el disco duro
7. Utilizando la idea de clasificación rápida de divide y vencerás, se puede implementar un programa para encontrar el k-ésimo número grande. Suponiendo que no se considera el peor de los casos, la complejidad de tiempo del algoritmo teóricamente más baja que se puede lograr es ().
A.O(N2)B . O(n log n)C . O(n)d
8. , Para garantizar el flujo fluido de información, () ha desarrollado una serie de estándares que involucran HTML, XML, CSS, etc. , se recomienda a los desarrolladores que lo cumplan.
A. Microsoft b. Association for Computing Machinery (ACM) C. UNESCO d. World Wide Web Consortium (W3C)
9. Uno tras otro, corrieron hacia el patio de recreo uno por uno y se pararon en fila de arriba a abajo según lo pedía la maestra. Cuando cada estudiante llegue al patio de recreo en orden, camine desde el final de la fila hasta el final, busque el primer estudiante que sea más alto que ellos y párese detrás de él. Este método de cola es similar al algoritmo ().
A. Clasificación rápida b. Clasificación por inserción c. Clasificación por burbuja d. Clasificación por fusión
10.1956() fue otorgada a Shockley, John Bardeen y Bratton.
A. Premio Nobel de Física b. ¿Feng? Premio Neumann
Premio C. Turing Premio D. Gartner (Premio Donald E. Knut)
2. Preguntas de opción múltiple indefinidas (* *10 preguntas, cada una de ellas vale 1,5 puntos. * * * 15 puntos. El número de respuestas correctas por cada pregunta no es inferior a 1. No se otorgarán puntos por más de una respuesta).
1. Si la profundidad del nodo raíz es 1, la profundidad de un árbol binario con exactamente 2011 nodos hoja puede ser ().
a . 10 b . 11 c . 12d 2011
2.
A. Ley de conversión: PVQ = QVP
B Ley vinculante: PV(QVR)=(PVQ)VR
C. P
D. Ley acotada: PV1 = 1 (1 representa la verdad lógica).
3. Si un número entero positivo tiene 100 dígitos hexadecimales, entonces puede tener () dígitos binarios.
A.399 B.400 C.401 D.404
4.
Es un lenguaje de programación independiente del hardware específico.
B. Al escribir programas complejos, en comparación con los lenguajes de alto nivel, la cantidad de código es grande y difícil de depurar.
Acceso directo a registros, unidades de almacenamiento y puertos de E/S.
d Con el nacimiento de los lenguajes de alto nivel, estos han sido eliminados por completo y ya no se utilizan.
5. Los textos chinos clásicos existentes deben comprimirse utilizando codificación binaria de Huffman. En aras de la simplicidad, supongamos que este texto chino clásico consta de sólo cuatro caracteres chinos, a saber, Zhi, Hu, Zhe y Ye, que aparecen 700, 600, 300 y 400 veces respectivamente. Entonces, la longitud de codificación de la palabra "también" puede ser ().
A.1
6. La identificación biométrica es una tecnología que utiliza las características biológicas del cuerpo humano para la autenticación de la identidad. En la actualidad, tecnologías como el reconocimiento de huellas dactilares, el reconocimiento de iris y el reconocimiento facial se han utilizado ampliamente en el gobierno, la banca, la seguridad y otros campos. Las siguientes son tecnologías biométricas y sus aplicaciones ().
A. Verificación de la vena del dedo b. Verificación de la marcha C. Verificación de la contraseña del cajero automático d. 8, 4", remove() reducirá 3 pares inversos sin cambiar el orden.
a7 b . 5 c . 3d .
8. La información numérica se divide en números enteros y reales (números de punto flotante). Debido al uso de (), los números reales pueden representar números muy grandes o muy pequeños.
A. Código secuencial b. Código complementario c. Mantisa más larga
9. derecha, a La distancia d [B] del punto B se asigna inicialmente a 8, y habrá () durante el proceso de implementación del algoritmo.
A.3 B.7 C.6 D.5
10. Se denomina red a un conjunto de reglas, estándares o convenciones establecidas para el intercambio de datos en una red informática. protocolo. Entre las siguientes abreviaturas en inglés, () es el protocolo de red.
A.HTTP B.TCP/IP
Tres. Resolución de problemas (***2 preguntas, 5 puntos por cada espacio en blanco, * * * 10 puntos)
1. Un gráfico plano puede ser un gráfico simple no dirigido dibujado en el plano y sus bordes solo pueden cruzarse. en los vértices. Un plano con cuatro vértices tiene al menos seis lados, como se muestra en la figura de la derecha. Entonces, un plano con cinco vértices tiene al menos una arista.
2. Defina una operación de cadena en la que un elemento se pueda mover a cualquier posición a la vez. Por ejemplo, para la cadena "BCA", mueve A antes de B y cambia la cadena "ABC". Cambiar la cadena "DACHEBGIF" a "ABCDEFGHI" requiere al menos _ _ _ _ _ veces.
Cuatro.
Puntuación de escritura del programa de lectura (***4 preguntas, 8 puntos cada una, 32 puntos***)
1.
# include ltiostream gt
# include ltcstring gt
Usar espacio de nombres std
const int TAMAÑO = 100;
int main()
{
int n, I, suma, x, a[TAMAÑO];
CIN gt;
memset(a, 0, tamaño de(a));
p>for(I = 1;i lt= n;i){
CIN gtx;
a[x];
}
I = 0;
suma = 0;
mientras(suma lt; (n/2 1)){
i;
suma = a[I];
}
cout lt lti lt ltendl
Devuelve 0;
}
Entrada:
11
4 5 6 6 4 3 3 2 3 2 1
Salida:
2.
# incluir ltiostream gt
Usar espacio de nombres std
int n;
void f2( int x , int y);
void f1(int x, int y)
{
if(x lt; n)
f2(y, x y);
}
void f2(int x, int y)
{
cout lt ltx lt lt'';
f1(y, x y);
}
int main()
{
CIN gt;
f1(0, 1);
Devuelve 0;
Devuelve 0; /p>
Entrada: 30
Salida: _ _ _ _ _ _ _ _ _ _
3.
# incluir ltiostream gt
Usar espacio de nombres std
const int V = 100;
int n, m, ans, e[V][V]; Booleano visitado [V];
void dfs(int x, int len)
{
int I;
visitado[x ]= verdadero;
if(len gt; ans)
ans = len
for(I = 1; i lt= n; i )
Si ((! Visitado [I]) amp; amp(e[x][i]!=-1) )
dfs(i,len e[x][I]);
visitado[x]= false;
}
int main()
{
int i, j, a, b, c;
CIN gt; gtn gt gtm;
for(I = 1; i lt= n; i)
for(j)
= 1;j lt= m;j)
e[I][j]=-1;
for(I = 1;i lt= m;i) p>
{
CIN gt; gta gt gt gt gtc;
e[a][b]=
e[; b] [a]= c;
}
for(I = 1;ilt= n;i)
visitado[I]= false;
p>ans = 0;
for(I = 1;ilt= n;i)
dfs(i, 0);
cout lt ltans lt ltendl
Devuelve 0;
}
Entrada:
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
Salida: _ _ _ _ _ _ _ _
4.
# include ltiostream gt
# include ltcstring gt
# incluir lt cadena gt
Usar espacio de nombres std
const int TAMAÑO = 10000
const int length = 10; /p>
int n, m, a [tamaño] [longitud];
int h(int u, int v)
{
int ans, yo;
ans = 0;
for(I = 1; i lt= n; i)
if (a[u] [ i]! =a[v][i])
ans;
return ans
}
int main()
{
int suma, I, j;
CIN gt;
memset(a, 0, tamaño de(a)
m = 1;
mientras(1)
{
I = 1; Y ((i lt= n) amp; amp(a[m][i]==1))
i;
if (i gtn)
Romper;
m;
a[m][I]= 1;
for(j = I 1; j lt= n; j )
a[m][j]= a[m-1][j];
}
suma = 0;
for(I = 1;i lt= m;i)
for(j = 1;j lt= m;j)
suma =h(i,j ) ;
cout lt ltsum lt ltendl
Retorno 0;
}
Entrada: 7
Producto salido : _ _ _ _ _ _ _ _
Verbo (abreviatura de verbo) plan perfecto (1 pregunta 2 puntos, 2 preguntas 3 puntos, * * * 28 puntos).
1. (Raíz entera grande) Ingrese un número entero positivo n (1≤n≤10100) e intente calcular la parte entera de su raíz cuadrada usando el método de bisección.
# incluir ltiostream gt
# incluir lt string gt
Usar espacio de nombres std
const int TAMAÑO = 200
La estructura es enorme {
int len, num[SIZE];
};
// donde len representa el número de dígitos en un tamaño grande. entero; num [1] representa un dígito, num [2] representa diez dígitos, y así sucesivamente.
veces enorme (enorme a, enorme b)
//Calcular el producto de enteros grandes A y b.
{
int i, j;
enorme ans
memset(ans.num, 0, sizeof(ans . num) );
for(I = 1;i lt= a.leni)
for(j = 1;j lt= b.lenj)
① =a número[i]*b número[j];
for(I = 1;ilt= a . len b . len;i){
ans . 1] = ans . num[I]/10;
②
}
if(ans . num[a . len b . len] gt; ; 0)
ans .len = a .len b . /p>
Devolver ans
}
hugeint add(hugeint a, hugeint b)
//Calcular la suma de enteros grandes A y b .
{
int I;
enorme ans
memset(ans.num, 0, sizeof(ans . num));
if(a . len gt; MA)
ans . len = a . len;
Otro
ans . b .len;
for(I = 1; I lt= ans.leni ){
ans . núm[I 1] = ans . núm[I]/10;
ans núm[I] = 10;
}
si(ans . num[ans . len 1] gt; 0)
ans . a, enormeint b)
//Calcular la parte entera del promedio de los enteros grandes A y b.
{
int I
enorme ans
ans=add(a,b);
for(I = ans . len;i gt=2;i-){
ans num[I-1] =(④)* 10;
ans . I]/= 2;
}
ans . num[1]/= 2;
if(ans . num[ans . len]= 0 )
ans . // Calcula el resultado de sumar 2 al entero grande a.
{
int I;
enorme ans
ans = a
ans . ] = 2;
I = 1;
Y ((i lt= ans . len) amp; amp(ans . num[I] gt;=10) ){
núm[I 1] = ans .núm[I]/10;
núm[I] = 10; p>
ans . núm[I] = 10;
i p>
}
if(ans . núm[ans . len 1] gt; 0)
⑤;
return ans
}
Fin booleano(Hewitt a, Hewitt b)
/ / Devuelve verdadero si el número entero es gtb, falso en caso contrario.
{
int I;
If(⑥)
Devuelve falso
if(a . len gt; MA)
devuelve verdadero
for(I = a . len; i gt=1; i-){
if(a . num [ I] lt; número [i])
Devuelve falso
if(a . num[I] gt; número [i])
Devuelve verdadero
}
Devuelve falso
}
int main()
{
String s;
int I;
objetivo enorme, izquierda, centro, derecha;
CIN gt;
memset( target.num, 0, sizeof(target . num));
target.len=s.length().
for(I = 1; I lt= target.leni)
objetivo num[I]= s[len-I]-⑦; p>memset(left.num, 0, sizeof(left.num)).
izquierda .len = 1;
izquierda num[1] = 1;
derecha = objetivo
Hacer {
Medio=promedio (izquierda, derecha);
if(over(⑧))
Derecha=medio;
Otros
p>
izquierda=centro;
}mientras(!over(másdos(izquierda),derecha));
for(I = izquierda . len ;i gt=1 ;I-)
cout lt ltleft num[I];
Devuelve 0;
}
. 2. (Descartes (árbol hijo) Para una secuencia dada de enteros positivos por pares, un árbol cartesiano es un árbol binario como este: primero, es un montón mínimo, es decir, el peso de cada nodo, excepto el nodo raíz, es mayor que el peso del nodo padre; en segundo lugar, es un montón mínimo, cuyo recorrido de secuencia intermedia es exactamente una secuencia dada. Por ejemplo, la secuencia 7, 2, 12, 1, 10, 5, 15, 3, la siguiente figura es el árbol cartesiano correspondiente. El número de decimales en la secuencia de entrada n (1 ≤ n
# include ltiostream gt
Usar espacio de nombres std
const int TAMAÑO = 100 5;
const int INFINITY = 1000000;
int n, a[TAMAÑO], maxDeep, num
void solve(int left, int right, int deep)
{
int i, j, min
if(profundo gt; maxDeep){
maxDeep = profundo
num = 1;
}
si no(deep==maxDeep)
①;
min=infinito;
for(I =izquierda;ilt=derecha;i)
if(min gt;a[i]{
min = a[I];
p>
②;
}
if(left lt;j)
③;
if(j lt; Derecha)
④;
}
int main()
{
int I;
int main()
p>
CIN gt;
for(I = 1;ilt= n;i )
CIN gt; gta[I];
profundidad máxima = 0;
Resolver (1, n, 1);
cout lt ltmaxDeep lt' lt ltnum lt ltendl
Return 0;
}
Respuestas de referencia y criterios de puntuación del grupo de mejora NOIP 2011 (lenguaje C)
1. Preguntas de opción múltiple: (65438 0,5 puntos cada una)
1. B 4. B
6. preguntas de elección (* * 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)
1. CD 2. AB 4. BC 6. A 9.
ABC
3. Resolución de problemas: (***2 preguntas, 5 puntos por cada espacio en blanco, * * * 10 puntos)
1,9
2,4< / p>
4. Programa de lectura y resultados de escritura (***4 preguntas, 8 puntos cada una, 32 puntos por ***)
1.3
2.1 2 5 13 34.
3.150
4.57344
5. Mejorar el procedimiento (N° 65438, 2 puntos por cada blanco, N° 2, 3 puntos por cada blanco, * * *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.
① ans.num[i j - 1]
②ans num[I]= ans num[I] mod 10
③No.A[ i] Número B[i]
④ ans.num[i] 2 (o ans.num[i] 1)
⑤ ans.len (o ans.len = ans .len 1)
⑥a .len lt;
7 pies 0 pulgadas (o 48 pulgadas)
⑧ veces (medio, medio), objetivo
2.
① num (o num = num 1)
② j = i
③Resolver (izquierda, j - 1, profundo 1)
④Resolver (j 1, derecha, profundo 1)