Me especialicé en educación primaria (artes liberales) y ahora soy estudiante de segundo año. Quiero estudiar un posgrado en ciencias de la computación. ¿Qué preparativos debo hacer?
Puedes echar un vistazo al esquema. Los algoritmos deben aprenderse para entonces, así que no se arriesgue. Los algoritmos son el alma de la clase de estructura de datos. El hecho de que no haya realizado el examen en 2009 no significa que no lo hará en el futuro. Y todavía había preguntas sobre algoritmos en 2009. La segunda pregunta de la pregunta de aplicación requiere escribir un algoritmo.
Se adjunta el esquema 09:
Objetivos del examen I
El examen integral básico de la especialización en informática cubre la organización de datos, los principios de composición de la computadora, los sistemas operativos y la informática. redes
p>Cursos básicos para carreras de otras disciplinas. Los candidatos deben dominar sistemáticamente los conceptos, principios básicos y métodos de los cursos básicos profesionales mencionados anteriormente, y ser capaces de utilizar los principios básicos y métodos básicos que han aprendido para analizar, juzgar y resolver problemas teóricos y prácticos relevantes.
Formato del examen II y estructura de la prueba
1 Puntuación completa y tiempo de prueba
La puntuación total de esta prueba es de 150 puntos y el tiempo de prueba es. 180 minutos
2. Método de respuesta a preguntas
El método de respuesta es una prueba escrita a libro cerrado
3. Estructura del contenido del cuestionario.
Estructura de datos 45 puntos
Principios de composición informática 45 puntos
Sistema operativo 35 puntos
Red informática 25 puntos
Estructura de preguntas del examen
Preguntas de opción múltiple 80 puntos (40 preguntas, 2 puntos cada una)
70 puntos para preguntas de aplicación integral
ⅢAlcance del examen
Estructura de datos
Objetivos de la prueba
1. Comprender los conceptos básicos de estructura de datos; dominar la estructura lógica, la estructura de almacenamiento y sus diferencias, así como la implementación de varias operaciones básicas
.
2. Ser capaz de diseñar y analizar algoritmos basados en el dominio de principios y métodos básicos de procesamiento de datos.
3. Ser capaz de elegir estructuras de datos y métodos adecuados para la resolución de problemas.
1. Tabla lineal
(1) Definición y operaciones básicas de tabla lineal
(2) Implementación de tabla lineal
1 .Estructura de almacenamiento secuencial
2. Estructura de almacenamiento en cadena
3. Aplicación de tabla lineal
2. (1) Conceptos básicos de pilas y colas
(2) Estructuras de almacenamiento secuencial de pilas y colas
(3) Estructuras de almacenamiento encadenado de pilas y colas
(4) Aplicaciones de pilas y colas
(5) Almacenamiento comprimido de matrices especiales
3 Árboles y árboles binarios
(1) Concepto de árboles <. /p>
(2) Árbol binario
1. La definición y características principales del árbol binario
2. La estructura de almacenamiento secuencial y la estructura de almacenamiento en cadena del árbol binario
p>
3. Recorrido del árbol binario
4. Conceptos básicos y construcción de árboles binarios de pistas
5. Árbol de clasificación binario
6. árbol
p>(3) Árboles y bosques
1. Estructura de almacenamiento de libros
2. Conversión entre bosques y árboles binarios
3. Recorrido de árboles y bosques
(4) Aplicación de árboles
1. Problema de clases de equivalencia
2. Árbol de Huffman y codificación de Huffman.
4. Gráficos
(1) Concepto de gráficos
(2) Almacenamiento y operaciones básicas de gráficos
1. >
2. Método de lista de adyacencia
(3) Recorrido del gráfico
1. Búsqueda en profundidad
2. >
(4) Aplicaciones básicas de gráficos y su análisis de complejidad
1. Árbol de expansión mínimo (coste)
2. Camino más corto
3. Clasificación topológica
4. Ruta crítica
5. Búsqueda
(1) Conceptos básicos de búsqueda
(2) Método de búsqueda secuencial
(3) Método de búsqueda media
(4) Árbol B
(5) Tabla hash y su búsqueda
p>(6) Análisis y aplicación del algoritmo de búsqueda
Página 2***? Página 6. Clasificación interna
(1) Conceptos básicos de clasificación
(2) Clasificación por inserción
1. Clasificación por inserción directa
2. Clasificación por media inserción
(3) Clasificación por burbujas (clasificación por burbujas)
(4) Clasificación por selección simple
(5) Clasificación por colinas (clasificación por conchas) )
(6) Clasificación rápida
(7) Clasificación en montón
(8) Clasificación por combinación bidireccional (clasificación por combinación)
(9) Clasificación por base
(10) Comparación de varios algoritmos de clasificación interna
(11) Aplicación de algoritmos de clasificación interna Principios de composición informática
Objetivos de la prueba
1. Comprender los principios de funcionamiento internos, las estructuras de composición y los métodos de interconexión de cada componente en un sistema informático de un solo procesador, y tener el concepto general de un sistema informático completo.
2. Comprender el concepto de estructura jerárquica de los sistemas informáticos, estar familiarizado con la interfaz entre hardware y software y dominar los conocimientos básicos y los métodos de implementación básicos de la arquitectura del conjunto de instrucciones.
3. Ser capaz de utilizar los principios y métodos básicos de composición informática para calcular y analizar problemas teóricos y prácticos en sistemas hardware informáticos.
y ser capaz de analizar algunos componentes básicos. diseño sencillo.
1. Descripción general de los sistemas informáticos
(1) Historia del desarrollo informático
(2) Jerarquía del sistema informático
1. La composición básica del software informático
2. Clasificación del software informático
3. Proceso de trabajo de la computadora
(3) Indicadores de rendimiento de la computadora
Volumen de rendimiento, tiempo de respuesta; ciclo de reloj de la CPU, frecuencia principal, CPI, tiempo de ejecución de la CPU;
2. Representación y operación de datos
(1) Sistema de numeración y codificación
1. Sistema de conteo de llevar y su conversión mutua
>2.Valor verdadero y número de máquina
3.Código BCD
4 Caracteres y cadenas
5 Código de verificación
Página. 3***? Página (2) Representación y operación de números de punto fijo
1. Representación de números de punto fijo
Representación de números sin signo;
2. Operaciones de números de punto fijo
Operaciones de desplazamiento de números de punto fijo; operaciones de suma/resta de números de punto fijo de código original; números de punto; números de punto fijo
Operaciones de multiplicación/división de p>
concepto de desbordamiento y método de identificación.
(3) Representación y operación de números de punto flotante
1. Representación de números de punto flotante
Rango de representación de números de punto flotante estándar IEEE754;
2. Suma/resta de números en coma flotante
(4) Unidad lógica aritmética ALU
1. Sumador serie y sumador paralelo
3. Jerarquía de memoria
(1) Clasificación de la memoria
(2) Estructura jerárquica de memoria
p>
(3) Memoria de acceso aleatorio semiconductor
1 Principio de funcionamiento de la memoria SRAM
2. p>
(4 ) Memoria de sólo lectura
(5) Conexión entre memoria principal y CPU
(6) RAM de doble puerto y memoria multimódulo
(7) Memoria caché (Caché)
1. Parte del acceso al programa
2. Principio de funcionamiento básico del método de mapeo. entre Caché y memoria principal
p>
4. Algoritmo de reemplazo de bloques de memoria principal en Caché
5 Estrategia de escritura de caché
(8) Virtual. memoria
1. Memoria virtual Conceptos básicos
2. Memoria virtual de página
3. Segmentar memoria virtual
4. memoria
5.TLB (tabla rápida)
IV. Sistema de instrucción
(1) Formato de instrucción
1. instrucciones
2. Formato de instrucción de código de operación de longitud fija
3. Formato de instrucción de código de operación extendido
(2) Modo de direccionamiento de instrucciones
1 . El concepto de dirección efectiva
2. Direccionamiento de datos y direccionamiento de instrucciones
Página 4***. Página 3. Métodos de direccionamiento comunes
(3) Conceptos básicos de CISC y RISC
5 Unidad central de procesamiento (CPU)
(1) Función y estructura básica
(2) Proceso de ejecución de instrucciones
(3) Función y estructura básica de la ruta de datos
(4) Función y trabajo del controlador Principio
1. Controlador cableado
2. Controlador microprogramado
Microprogramas, microinstrucciones y microcomandos;
(5) Canalización de instrucciones
1. Conceptos básicos de canalización de instrucciones
2 Conceptos básicos de canalización superescalar y dinámica
6. . Autobús
(1) Descripción general del autobús
1. Concepto básico de autobús
2. Clasificación del autobús. Indicadores de composición y desempeño (2) Arbitraje del autobús
1. Método de arbitraje centralizado
2. Método de arbitraje distribuido
(3) Operación y sincronización del autobús
1. Modo de sincronización síncrona
2. Modo de sincronización asíncrona
(4) Bus estándar
7. O) Sistema
(1) Conceptos básicos del sistema de E/S
(2) Dispositivos externos
1. >
2. Dispositivos de salida: monitores, impresoras
3. Almacenamiento externo: almacenamiento en disco duro, matriz de discos, almacenamiento en disco óptico
(3) Interfaz de E/S (I /O controlador)
1. Función y estructura básica de la interfaz de E/S
2. Puerto de E/S y su direccionamiento
(4) E/S. Modo O
1. Modo de consulta de programa
2. Modo de interrupción del programa
Conceptos básicos de interrupción del proceso de respuesta; enmascaramiento
Concepto.
3.Modo DMA
La composición del controlador DMA;
4. Modo canal
Página 5***? Página Sistema Operativo
Objetivos de la prueba
1. Comprender el papel, estado, desarrollo y características del sistema operativo en los sistemas informáticos.
2.Comprender los conceptos y principios básicos de los sistemas operativos y dominar los métodos de diseño y las tecnologías de implementación de sistemas operativos.
3. Ser capaz de utilizar los principios, métodos y tecnologías del sistema operativo aprendidos para analizar y resolver problemas.
1. Descripción general de los sistemas operativos
(1) Conceptos, características, funciones y servicios que proporcionan los sistemas operativos
(2) Desarrollo y clasificación de los sistemas operativos
(3) Entorno operativo del sistema operativo
2. Gestión de procesos
(1) Procesos y subprocesos
1. concepto
2. Estado y transición del proceso
3. Control del proceso
4. Organización del proceso
5. >
*** Sistema de almacenamiento compartido; sistema de paso de mensajes; comunicación por canalización.
6. Concepto de subprocesos y modelo multiproceso
(2) Programación del procesador
1. Conceptos básicos de programación
2. Programación de tiempos, cambios y procesos
3. Principios básicos de programación
4 Métodos de programación
5 Algoritmos de programación típicos
Primero. algoritmo de programación por orden de llegada; algoritmo de programación de prioridad de trabajo corto (tarea corta, proceso corto, hilo corto); algoritmo de programación de cola de retroalimentación multinivel; .
(3) Sincronización de procesos
1. Concepto básico de sincronización de procesos
2. Método básico para realizar la exclusión mutua de secciones críticas
Método de implementación de software; método de implementación de hardware.
3. Semáforo
4. Proceso de canalización
5. Problema de sincronización clásico
Problema productor-consumidor-Problema del escritor; El problema gastronómico de los filósofos. (4) Punto muerto
1. El concepto de punto muerto
2. Estrategia de manejo de punto muerto
3. Prevención de punto muerto
4. Punto muerto evitación
Página 6***? Estado de seguridad del sistema de páginas: algoritmo bancario.
5. Detección y liberación de interbloqueos
3. Gestión de la memoria
(1) Conceptos básicos de la gestión de la memoria
1.
Carga y vinculación de programas; protección de direcciones lógicas y de memoria física;
2. Intercambio y cobertura
3. Método de gestión de asignación continua
Asignación de partición única.
4. Método de gestión de asignación no continua
Método de gestión de páginas; método de gestión de páginas de segmentos.
(2) Gestión de la memoria virtual
1. Conceptos básicos de la memoria virtual
2. Método de gestión de paginación de solicitudes
3. Algoritmo de reemplazo
Algoritmo de reemplazo óptimo (OPT); algoritmo de reemplazo de primero en entrar, primero en salir (FIFO); algoritmo de reemplazo de reloj más cercano (LRU);
4. Estrategia de asignación de páginas
5. Jitter
Conjunto de trabajo del jitter.
6. Método de gestión de segmentos de solicitud
7. Método de gestión de páginas de segmentos de solicitudes
4. conceptos básicos
1. Concepto de archivo
2. Estructura de archivos
Archivos secuenciales; indexar archivos secuenciales.
3. Estructura de directorios
Bloque de control de archivos y nodo de índice; estructura de directorios de un solo nivel y estructura de árbol de dos niveles
Estructura de directorios.
4. Compartir archivos ***
*** compartir motivación; *** compartir método *** compartir semántica.
5. Protección de archivos
Tipo de acceso;
(2) Implementación del sistema de archivos
1. Jerarquía del sistema de archivos
2. Implementación del directorio
3. >
p>
(3) Organización y gestión del disco
1. Estructura del disco
2. Algoritmo de programación del disco
3.
p>
5. Gestión de entradas y salidas (E/S)
Página 7***? Página (1) Descripción general de la gestión de E/S
1.Dispositivos de E/S
2.Objetivos de la gestión de E/S
3.Funciones de gestión de E/S
4.Interfaz de aplicación de E/S
5.Método de control de E/S
(2) Subsistema central de E/S
1. Concepto de programación de E/S
2. Caché y búfer
3. Asignación y reciclaje de dispositivos
4. Tecnología de cola de impresión (SPOOLing)
5. Manejo de errores en redes informáticas
Objetivos de la prueba
1. Dominar los conceptos básicos, principios básicos y métodos básicos de las redes informáticas.
2. Dominar la arquitectura de las redes informáticas y los protocolos de red típicos, y comprender los principios de funcionamiento de los grupos de equipos de red típicos.
3. Los conceptos básicos, principios básicos y métodos básicos de las redes informáticas para implementar sistemas de red.
Uso
1. Arquitectura de redes informáticas
(1) Descripción general de las redes informáticas.
p>1. El concepto, composición y funciones de las redes informáticas
2. Clasificación de las redes informáticas
3. Internet
4. Trabajo de estandarización de redes informáticas y organizaciones relacionadas
(2) Arquitectura de redes informáticas y modelo de referencia
1. Estructura en capas de redes informáticas
2. Protocolos de red informática, interfaces, servicios y otros conceptos
3 Modelo de referencia ISO/OSI y modelo TCP/IP
2. p>(1) Conceptos básicos de comunicación
1. Conceptos básicos como canal, señal, banda ancha, elemento de código, baudios, velocidad, etc.
2. /p>
3. Fuente y sumidero
4. Codificación y modulación
5. Conmutación de circuitos, conmutación de mensajes y conmutación de paquetes
6. y Circuito virtual
(2) Medios de transmisión
1 Par trenzado, cable coaxial, fibra óptica y medios de transmisión inalámbricos
Página 8***? Página 2. Características de la interfaz de la capa física
(3) Equipo de la capa física
1. Repetidor
2. Capa de enlace de datos
(1) Funciones de la capa de enlace de datos
(2) Encuadre
(3) Control de errores
1 Codificación de detección de errores
2. Codificación de corrección de errores
(4) Control de flujo y mecanismo de transmisión confiable
1.
2. Ventana deslizante de fotograma único y protocolo de parada y espera
3. Ventana deslizante de fotogramas múltiples y protocolo de retroceso de fotograma N (GBN)
> 4. Ventana deslizante de fotogramas múltiples y protocolo de retransmisión selectiva (SR)
(5) Control de acceso a medios
1. Control de acceso a medios por división de canales
Frecuencia Multiplexación por división, multiplexación por división de tiempo, multiplexación por división de longitud de onda, multiplexación por división de código
Este principio.
2. Acceso instantáneo al control de acceso a los medios
Protocolo ALOHA; protocolo CSMA/CD; Acceso de sondeo al control de acceso a los medios: Protocolo de transferencia de tarjeta
(6) Red de área local
1. Conceptos básicos y arquitectura de la red de área local
2. >
3.IEEE 802.11
4. Principios básicos de la red Token Ring
(7) Red de área amplia
1. red
2.Protocolo PPP
3.Protocolo HDLC
4.Principios básicos de la red ATM
(8) Capa de enlace de datos equipo
1. Puente de red
El concepto de puente de red y cálculo de árbol de expansión; puente de ruta de selección de fuente y selección de fuente
2. y su principio de funcionamiento.
4. Capa de red
(1) Funciones de la capa de red
1. Interconexión de red heterogénea
2.
3. Control de congestión
(2) Algoritmo de enrutamiento 1. Enrutamiento estático y enrutamiento dinámico
2. Algoritmo de enrutamiento por vector distancia
3. Algoritmo de enrutamiento del estado del enlace
4. Enrutamiento jerárquico
3) IPv4
1.Agrupación IPv4
2.Dirección IPv4 y NAT
3 División de subred y máscara de subred, CIDR
4 protocolo ARP, protocolo DHCP y protocolo ICMP
4) IPv6
<. p>1. Principales características de IPv62. Dirección IPv6
5) Protocolo de enrutamiento
1. Enrutamiento intradominio y enrutamiento entre dominios
3.Protocolo de enrutamiento RIP
4.Protocolo de enrutamiento OSPF
Protocolo de enrutamiento 5.BGP
6) Multicast IP
1. Concepto de multicast
2. Dirección IP de multicast
3. Algoritmo de enrutamiento de multicast
7. ) IP móvil
1. El concepto de IP móvil
2 El proceso de comunicación de IP móvil
8) Equipo de capa de red
1. La composición y función de un enrutador
2 Tabla de enrutamiento y reenvío de rutas
Capa de transporte
Servicios proporcionados por la capa de transporte
1. Funciones de la capa de transporte
2. Direccionamiento y puertos de la capa de transporte
3. Servicios sin conexión y servicios orientados a conexión
Protocolo UDP<. /p>
1.Datagrama UDP
2.Verificación UDP
Protocolo TCP
1.Segmento TCP
2. Gestión de conexiones TCP
3.Transmisión confiable TCP
4.Control de flujo TCP y control de congestión
Capa de aplicación
No. ***? Modelo de aplicación de red de páginas
1. Modelo cliente/servidor
2. Modelo P2P
Sistema DNS
1.
2. Servidor de nombres de dominio
3. Proceso de resolución de nombres de dominio
FTP
1. >
2. Controlar la conexión y la conexión de datos
Correo electrónico
1. Estructura del sistema de correo electrónico
2. y MIME
3.Protocolo SMTP y protocolo POP3
WWW
1 Concepto y estructura de WWW
2.Protocolo HTTP IV. .
Ejemplos de preguntas del test
1. Preguntas de opción única: de 1 a 40 preguntas, cada pregunta vale 2 puntos, con una puntuación máxima de 80 puntos. Entre las cuatro opciones dadas en cada pregunta,
Elija la que mejor cumpla con los requisitos de la pregunta.
Ejemplos de preguntas de prueba:
1. Entre los siguientes algoritmos de clasificación, el que tiene una complejidad temporal de O(nlog2n) y ocupa menos espacio adicional es
<. p>A. Clasificación de montónB. Clasificación de burbujas
C. Clasificación rápida
D. Clasificación de colinas
2. Entre las siguientes secuencias, la que satisface la definición de montón es
A. (100, 86, 48, 73, 35, 39, 42, 57, 66, 21)
B. (12, 70, 33, 65, 24, 56, 48, 92, 86, 33)
C. (103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 6, 26)
D. (5, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100)
3. El contador de programa PC se utiliza para almacenar la dirección de instrucción. ¿A cuál de los siguientes registros corresponde el mismo?
A. Registro de instrucciones IR
B. Registro de datos de la memoria principal MDR
C. Registro de palabras de estado del programa PSWR
D. Registro de dirección de memoria principal MAR
4. Supongamos que un número decimal es -66 y está almacenado en un registro de 8 bits en forma de complemento a dos. El contenido del registro se expresa en hexadecimal.
Expresado como
A. C2H
B. BEH
C. BDH
D. 42H
5. Entre las siguientes transiciones de estado de proceso, la transición imposible es
A. Ejecutar → Listo
B. Ejecutar → Espera
C. Espere → Ejecutar
D. Espere → Listo
6. Hay tres procesos concurrentes en un determinado sistema que requieren cuatro recursos similares. El recurso mínimo que no causará un punto muerto en este sistema es
A. 9
B. 10
C. 11
D. 12
7. De acuerdo con el principio de funcionamiento del protocolo CSMA/CD, la longitud mínima de la trama debe aumentarse en las siguientes situaciones:
A. La velocidad de transmisión de la red permanece sin cambios, pero la distancia máxima del dominio de colisión se acorta
Página 12***? Página B. La distancia máxima del dominio de colisión permanece sin cambios y la velocidad de transmisión de la red aumenta
C. La probabilidad de que los protocolos de capa superior utilicen TCP aumenta
D. Reducir el número de repetidores en la línea sin cambiar el dominio de colisión
8 En el protocolo de retransmisión selectiva (SR), cuando el campo de número de secuencia de la trama es de 3 bits, y la ventana de recepción y de envío. ventana Cuando los tamaños son iguales
, el tamaño máximo de la ventana de envío es
A. 2
B. 4
C. 6
D. 8
2. Preguntas de aplicación integral: Preguntas 41 a 47, ***70 puntos.
Ejemplos de preguntas del examen:
41. (10 puntos) Supongamos el grafo no dirigido G = (V, E), donde V = {1, 2, 3, 4, 5}, E = { (1, 2, 4), (2, 5, 5),
(1, 3, 2), (2, 4, 4), (3, 4, 1), (4, 5, 3), (1, 5, 8)}, cada uno El borde está representado por un triple. Los dos primeros elementos del triple son los vértices asociados con el borde y el tercer elemento es el peso del borde. Por favor escriba el proceso de resolución del camino corto desde el vértice 1 a otros puntos en el gráfico G. Es necesario enumerar los vértices en la ruta más corta y calcular la longitud de la ruta.
42 (15 puntos) Se sabe que un árbol binario se almacena en una lista enlazada binaria y la estructura de nodos es. :
Datos de LeftChild RightChild, raíz apunta al nodo raíz. Ahora defina la ruta raíz del nodo X0 en el árbol binario como una ruta desde el nodo raíz hasta el nodo X0. Escriba un algoritmo para generar la ruta raíz más larga (múltiples rutas) en el árbol binario p>Solo una de las raíces más largas. Las rutas se pueden generar. El algoritmo se puede implementar en lenguaje C, C++ o JAVA).
43. (11 puntos) La dirección de la memoria principal de una determinada computadora es de 32 bits y se direcciona en bytes.
Supongamos que la caché de datos puede almacenar hasta 128 bloques de memoria principal
utilizando el método asociativo de configuración de 4 vías, el tamaño del bloque es de 64 bytes y cada bloque está configurado con 1 bit válido "sucio"
Un poco.
Requisitos:
(1) Pagar las tres partes de la dirección de memoria principal (Etiqueta), número de grupo (Índice) y dirección de bloque (Desplazamiento) respectivamente
Posición y número de dígitos
(2) Calcule el número total de dígitos en el caché de datos (proporcione un proceso de cálculo detallado)
44 (0,10 puntos) La siguiente figura es un diagrama esquemático simplificado de la estructura de conexión de la CPU y la memoria principal (todos los multiplexores se omiten en la figura).
Existe un registro de acumulación AC, un registro de datos de estado y otros cuatro registros: registro de direcciones de la memoria principal
MAR, registro de datos de la memoria principal MDR, contador de programas PC y registro de instrucciones IR, cada componente y la lista de conexiones entre ellos
representa la ruta de datos y la flecha representa la dirección de transmisión de la información.
Preguntas frecuentes sobre el examen de ingreso de posgrado en informática
Dirección:/post/49.html
Esquema del examen de ingreso de posgrado en informática de 2010
Dirección: /post /70.html
Preguntas y análisis del examen unificado de informática de 2009
Dirección: /post/70.html
Resumen en vídeo del examen de ingreso de posgrado en informática
Dirección: /post/19.html
Revise la orientación y sugerencias de preparación para el examen de ingreso nacional unificado de posgrado en informática
Dirección: /post/390.html
09 Se anuncia el Ranking Nacional de Informática 2020
Dirección: /post/70.html
Un plan de preparación eficaz para el examen unificado de ingreso de posgrado en informática
Dirección: /post/335 .html
Las 10 mejores escuelas para exámenes de ingreso de posgrado por computadora
Dirección: /post/70.html