Respuestas a las preguntas del examen preliminar provincial de la XVI Olimpiada Nacional de Informática.

La respuesta es la siguiente,

NOIP2010 (Pascal Improvement Group)

1. Preguntas de opción múltiple

1,10 números decimales equivalen a 16 números decimales A1.2 es () a.

2. Un byte se compone de () binario. A.8B.16 C.32 D. Todo lo anterior es posible.

3. El valor de la siguiente expresión lógica siempre es verdadero ().

A.p∨(┓p∧q)∨(┓p∧┓q)b.q∨(┓p∧q)∨(p∧┓q)

C.p∨q∨( p∧┓q)∨(┓p∧q)d.p∨┓q∨(p∧┓q)∨(┓p∧┓q)

La extensión predeterminada de los archivos ejecutables en 4.4. Linux es (). A.exeb.com.dll.d. Ninguno de los anteriores.

5. Si la ecuación 7*7=41 se cumple en un determinado sistema, entonces la ecuación 12*12=() también se cumple en este sistema.

A.100b. 144c. 164d. 196

6. Fue () quien propuso el principio de funcionamiento del "programa almacenado" de computadora.

¿A. Shannon B. Gordon. ¿Moore Charles? ¿Babic von? Neumann

7. El valor de la expresión del prefijo "+3 * 2+5 12" es (). Respuesta 23B. 25 C. 37D. 65

8. La velocidad de acceso a la memoria principal es mucho más lenta que la velocidad de trabajo de la unidad central de procesamiento (CPU), lo que afecta la eficiencia de esta última. Según el principio de localidad, las unidades de memoria a las que accede la CPU suelen estar en un área pequeña y continua. Por lo tanto, para mejorar la eficiencia de ejecución de todo el sistema, se introdujo () en la CPU. a. Registro b. Caché c. Memoria flash d. Memoria externa

9. El esquema de almacenamiento secuencial de un árbol binario completo se refiere a almacenar los nodos del árbol binario completo en una estructura secuencial. y de izquierda a derecha en una matriz. Suponiendo que el nodo raíz está almacenado en la posición 1 de la matriz, el nodo padre del nodo K, si existe, debe almacenarse en la posición () de la matriz. A.2kb.2k+1 C.K./2, vuelta D. (k+1)/2.

10. La más antigua de las siguientes competiciones es (). Opaco. APIO

2. Preguntas de opción múltiple indefinidas

1. Los elementos R1, R2, R3, R4 y R5 se apilan en el orden de R1, R2, R3, R4 y R5. Si el primero es R3, entonces el quinto podría ser (). A.R1 B.R2 C.R4 D.R5

2. El lenguaje Pascal, el lenguaje C y el lenguaje C++ pertenecen a (). a. Lenguaje de alto nivel b. Lenguaje natural c. Lenguaje interpretado d. La clasificación in situ se refiere a una clasificación en la que el tamaño del espacio auxiliar (excepto para almacenar los elementos) ordenarse) no tiene nada que ver con el tamaño del algoritmo de datos. Las siguientes son clasificaciones in situ (). a. Ordenación por burbuja b. Ordenación por inserción c. Ordenación por base d. En la representación en complemento de números enteros, la siguiente afirmación es correcta ().

A. Sólo el bit de codificación más alto de un entero negativo es 1B. Una vez determinado el número de bits de codificación, los valores absolutos del número entero más pequeño y más grande que se pueden representar son los mismo.

C. El número entero 0 tiene un solo código único. d. Al sumar dos números representados por números en complemento a dos, si se produce un acarreo en el bit más significativo, significa que la operación se desborda.

5. Si la secuencia transversal de preorden del árbol binario es ABCDEFG y la secuencia transversal de postorden es CBFEGDA, entonces el número de nodos en el subárbol izquierdo del nodo raíz puede ser (). A0 b . 2 c . 4d . 6

6 En la siguiente declaración HTML, el hipervínculo al sitio web oficial de NOI se puede generar correctamente ().

A.& lta URL = " h t t p://w w w w n o I . c n " >Bienvenido al sitio web de NOI

B.& lta href = " h t t p://w w w n o I . c n " >Bienvenido al sitio web de NOI

C.& lta & gth t t p://w w w w n o I . c n </a & gt;

D.& lta nombre " h t t p ://w w w n o I c n " >Bienvenido al sitio web de NOI

7. Con respecto a la clasificación topológica, la siguiente afirmación es correcta ().

A. Todos los gráficos dirigidos conectados pueden lograr una clasificación topológica.

bPara el mismo gráfico, la estructura de orden topológico es única.

C. En la clasificación topológica, los nodos con grado 0 siempre se clasifican antes que los nodos con grado mayor que 0.

D. El primer nodo en la secuencia de resultados de clasificación topológica debe ser un punto con un grado de entrada mayor que 0.

8. La normal de un plano se refiere a la recta perpendicular al plano. La recta normal del avión que pasa por los puntos (1, 1, 1), (0, 3, 0), (2, 0, 0) es ().

A. Recta que pasa por los puntos (1, 1, 1) y (2, 3, 3) b. /p >

C. La recta que pasa por los puntos (0, 3, 0) y (-3, 1, 1) d. La recta que pasa por los puntos (2, 0, 0) y (5). , 2, 1)

9. Hay dos campos de puntero llink y rlink en la lista vinculada, que apuntan al predecesor y sucesor del nodo respectivamente. Supongamos que p apunta a un nodo en la lista vinculada y que sus nodos izquierdo y derecho no están vacíos. Ahora es necesario eliminar el nodo p, entonces el correcto en la siguiente secuencia de instrucciones es ().

a .p->rlink->llink = p->rlink

p->;llink->rlink = p->llink eliminar p;

b->llink->rlink = p->rlink

p->;rlink->llink = p ->llink eliminar p;

C.p->rlink->llink = p->llink

p->rlink->llink-& gt;rlink = p-& gt;rlink eliminar p;

D.p->llink-& gt;rlink = p-& gt;rlink

p->llink-& gt;rlink-& gt;link = p->llink eliminar p;

10. Los hechos ocurridos este año (2010) incluyen ().

A. Vinay Deolalikar, investigador de HP Labs, afirma haber demostrado que P≠NP.

B. Intel adquirió la empresa de software de seguridad informática McAfee.

C. Apple lanza el teléfono móvil iPhone 4 d. Microsoft lanza el sistema operativo Windows 7.

En tercer lugar, resuelva el problema

1. La codificación LZW es una codificación de diccionario adaptativa. En el proceso de codificación, al principio solo hay un diccionario de codificación de elementos estructurales básicos. Si se encuentra una nueva entrada durante la codificación, la entrada y el nuevo código se agregan al diccionario y se utilizan para codificar la información posterior.

Por ejemplo, considere una cadena de información a codificar: "xyx yy yy xyx". El diccionario inicial tiene sólo tres entradas, la primera es X, el código es 1; la segunda es y, el código es 2; la tercera es un espacio, el código es 3, por lo tanto, el código de la cadena "xyx" es 1-2; -1 (donde - es el separador de código), seguido de un espacio es 1-2-1-3.

Pero debido a que hay un espacio, sabemos que el "xyx" anterior es una palabra, y debido a que esta palabra no está en el diccionario, podemos agregar de forma adaptativa esta entrada al diccionario, codificarla como 4 y luego procesar la información posterior. según el nuevo código del diccionario, etc. Entonces, el código final es: 1-2-1-3-2-2-3-5-3-4.

Podemos ver que la información está comprimida. La información comprimida se transmite al receptor, y el receptor puede completar la recuperación completa de la secuencia basándose en el diccionario básico. El proceso de decodificación es la operación inversa del proceso de codificación. Ahora se sabe que las tres entradas del diccionario inicial son las mencionadas anteriormente, y la información codificada recibida por el receptor es 2-2-1-2-3-1-3-4-3-1-2-1- 3-5-3-6.

2. El grafo no dirigido G tiene siete vértices. Si no hay un anillo simple que consta de aristas impares, tiene como máximo _ _ _ _ _ _ _ _ _ aristas.

3. Recuerde que T es una cola, que está vacía al principio. Los n enteros positivos existentes cuyo número total no excede 32 se colocan en la cola en secuencia. Si no importa cuáles sean estos números, podemos encontrar una manera de quitar la cola para que la suma de los números en la cola T en un momento determinado sea exactamente 9, entonces el valor mínimo de n es _ _ _ _ _ _ _ _.

Cuarto, el programa de lectura escribe los resultados

1.

Constante

tamaño = 10;

Definir variables

I, j, cnt, n, m: entero;

Datos: entero de matriz [1..tamaño]

Inicio p>

readln(n, m);

Para i := 1 an do

read(data[I]);

Para i := 1 a n hacer

Inicio

CNT:= 0;

Para j := 1 a n hacer

si (datos[I]<datos[j]) o ((datos[j] = datos[i]) AND (j<I))

Entonces Inc(CNT);

p >

Si cnt = m

Entonces writeln(data[I]);

Fin;

Fin.

Entrada

5 2

96 -8 0 16 87

Salida:_ _ _ _ _ _ _ _ _

p>

2.

Constante

tamaño = 100;

Definir variables

na, nb , I, j, k: entero;

a, b: entero del array [1..size];

Inicio

readln(na);

For i := 1 to na do

Leer (a[I]); i := 1 a nb do

Leer como (b[I]);

I:= 1;

j:= 1;

mientras (i & lt= na) y (j & lt= nb) hacen

Iniciar

Si a[I]<= b[j] entonces

Inicio

Escribir (a[i], ' ');

inc(uno); p>En caso contrario empezar

Escribir(b[j],' ');

Inc(j);

Fin;

Fin;

p>

Si i<=entonces na

For k := i to na do

Escribe (a[k], ' ' );

Si j & lt entonces = nb

Para k := j a nb hacer

Escribe (b[k], ' ');

Finalizar.

Inversión

Cinco

1 3 5 7 9

Cuatro

2 6 10 14

Salida:_ _ _ _ _ _ _ _ _

3.

Constante

núm = 5;

Definir variables

n: entero;

Función r(n: entero): entero;

Definir variables

I: entero;

Inicio

Si n & lt= num entonces

Inicio

r:= n;

Salir ;

Fin;

Para i :=1 a num do

Si r(n-I)& lt;

r:= I;

Salir

Fin

r:=-1; Fin;

Inicio

readln(n);

writeln(r(n));

Fin.

Entrada 16

Salida:_ _ _ _ _ _ _ _ _

4.

Constante

tamaño = 100;

Definir variables

n, m, x, y, I: entero

r: matriz[1..tamaño] Entero;

Mapa: valor booleano de la matriz [1..tamaño,1..tamaño];

Encontrado: booleano;

Función exitosa: tipo booleano;

Definir variables

I: entero

Inicio

Para i:=1 to n do

Si no está mapeando [r[i]][r[i mod n + 1]]

Entonces comencemos

Éxito:=false;

Salir ;

Fin;

Éxito:=Verdadero;

Fin;

Intercambio de proceso (var a, b: entero); /p>

Definir variables

t:integer;

Inicio

t:= a;

a:= b ;

b:= t;

Fin;

procedimiento permanente (izquierda, derecha: entero); p>

I: entero;

Iniciar

Si lo encuentra

Luego salir;

Si sale& gtCorrecto

Entonces comencemos

Si tiene éxito

Entonces comencemos

Para i := 1 to n do

writeln(r [i], ' ');

Encontrado:=Verdadero

Fin

Salir

Fin; >

Para i:= hazlo de izquierda a derecha

Inicio

swap(r[izquierda], r[I]);

Perm( izquierda+1,derecha);

intercambiar(r[izquierda], r[I]);

Fin;

Fin;

p>

Inicio

readln(n, m);

fillchar(map, sizeof(map), false

Para i; := 1 a m hacer

Inicio

readln(x, y);

map[x][y]:= true;

map[y][x]:= true;

Fin;

Para i := 1 to n do

r[I]: = I ;

Encontrado:=false;

perm(1,n);

Si no se encuentra

entonces writeln(' Ninguna resolución');

Fin.

Entrada:

9 12

1 2

2 3

3 4

4 5

5 6

6 1

1 7

2 7

3 8

4 8

5 9

6 9

Salida:_ _ _ _ _ _ _ _ _

Procedimiento de mejora del verbo (abreviatura de verbo)

1. (Cruzar el río) Una noche oscura de un mes, un grupo de personas se encontraba en la margen derecha del río, intentando caminar hacia la margen izquierda. del río a través del único puente de madera. En la oscuridad, tuvieron que utilizar lámparas para iluminarse mientras cruzaban el puente. Lamentablemente solo tienen una luz. Además, el puente de madera puede soportar el paso de hasta dos personas al mismo tiempo, de lo contrario colapsará. Todos cruzaron solos el puente de una sola tabla. Diferentes personas pueden requerir diferentes cantidades de tiempo. Dos personas cruzan juntas un puente de una sola tabla. Debido a que solo hay una luz, el tiempo que tarda es el tiempo que le toma a la persona más lenta cruzar el puente sola. Ahora ingresa n (2

Por ejemplo, hay tres personas, A, B, C, y el tiempo que les toma cruzar el puente solos es 1,24, entonces el tiempo mínimo total requerido es 7.

El método específico es: A y B cruzan el puente juntos hacia la orilla izquierda del río, A regresa solo a la orilla derecha del río y trae de vuelta la luz, y luego A y C cruzan el puente juntos hacia la orilla izquierda del río. el río El tiempo total es 2+65, 438+4.

Constante

TAMAÑO = 100;

Infinito = 10000;

Izquierda = Verdadero

Derecha = False;

De izquierda a derecha = verdadero;

DERECHA _ A _ IZQUIERDA = falso

Definir variables

n, I: entero ;

Tiempo: número entero de la matriz [1..Tamaño];

Posición: valor booleano de la matriz [1..Tamaño];

Función max( a, b: entero): entero;

Inicio

Si a & gtb entonces

Máximo:= a

Otro p>

max:= b;

Fin;

Función go(etapa: booleana): entero;

Definir variables

I, j, num, tmp, ans: integer;

Inicio

if (etapa = de derecha a izquierda)

Entonces comencemos

p>

num:= 0;

ans:= 0;

for i := 1 to n do

si pos [i] = Correcto, entonces

Iniciar

inc(número);

Si tiempo[I]& gt; >ans:= hora[I];

Fin;

Si __________, entonces

Inicio

ir:= ans;

Salir;

Fin;

ans := infinito;

para i := 1 a n–1 hacer

Si pos[i] = DERECHA, entonces

Para j := i+1 to n do

Si pos[j] = DERECHA, entonces

Inicio

pos[I]:= IZQUIERDA;

pos[j] := IZQUIERDA

tmp := max(tiempo[i], time[j ])+_ _ _ _ _ _ _;

Si tmp & lt entonces responde

ans:= tmp;

pos[i] :=derecha ;

pos[j]:= DERECHA;

Fin;

go:= ans;

Fin

else if (etapa = de izquierda a derecha)

Comencemos

ans := infinito;

Para i := 1 a n hacer

Si_______entonces

Iniciar

pos[i] :=right;

tmp:= _ _ _ _ _ _ _ _;

Si tmp & lt entonces responde

ans:= tmp;

_________;

Fin;

ir:= ans;

Fin

si no ir:= 0;

Fin;

Inicio

readln(n);

Para i := 1 a n hacer

Inicio

read(time[I]);

pos[i] :=derecha;

Fin;

writeln(go(DERECHA _ A _ IZQUIERDA));

Fin.

-

1. Preguntas de opción múltiple (* *10 preguntas, 1,5 puntos cada una, **15 puntos)

1 2 3 4 5 6 7 8 9 10

C A A D B D C B C B

2. Preguntas de opción múltiple indefinidas (* * 10 preguntas, 1,5 puntos por cada pregunta, * * * 15 puntos, sin puntos por más o menos opciones)< / p>

1 2 3 4 5 6 7 8 9 10

ACD AD ABD AC B B D D BCD ABC

Resuelve los problemas (***3 preguntas, 5. por cada pregunta puntos, * * * 15 puntos)

1. yyxy xx yyxy xyx xx xyx 2.12 3.18

4. puntos cada uno, 28 puntos por ***)

1.16 2.1 2 3 5 6 7 9 10 14 3.4 4.1 6 9 5 4 8 3 2 7

5. 1 vacío 2 puntos, los 10 espacios en blanco restantes, 2,5 puntos por cada espacio en blanco, * * * 27 puntos)

(Nota: Puede haber algunos métodos equivalentes para completar los espacios en blanco en el siguiente proceso. Cada provincia puede pedirle a sus propios expertos que lo revisen en la computadora, no es necesario enviarlo a la Comisión de Ciencia y Tecnología para su revisión)

1.Cantidad & lt= 2 (o números

②Ir (de izquierda a derecha)

③Posición[i] = izquierda (o izquierda = posición[i])

④ tiempo[i]+ir(de derecha a izquierda) (o ir(de derecha a izquierda)+tiempo[i] )

⑤Position[i]:=Lado izquierdo

En esta pregunta, LEFT se puede reemplazar con verdadero, LEFT_TO_RIGHT se puede reemplazado por verdadero y RIGHT_TO_LEFT se puede reemplazar por falso

2.① opt[k]

② home[r] := k

③ j. := i+i(o j := 2 * i o j := i * 2)

④ intercambiar(i,j)(o intercambiar(j,I))

⑤Valor[i]+montón[1](o montón[ 1]+valor[I])

⑥Mensajería instantánea