1. Análisis de puntos clave y difíciles y sugerencias de revisión.
El objetivo del examen del programa de examen unificado es dominar los conceptos, principios y métodos básicos de la estructura de datos, y dominar la estructura lógica, la estructura de almacenamiento y las operaciones básicas de la implementación de datos; ser capaz de analizar la complejidad temporal básica y la complejidad espacial de los algoritmos; ser capaz de utilizar los principios y métodos básicos de las estructuras de datos para analizar y resolver problemas; Diseñar programas e implementar algoritmos en lenguaje C, C++ o JAVA.
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étera.
Á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 matrices), el problema de la ruta crítica (es difícil comprender 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; ASL tiene en cuenta varios métodos de cálculo y resultados en este algoritmo de búsqueda, especialmente los valores ASL de algunas estructuras típicas, 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+ (agregar puntos de prueba), especialmente tenga en cuenta la comparación de los conceptos de árbol B y árbol B+, así como 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 la búsqueda secuencial y los métodos de búsqueda binaria (por ejemplo, el método de búsqueda binaria en listas vinculadas no es aplicable) y la complejidad del algoritmo. .
Clasificación: el último esquema amplía el alcance de clasificación interna del año pasado a la clasificación, que es un punto importante y difícil. Hay muchos algoritmos de clasificación y 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 recordarse. Los problemas comunes con las preguntas de opción múltiple incluyen: dada una secuencia, que requiere un resultado de clasificación de un método de clasificación específico después de una ejecución, o dada una secuencia inicial y una ronda de resultados de clasificación, que requieren la selección de un algoritmo de clasificación apropiado, dado el tiempo y el espacio. complejidad. requisitos y características de la secuencia, etc. Si el punto de prueba de clasificación aparece en un problema de aplicación integral, a menudo se examina en combinación con una matriz.