Examen de ingreso de posgrado 2016: ¿Cómo revisar las estructuras de datos informáticos?
Se puede ver en la parte de estructura de datos y los puntos de conocimiento relacionados en el Programa de Examen Unificado por Computadora de 2016 que las partes de estructura de datos y principios de composición de computadora representan una proporción similar, lo que es suficiente para reflejar la importancia de Cursos de estructura de datos en la selección de estudiantes de posgrado en informática. En respuesta a esta situación, a continuación se preparan cuidadosamente algunas sugerencias de revisión de la estructura de datos para los candidatos.
1. Análisis de puntos clave y difíciles y sugerencias de revisión.
El objetivo de la prueba de estructura de datos es dominar los conceptos, principios y métodos básicos de la estructura de datos, y dominar la lógica. estructura, estructura de almacenamiento y operaciones básicas de implementación de datos; ser capaz de analizar la complejidad temporal y espacial básica de los algoritmos; ser capaz de utilizar los principios y métodos básicos de las estructuras de datos para analizar y resolver problemas; programas e implementar algoritmos en lenguaje C, C++ o JAVA.
Por supuesto, los candidatos no necesitan revisar la programación en C o C++ específicamente debido a esto. Después de todo, el tiempo de revisión es limitado y el enfoque de los requisitos de la estructura de datos radica en las capacidades de diseño de algoritmos, no en la capacidad de escribir código. Por lo tanto, siempre que pueda expresar sus ideas claramente en forma de pseudocódigo, no tiene que forzarse a escribir un programa sin errores gramaticales.
Analicemos los puntos de conocimiento:
No hay muchos puntos de conocimiento en este capítulo de tablas lineales, pero debe tener una comprensión profunda y poder aplicar puntos de conocimiento relevantes para resolver. problemas prácticos. Las operaciones de puntero al insertar o eliminar nodos en una lista vinculada son puntos de prueba comunes para preguntas de opción múltiple. Algunas operaciones de listas vinculadas relativamente complejas, como las listas doblemente vinculadas, también aparecerán en preguntas de aplicaciones integrales.
Las pilas, colas y matrices pueden probar más puntos de conocimiento que las listas vinculadas. Las más básicas son las características de pila y cola FILO y FIFO. Por ejemplo, según las características de la pila FILO, el orden de entrada y salida de la pila suele ocurrir en preguntas de opción múltiple. Seguido por las estructuras de almacenamiento secuencial y encadenada de pilas y colas. Un punto de prueba común aquí es el funcionamiento del puntero superior de la pila, el puntero del encabezado de la cola y el puntero del final de la cola bajo diferentes estructuras de almacenamiento, especialmente los dos métodos para juzgar si la cola circular está llena o vacía. En tercer lugar, se trata del almacenamiento comprimido de matrices especiales. El enfoque de la revisión de este punto de prueba puede estar en el método de cálculo de los subíndices al convertir matrices bidimensionales y matrices unidimensionales. Por ejemplo, después de almacenar una matriz con datos distintos de cero en varias filas paralelas a la diagonal. una matriz unidimensional, cada punto de datos Cálculo de los subíndices correspondientes. El gran problema que puede surgir en este capítulo es utilizar las características de las pilas o colas como estructuras de datos básicas para respaldar el diseño de algoritmos prácticos de resolución de problemas, como el uso de pilas para resolver problemas de recursividad, el uso de colas para resolver problemas de recorrido de gráficos, etc.
Árboles y árboles binarios: en este capítulo, pasamos de estructuras de datos secuenciales a estructuras de datos jerárquicas. Dominar las diversas propiedades de los árboles y los árboles binarios, las diferentes estructuras de almacenamiento de los árboles y los árboles binarios, la conversión entre bosques, árboles y árboles binarios, la aplicación de pistas de árboles binarios y árboles binarios (árboles de clasificación binaria, árboles binarios equilibrados y Huffman árboles). La clave para dominar son los tres métodos transversales de bosque, árbol y árbol binario: frontal, medio y posterior. Esta parte siempre ha sido el foco y la dificultad de las preguntas del examen de estructura de datos, por lo que debes prestar especial atención al revisar. Algunos puntos de prueba comunes de opción múltiple incluyen: cálculo del número de nodos de un árbol binario completo y un árbol binario completo, el orden transversal correspondiente dado por el diagrama esquemático del árbol y el árbol binario, recuperación del árbol binario de acuerdo con el orden transversal del árbol binario, cálculo de la naturaleza de las pistas, cálculo de diferentes métodos para El número de campos de puntero nulo que quedan en el árbol binario después de la pista, equilibrando así la definición, las propiedades y el establecimiento del árbol binario, cuatro ajustes algoritmos y métodos de retroceso. Los puntos de prueba de aplicaciones integrales comunes incluyen: algoritmo transversal del árbol binario, que determina si un árbol binario es un árbol de clasificación binaria en función de algunas estadísticas y operaciones del árbol binario (como estadísticas de número de nodos, intercambio de subárboles izquierdo y derecho, etc.). ), estos requieren algoritmos recursivos y no recursivos para resolverse. Preste especial atención a los algoritmos no recursivos, así como a los algoritmos de recorrido de árbol binario de pistas, como los algoritmos que encuentran el nodo predecesor o sucesor de un nodo y dan códigos de Huffman.
Gráficos: lo que debe recordar en este capítulo son los gráficos y varias definiciones y métodos de almacenamiento basados en gráficos. Debe dominar los algoritmos de recorrido de profundidad y ancho de los gráficos, que son la base de los algoritmos comúnmente utilizados cuando se utilizan gráficos para resolver problemas de aplicaciones. Debe dominar una variedad de algoritmos basados en gráficos y poder realizar algoritmos específicos mediante cálculos manuales en un gráfico determinado para resolver problemas.
Los problemas de aplicación comunes se dan o se abstraen directamente y se convertirán en los siguientes problemas: solución de árbol de expansión mínima (algoritmo PRIM y algoritmo KRUSKAL, ambos son simples, pero tenga cuidado de no confundir estos dos métodos), problema de clasificación topológica (se utilizará aquí Puede prestar atención a la lista vinculada implementada por la matriz), el problema de la ruta crítica (es difícil entender el concepto a fondo, puede hacer una tabla para encontrar la ruta crítica), el problema de la ruta más corta (.
Búsqueda: en este capítulo, debe recordar el significado de las palabras clave, las palabras clave de primer nivel y las palabras clave de segundo nivel, el significado y la diferencia entre la búsqueda estática y la búsqueda dinámica que toma ASL; tenga en cuenta los métodos de cálculo y los resultados en varios algoritmos de búsqueda, especialmente algunos típicos El valor ASL de la estructura, el concepto de árbol B, la selección de métodos de resolución de conflictos de operación básica y la descripción del proceso de manejo de conflictos, el concepto de árbol B+ (puntos de prueba agregados), preste especial atención a la comparación de los conceptos de árbol B y árbol B +, y a la comparación con conceptos relacionados con tablas hash. Familiarícese con los métodos de búsqueda en listas secuenciales, listas vinculadas y árboles binarios. Preste especial atención a las condiciones aplicables de los métodos de búsqueda secuencial y binaria (por ejemplo, el método de búsqueda binaria en listas vinculadas no es aplicable) y la complejidad del algoritmo.
Clasificación: existen muchos algoritmos de clasificación. El programa de estudios de este año también agrega clasificación externa, con un total de 10 tipos. Los diferentes algoritmos tienen algunas definiciones de conceptos correspondientes que deben memorizarse. Las preguntas comunes en las preguntas de opción múltiple incluyen: Dada una secuencia, se requiere una vez. Se dan los resultados de clasificación de un método de clasificación específico, o se dan la secuencia inicial y una ronda de resultados de clasificación, y se requiere seleccionar un algoritmo de clasificación adecuado, se dan los requisitos de complejidad de tiempo y espacio y se dan las características de la secuencia. dado, etc. Si se prueba la clasificación, los puntos aparecen en preguntas de aplicación completas, que a menudo se examinan junto con matrices.
El libro de referencia recomienda que utilice la versión de Tsinghua Yan Weimin, que ayuda a establecer. un sistema de conocimiento y es más transparente en la revisión de las estructuras de datos. Libro de referencia, lea el libro detenidamente varias veces para comprender en profundidad los puntos de conocimiento relacionados con el programa de estudios.
Si tiene preguntas sobre el examen de ingreso de posgrado. , No sé cómo resumir el contenido del centro de exámenes de ingreso de posgrado y no entiendo las políticas locales para el registro de exámenes de ingreso de posgrado. Haga clic en la parte inferior para consultar el sitio web oficial y obtener materiales de revisión de forma gratuita:/xl/