¿El examen NCRE C++ Nivel 2 requiere conocimientos básicos de sexo público?
Capítulo 1 Estructura de Datos y Algoritmo
1.1 Algoritmo
Algoritmo: Es una descripción precisa y completa de la solución al problema.
Los algoritmos no son iguales a los programas, ni son iguales a los métodos informáticos; la escritura de programas no puede ser mejor que el diseño de algoritmos.
Las características básicas del algoritmo: Es un conjunto de reglas que define estrictamente la secuencia de operaciones. Cada secuencia de operaciones es válida y clara, y esta secuencia terminará un número limitado de veces. Las características incluyen:
(1) Viabilidad;
(2) Determinismo, cada paso del algoritmo debe estar claramente definido, no se permiten interpretaciones ambiguas, no se permite ninguna ambigüedad;
p>
(3) Infinito, el algoritmo debe poder completarse en un tiempo limitado, es decir, puede finalizarse después de ejecutar un número limitado de pasos, incluido el significado de un tiempo de ejecución razonable;
p >(4) Tener suficiente inteligencia.
Los elementos básicos del algoritmo: primero, la operación y manipulación de objetos de datos; segundo, la estructura de control del algoritmo.
Conjunto de instrucciones: Colección de todas las instrucciones que un sistema informático puede ejecutar.
Las operaciones básicas incluyen: operaciones aritméticas, operaciones lógicas, operaciones relacionales y transmisión de datos.
Estructuras de control de algoritmos: estructura secuencial, estructura de selección y estructura de bucle.
Métodos básicos de diseño de algoritmos: enumeración, inducción, recursividad, recursividad, tecnología de recursividad de reducción de depósitos y retroceso.
Complejidad algorítmica: complejidad temporal del algoritmo y complejidad espacial del algoritmo.
La complejidad del tiempo del algoritmo se refiere a la cantidad de cálculos necesarios para ejecutar el algoritmo.
La complejidad del espacio algorítmico se refiere al espacio de memoria necesario para ejecutar el algoritmo.
1.2 Conceptos básicos básicos de la estructura de datos
Estudie tres aspectos de la estructura de datos:
(1) La relación lógica interna de los elementos de datos en el conjunto de datos, es decir, la estructura lógica de los datos;
(2) la relación lógica interna de los elementos de datos en el conjunto de datos, es decir, la estructura lógica de los datos;
(3) La relación lógica interna de los elementos de datos en el conjunto de datos, es decir, la estructura lógica de los datos, la estructura lógica de los datos;
(2) La relación de almacenamiento de varios elementos de datos cuando el la computadora procesa datos, es decir, la estructura de almacenamiento de datos;
(3) La estructura de almacenamiento de varios elementos de datos, es decir, la estructura de almacenamiento de datos.
Una estructura de datos es una colección de elementos de datos interrelacionados.
La estructura lógica de los datos incluye:
(1) Información que representa elementos de datos
(2) Los fragmentos anteriores y siguientes que representan la relación entre; elementos de datos.
Las estructuras de almacenamiento de datos incluyen estructura secuencial, estructura de enlaces y estructura de índice.
Condiciones para la estructura lineal:
(1) Hay y solo hay un nodo raíz;
(2) Cada nodo tiene como máximo un antecedente y un piezas consiguientes.
Estructura no lineal: estructura de datos que no cumple las condiciones de una estructura lineal.
1.3 Tabla lineal y su estructura de almacenamiento secuencial
Una tabla lineal consta de un conjunto de elementos de datos. Las posiciones de estos elementos de datos solo dependen de sus propios números de serie y de las relaciones relativas. entre los elementos. La posición es lineal.
En una tabla lineal compleja, un elemento de datos compuesto por varios elementos se denomina registro, y una tabla lineal compuesta por varios registros también se denomina archivo.
Características estructurales de las listas lineales no vacías:
(1) Solo hay un nodo raíz a1, que no tiene predecesor.
(2) Allí; es solo un nodo terminal y no tiene consecuente;
(3) Excepto el nodo raíz y el nodo terminal, todos los demás nodos tienen solo un predecesor y solo un consecuente. El número de nodos n se denomina longitud de la lista lineal. Cuando n = 0, se denomina lista vacía.
La estructura de almacenamiento secuencial de una mesa lineal tiene las siguientes dos características básicas:
(1) El espacio de almacenamiento ocupado por todos los elementos de la mesa lineal es continuo;
(2) Los elementos de datos de la tabla lineal se almacenan en orden lógico en el espacio de almacenamiento.
La dirección de almacenamiento de ai es ADR(ai)=ADR(a1)+(i-1)k, donde ADR(a1) es la dirección del primer elemento y k representa el espacio ocupado por cada elemento. Número de bytes.
Operaciones de tabla de secuencia: inserción, eliminación.
1.4 Pila y cola
La pila es una lista lineal, un extremo de la cual está limitado a la inserción y eliminación; el extremo que permite la inserción y eliminación se denomina parte superior de la pila; , y el otro extremo que no permite la inserción y eliminación se llama la parte superior de la pila. Un extremo se llama la parte inferior de la pila.
La pila organiza los datos según "primero en entrar, primero en salir" (FILO) o "último en entrar, primero en salir" (LIFO), y la pila tiene una memoria. La parte superior de la pila se usa para representar la posición de la parte superior de la pila y la parte inferior de la pila se usa para representar la posición de la parte inferior de la pila.
Operaciones básicas de la pila: (1) Insertar un elemento se llama operación push; (2) Eliminar un elemento se llama operación pop (3) Leer el elemento superior de la pila es asignarlo; elemento superior de la pila. A la variable especificada, el puntero permanece sin cambios en este momento.
Una cola es una lista lineal que permite inserciones en un extremo (el final de la cola) y eliminaciones en el otro extremo (el encabezado de la cola). El puntero posterior apunta al final de la cola y el puntero frontal apunta al principio de la cola.
Una cola es una lista lineal de primero en entrar, primero en salir (FIFO) o último en entrar, último en salir (LILO).
Las operaciones de la cola incluyen: (1) operación de inserción de cola, es decir, insertar elementos del final de la cola; (2) operación de listado de cola, es decir, eliminar elementos del principio de la cola. cola.
Cola duplicada: s=0 significa que la cola está vacía, s=1 y front=rear significa que la cola está llena
1.5 Lista lineal enlazada
En la estructura de datos Cada nodo corresponde a una unidad de almacenamiento, llamada nodo de almacenamiento, o nodo para abreviar.
El nodo se compone de dos partes: (1) la parte utilizada para almacenar el valor del elemento de datos, llamada campo de datos; (2) la parte utilizada para almacenar el puntero, llamada campo de puntero; , que se utiliza para apuntar al nodo anterior o siguiente.
En una estructura de almacenamiento encadenada, el espacio de almacenamiento utilizado para almacenar estructuras de datos puede ser discontinuo y el orden de almacenamiento de los nodos de datos puede ser inconsistente con la relación lógica entre elementos de datos, mientras que el orden de almacenamiento entre elementos de datos puede ser inconsistente. La relación lógica está determinada por el campo del puntero.
El almacenamiento encadenado se puede utilizar para representar estructuras lineales o no lineales.
En una lista enlazada lineal, HEAD se denomina puntero principal y HEAD = NULL (o 0) se denomina lista vacía. Si hay dos punteros: el puntero izquierdo (Llink) apunta al anterior. nodo, y el puntero derecho (Rlink) apunta al nodo posterior.
Operaciones básicas de listas enlazadas lineales: búsqueda, inserción y borrado.
1.6 Árboles y Árboles Binarios
Un árbol es una estructura no lineal simple con características jerárquicas obvias entre todos sus elementos.
En la estructura del árbol, cada nodo tiene un solo antecedente, que se llama nodo padre. Sólo hay un nodo sin antecedente, que se llama nodo raíz del árbol, o simplemente raíz del árbol. el árbol. Cada nodo puede tener varios nodos siguientes, llamados nodos secundarios de ese nodo. Los nodos sin descendientes se denominan nodos hoja.
En una estructura de árbol, el número de nodos secundarios de un nodo se denomina grado del nodo y el grado máximo de todos los nodos se denomina grado del árbol. El nivel máximo de un árbol se llama profundidad del árbol.
Características de los árboles binarios: (1) Un árbol binario no vacío tiene solo un nodo raíz; (2) Cada nodo tiene como máximo dos subárboles, llamados subárbol izquierdo y subárbol derecho del nodo.
Propiedades básicas de los árboles binarios:
(1) En el k-ésimo nivel del árbol binario, hay como máximo 2k-1 (k ≥ 1) nodos;
( 2) Un árbol binario con una profundidad de m tiene como máximo 2m-1 nodos;
(3) Un nodo con grado 0 (es decir, nodo hoja) siempre tiene un nodo más ( nodo hoja) que grado Hay un nodo más con 2;
(4) La profundidad de un árbol binario con n nodos es al menos [log2n]+1, donde [log2n] significa tomar la parte entera de log2n;
(5) La profundidad de un árbol binario completo con n nodos es [log2n]+1;
(6) Sea un árbol binario completo que tenga n nodos.
Si los nodos están numerados con números naturales 1, 2, .... (k=1,2....n)n comenzando desde el nodo raíz y numerados en orden de capas (cada capa de izquierda a derecha), entonces el se llegan a las siguientes conclusiones:
(1) Si k=1, entonces el nodo es el nodo raíz y no tiene nodo padre si k>1, entonces el número de nodo padre del nodo es INT(k/); 2);
② Si 2k≤n, entonces el número de nodo secundario izquierdo del nodo numerado k es 2k; de lo contrario, el nodo no tiene nodo secundario izquierdo (ni nodo secundario derecho);
③ Si 2k+ 1≤n, entonces el número de nodo secundario derecho del nodo numerado k es 2k+1; de lo contrario, el nodo no tiene ningún nodo secundario derecho;
Un árbol binario completo significa que todos los nodos en cada nivel excepto el último nivel tienen dos nodos secundarios, entonces un árbol binario completo con 2k-1 nodos en el nivel k es Hay 2m-1 nodos en la profundidad m; .
Un árbol binario completo significa que, excepto el último nivel, el número de nodos en cada nivel es el mayor y solo faltan algunos nodos de la derecha en el último nivel.
La estructura de almacenamiento del árbol binario utiliza una estructura de almacenamiento en cadena, porque el árbol binario completo y el árbol binario completo se pueden almacenar en orden de capas.
Recorrido del árbol binario:
(1) Recorrido de nivel frontal (DLR), primero visite el nodo raíz, luego atraviese el subárbol izquierdo y finalmente atraviese el subárbol derecho;
p>
(2) Recorrido de orden intermedio (LDR), primero atraviesa el subárbol izquierdo, luego visita el nodo raíz y finalmente atraviesa el subárbol derecho;
(3) Recorrido de orden posterior ( LRD), primero atraviesa el subárbol izquierdo y luego atraviesa el subárbol derecho. Luego se visita el subárbol derecho y finalmente se visita el nodo raíz.
1.7 Tecnología de búsqueda
El uso de búsqueda secuencial:
(1) Las tablas lineales están desordenadas;
(2) Uso de las tablas estructura de almacenamiento encadenada.
La búsqueda binaria solo es aplicable a listas ordenadas con almacenamiento secuencial. Para una lista lineal ordenada de longitud n, solo se requieren comparaciones logarítmicas 2n en el peor de los casos.
1.8 Tecnología de clasificación
La clasificación es el proceso de organizar secuencias desordenadas en secuencias de valores ordenadas en orden no decreciente.
Método de clasificación de intercambio: (1) clasificación de burbujas, que requiere n (n-1)/2 comparaciones (2) clasificación rápida.
Clasificación por inserción: (1) Clasificación por inserción simple, que requiere n (n-1)/2 comparaciones en el peor de los casos; (2) Clasificación Hill, que requiere comparaciones O (n1.5).
Clasificación por selección: (1) Clasificación por selección simple, que requiere n(n-1)/2 comparaciones en el peor de los casos; (2) Clasificación en montón, que requiere O(nlog2n) veces en el peor de los casos; Comparar.