Un portador de información es una colección de números, caracteres y todos los símbolos que pueden ser reconocidos y procesados ​​por computadoras que describen los atributos de las cosas objetivas.

La unidad básica de datos, que consta de elementos de datos, la unidad indivisible más pequeña.

Una colección de elementos de datos con las mismas propiedades, un subconjunto de datos.

Una colección de valores y un conjunto de operaciones definidas en la colección.

1. Definición: Un modelo matemático y un conjunto de operaciones definidas en el modelo.

2. Características: La definición sólo depende de su conjunto de características lógicas, y no tiene nada que ver con cómo se representa e implementa dentro del ordenador.

3. Representación: (objetos de datos, relaciones de datos, conjuntos de operaciones básicas)

1. Estructura: la relación entre elementos de datos.

2. Definición: Colección de elementos de datos que tienen una o más relaciones específicas entre sí.

3. Contenido: estructura lógica, estructura de almacenamiento, operaciones de datos.

1. Definición: La relación lógica entre elementos de datos, que no tiene nada que ver con el almacenamiento y es independiente de la computadora.

2. Clasificación

1. Definición: Representación de la estructura de datos en una computadora (también llamada imagen/estructura física)

2. Incluyendo: representación de elementos de datos y representación de relaciones.

3. Clasificación

1. Definición de operación: Señale la función de operación según la estructura lógica.

2. Implementación de la operación: Señale los pasos operativos específicos de la operación de acuerdo con la estructura de almacenamiento.

1. Pertenece a una estructura lógica

2. Una cola circular es una cola representada por una tabla de secuencia. Es una estructura de datos, no una estructura de datos abstracta.

3. Los espacios de almacenamiento de diferentes nodos pueden ser discontinuos, pero los espacios de almacenamiento dentro de los nodos deben ser continuos.

4. Dos estructuras de datos diferentes, la estructura lógica y la estructura física, pueden ser exactamente iguales, pero las operaciones de datos son diferentes.

1. Finitud

2.Certidumbre

3. Viabilidad

4.Entrada

5.Salida

1. Corrección

2. Legibilidad

3. Robustez

4. Eficiencia y bajos requisitos de almacenamiento.

Definición: Mide qué tan rápido aumenta el tiempo de ejecución de un algoritmo a medida que aumenta el tamaño del problema.

1. Definición: Mide qué tan rápido aumenta el espacio requerido por el algoritmo a medida que aumenta el tamaño del problema.

2. El algoritmo funciona in situ: el espacio auxiliar requerido por el algoritmo es constante, es decir, O (1)

1. Fusione dos listas enlazadas ascendentes de longitud m, n en una lista enlazada descendente de m n (tome el elemento más pequeño, método de interpolación principal)

2. Cálculo de la complejidad del tiempo.

3. Para el mismo algoritmo, cuanto mayor sea el nivel del lenguaje implementado, menor será la eficiencia de ejecución.

La posición inicial del espacio de almacenamiento.

Espacio máximo de almacenamiento de la tabla de secuencia.

La longitud actual de la tabla de secuencia.

Lenguaje C: L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

C: L.data=nuevo ElemType[InitSize];

1. La tabla lineal debe ser una secuencia finita.

2. Inserte un número en la i-ésima posición de la tabla de secuencia. El valor legal de i es: 1≤i≤n 1.

1. Invertir todos los elementos de la lista de secuencia.

1.1 En la matriz A [m n], hay dos tablas de secuencia con longitudes myn, y las posiciones están intercambiadas.

2. La lista secuencial (no ordenada) elimina todos los elementos de datos con valor x

2.1 La lista secuencial (no ordenada) elimina todos los elementos con valores entre syt

3. La lista de secuencia ordenada elimina todos los elementos entre los valores dados syt

4. Eliminar todos los elementos con valores duplicados de la lista ordenada.

4.1 Cambiar lista ordenada a lista desordenada

5. Fusionar dos listas ordenadas en una lista ordenada y devolver el resultado mediante la función

6. Una secuencia ascendente S de longitud L, la mediana es ┍L/2┑ Encuentre la mediana de dos secuencias ascendentes de igual longitud A y B

7. Si el número de elementos con valor x > n/2, se llama elemento principal Encuentre el elemento principal de A.

8. Encuentra el entero positivo más pequeño que no aparece en la matriz, menos tiempo

1. Independientemente de si hay un nodo principal o no, el puntero principal siempre apunta al primer nodo de la lista vinculada.

2. El nodo principal es el primer nodo en la lista vinculada con el nodo principal y generalmente no almacena información.

1. La operación en la primera posición de la lista vinculada es coherente con la operación en otras posiciones.

2. Independientemente de si la lista vinculada está vacía o no, el puntero principal apunta al puntero no nulo del nodo principal, y las listas vacías y no vacías se tratan de la misma manera.

Operación de inserción directa: busque primero el nodo anterior, la complejidad del tiempo es O (n)

Extensión: convierta la operación de inserción hacia adelante en una operación de inserción hacia atrás y luego intercambie los datos de los dos nodos. La complejidad del tiempo es O (1).

Busque primero el nodo predecesor y luego elimine el nodo, O (n)

Extensión: primero intercambie datos con el nodo sucesor y luego elimine el nodo sucesor, O (1)

Cuente el número de nodos de datos

1. Condición nula: si el puntero del nodo principal apunta al puntero principal

2. Cuando opere en el principio y el final de una lista enlazada individualmente: no configure el puntero principal, solo configure el puntero final, lo cual es más eficiente.

3. Puede recorrer toda la lista vinculada comenzando desde cualquier nodo.

Condición nula: el campo anterior y el campo siguiente del nodo principal apuntan al puntero principal.

1. Al igual que la tabla de secuencia, se debe asignar un espacio de memoria continuo por adelantado.

2. La inserción y eliminación solo requieren modificar el puntero y no requieren mover elementos.

3. Muy inteligente en lenguajes de alto nivel (Básico) que no admiten punteros.

Se puede acceder a la lista de secuencia de forma secuencial o aleatoria. Solo se puede acceder a la lista vinculada de forma secuencial desde el encabezado.

1. Buscar por valor

2. Buscar por número de serie

1. Consideraciones de almacenamiento

2. Consideraciones basadas en operaciones

3. Consideraciones ambientales

1. La estructura de almacenamiento en cadena es más conveniente que la estructura de almacenamiento secuencial para representar varias estructuras lógicas.

2. El almacenamiento secuencial no solo se puede utilizar para almacenar estructuras lineales, sino también estructuras de gráficos y árboles (árboles binarios completos).

3. Las listas enlazadas estáticas necesitan asignar un gran espacio continuo, y la inserción y eliminación no requieren elementos móviles.

4. Si se utiliza una lista enlazada individualmente para representar la cola, se debe utilizar una lista enlazada circular con un puntero de cola.

5. Dada una matriz unidimensional, el tiempo mínimo para construir una lista enlazada individualmente ordenada es O (nlog₂n)

6. Las operaciones más utilizadas en listas vinculadas son insertar después del último elemento y eliminar el primer elemento. La operación que ahorra más tiempo es.

1. Puntero superior de la pila: S.top Elemento superior de la pila: S.data[S.top]

2. Empuje a la pila: el puntero primero se incrementa en 1 y luego el valor se envía al elemento superior de la pila.

3. Haga estallar la pila: primero tome el valor del elemento en la parte superior de la pila y luego disminuya el puntero en la parte superior de la pila en 1.

4. Condiciones para el juicio vacío y el juicio pleno: varían debido a las diferentes condiciones reales dadas.

1. Definición: Coloque la parte inferior de las dos pilas en ambos extremos del espacio compartido y la parte superior de las dos pilas se extienda hacia el medio.

2. Juicio en blanco: top0=-1 top1=MaxSize

3. Frase completa: top1-top0=1

4. Empuje hacia la pila: top0 primero agrega 1 y luego asigna un valor, top1 primero disminuye 1 y luego asigna un valor, y ocurre lo contrario cuando sale de la pila.

1. Elemento superior de la pila

2. El siguiente elemento del elemento superior de la pila.

3. Las condiciones de evaluación para pila vacía y pila llena también cambiarán.

Para secuencias crecientes

f(2)=2, f(3)=5, f(4)=14

1. La pila y la cola tienen la misma estructura lógica, no una estructura de almacenamiento.

2. La lista vinculada no tiene un nodo principal y todas las operaciones se realizan al principio de la lista. Es la pila de enlaces más inadecuada.

3. Inserte un nodo x en una pila de cadena (sin el nodo principal) cuyo puntero superior sea superior

4. La secuencia de inserción es 1,2,...,n, y la secuencia pop es P1, P2,...,Pn. Si P2 = 3, el número de valores posibles de P3 es n-1.

5. Al reescribir un programa recursivo de forma no recursiva, es posible que la pila no sea aplicable

6. Las definiciones de los punteros en la parte superior de la pila, el principio de la cola y el final de la cola no son únicos. Asegúrese de revisar la pregunta detenidamente.

1. Determinar si una lista enlazada es centralmente simétrica

1. Dos punteros: el frente apunta al elemento principal de la cola y el trasero apunta a la siguiente posición del elemento final de la cola.

2. Estado inicial (equipo vacío): Q.front==Q.rear==0

3. Ingrese a la cola: primero envíe el valor al último elemento de la cola y luego agregue 1 al último puntero de la cola.

4. Quitar de la cola: primero tome el valor del elemento principal y luego agregue 1 al puntero principal

5. Existe un desbordamiento falso

6.Descripción del tipo

1. Estado inicial (equipo vacío): Q.front==Q.rear==0

2. Avance el puntero frontal: Q.front=(Q.front 1)%MaxSize

3. Avance el puntero de cola de cola: Q.rear=(Q.rear 1)%MaxSize

4. Longitud de la cola: (Q.rear MaxSize-Q.front)%MaxSize

5. Distinga entre equipos vacíos y llenos.

1.Descripción del tipo

2. Lista enlazada única con nodo principal: operaciones unificadas de inserción y eliminación

3. Adecuado para situaciones en las que los elementos de datos cambian mucho, no hay desbordamiento de cola ni asignación de almacenamiento irrazonable en varias colas.

1. Cuando se utiliza una cola de almacenamiento encadenada para realizar una operación de eliminación, se pueden modificar tanto el puntero principal como el final.

2. En la cola en cadena, cuando el elemento señalado por x ingresa a la cola, realice la operación

1. Determinar el estado inicial y completo de la cola circular.

2. Determine la secuencia que no puede obtener la cola de doble extremo restringida de entrada / salida

1. Configure una pila vacía y lea los paréntesis secuencialmente

2. Si es ), saldrá de la pila si se combina con la parte superior de la pila (o es ilegal).

3. Si es (, empújelo a la pila como una nueva expectativa más urgente).

4. El algoritmo finaliza y la pila está vacía; de lo contrario, la secuencia de corchetes no coincide

1. Agregue paréntesis a todos los operadores y sus operandos según la precedencia de los operadores (no es necesario agregar paréntesis si existen originalmente)

2. Mueva el operador después del paréntesis correspondiente.

3. Retire los soportes

Nota: La expresión de prefijo coloca el operador delante del paréntesis y los demás son iguales.

1. Números: agregados directamente a la expresión del sufijo

2. Si es (: empujar para apilar

3. Si es): agregue los operadores en la pila a la expresión postfijo en secuencia hasta ( y elimine ( en la pila

4.Si - */

5. Se completa el recorrido. Si la pila no está vacía, muestre todos los elementos en secuencia.

1. Escanea cada término de la expresión secuencialmente.

2. Operando: empujar sobre la pila

3. Operador <op>: salga continuamente de dos operandos xey de la pila para formar una instrucción de operación x<op>y y envíe el resultado del cálculo nuevamente a la pila.

1. Expresión recursiva (cuerpo recursivo)

2. Condiciones de contorno (salida recursiva)

1. Configure un búfer de datos de impresión, pausar la salida cuando esté llena, hacer otras cosas y esperar a que la impresora envíe una solicitud.

1. Organice cada solicitud en una cola de acuerdo con el orden de tiempo y asigne la CPU al primer usuario de la cola cada vez.

1. Matriz simétrica

2.matriz triangular

3. Matriz tridiagonal

El número de nodos secundarios de un nodo.

El grado máximo de un nodo en un árbol.

Comenzando desde el nodo raíz y acumulando capa por capa de arriba a abajo.

Comenzando desde los nudos de las hojas y acumulando capa por capa de abajo hacia arriba.

El número máximo de niveles de nodos en el árbol.

La secuencia de nodos que pasan entre dos nodos.

El número de aristas pasadas en el camino.

Las ramas del árbol están dirigidas (los padres señalan a los niños), el camino es de arriba a abajo y no hay camino entre dos niños.

Suma de series geométricas

1. Los subárboles se pueden dividir en izquierdo y derecho, y el orden no se puede invertir arbitrariamente.

2. La diferencia entre un árbol binario y un árbol ordenado de grado 2

1. Árbol binario completo

2. Árbol binario completo

3. Árbol de clasificación binaria

4.Árbol binario equilibrado

1.n0=n₂ 1

2. La enésima capa tiene como máximo 2 ^ (n-1) nodos.

3. Un árbol binario con altura h tiene como máximo 2^h-1 nodos.

4. Para árboles binarios completos

5.La altura de un árbol binario completo con n nodos es ㏒₂n (quitado del límite) 1

1. Adecuado para árboles binarios completos y árboles binarios completos.

2. Generalmente, algunos nodos vacíos que no existen se agregan al árbol binario.

3. Nota: Solo iniciando el almacenamiento desde el subíndice 1 de la matriz se pueden satisfacer las propiedades anteriores.

4. Distinga entre el almacenamiento secuencial de árboles y árboles binarios.

1. La lista vinculada binaria tiene tres campos: datos, lchild, rchild

2. Una lista enlazada binaria con n nodos tiene n 1 campos de enlace vacíos (el nodo raíz no usa un puntero) para formar una lista enlazada de pistas.

1. Pensamientos

2. Implementación del algoritmo

3. La eficiencia de ejecución de los algoritmos no recursivos es mayor que la de los algoritmos recursivos.

1. Pensamientos

2. Implementación del algoritmo

1. Reserva y reserva a mitad de camino

2. Orden posterior y a mitad del pedido

3. No se permiten el primer pedido ni el último pedido.

1.Propósito: Acelerar la búsqueda de predecesores y sucesores de nodos.

2. Reglamentos

3.Pista: Indicaciones sobre predecesores y sucesores

4. Subprocesamiento: el proceso de atravesar un árbol binario en un orden determinado para convertirlo en un árbol binario subproceso.

1. La esencia de las pistas

2. Implementación del recorrido en orden de subprocesos

3. A veces, también se agrega un nodo principal a la lista vinculada de pistas para formar una lista vinculada de pistas bidireccional.

1. Se puede implementar un algoritmo no recursivo para atravesar árboles binarios utilizando árboles binarios de pistas.

2. Implementación del algoritmo

1. Definición: almacenamiento de espacio continuo, cada nodo agrega un pseudopuntero para indicar la posición de los padres en la matriz, el subíndice del nodo raíz es 0 y su pseudopuntero es -1

2. Características: Los padres se pueden obtener rápidamente, pero el niño debe atravesar toda la estructura.

1. Definición: conecte los hijos de cada nodo en una estructura lineal utilizando una única lista vinculada

2. Características: Es conveniente preguntar por los niños, pero inconveniente preguntar por los padres.

1. Definición: el puntero izquierdo apunta al primer hijo, el puntero derecho apunta al primer hermano y la lista binaria vinculada se utiliza como estructura de almacenamiento.

2. Ventajas: conveniente para convertir un árbol en un árbol binario, fácil de encontrar hijos

3. Desventajas: es problemático encontrar padres. Será conveniente agregar padres para señalar a los padres.

El puntero izquierdo apunta al primer hijo, el puntero derecho apunta al primer hermano, la raíz no tiene hermanos y el árbol binario no tiene un subárbol derecho.

La raíz de cada árbol binario sirve como subárbol derecho del árbol binario anterior.

1. La raíz y el subárbol izquierdo del árbol binario se utilizan como la forma de árbol binario del primer árbol y luego se convierten en un árbol (el hijo derecho se convierte en hermano)

2. El subárbol derecho de la raíz y su hijo izquierdo sirven como segundo árbol, y el hijo derecho sirve como tercer árbol, y así sucesivamente.

Visite primero la raíz y luego recorra cada subárbol de izquierda a derecha, que es lo mismo que el recorrido de la raíz primero del árbol binario correspondiente.

Recorra cada subárbol de izquierda a derecha y luego visite la raíz, que es lo mismo que el recorrido de la raíz media del árbol binario correspondiente.

Igual que el recorrido de raíz primero de un árbol binario

Igual que el recorrido de raíz en un árbol binario

1.Union (S, Root1, Root2): fusiona dos subcolecciones y conecta la raíz Root2 con la raíz Root1

2.Find(S,x): Encuentra la raíz del árbol que contiene x hasta encontrar un número negativo

3.Inital(es): Cada elemento del conjunto S se inicializa como un subconjunto con un solo elemento (a todos los elementos se les asigna un valor de -1)

1. Las claves de todos los nodos en el subárbol izquierdo son menores que las del nodo raíz.

2. Las palabras clave de todos los nodos en el subárbol derecho son mayores que las del nodo raíz.

3. Los subárboles izquierdo y derecho son cada uno de ellos un árbol de clasificación binario.

El recorrido en orden puede obtener una secuencia ordenada creciente

1. Implementación no recursiva, la recursividad es simple pero ineficiente

1. El nuevo nodo insertado debe ser un nodo hoja (solo se insertará cuando el árbol esté vacío)

1. Incluso si los elementos insertados son los mismos pero en diferentes órdenes, el BST construido será diferente.

1. Nodo hoja: eliminar directamente

2.i tiene solo un subárbol izquierdo/derecho: hagamos que el subárbol de i se convierta en el subárbol del nodo padre de i, reemplazando la posición de i

3.i tiene dos subárboles a la izquierda y a la derecha: reemplace i con el sucesor/predecesor directo de i, luego elimine el sucesor/predecesor directo y convierta al caso 1,2

1. Longitud promedio de búsqueda ASL = (número de cada capa * número de capas correspondientes) / número total

2. Peor caso: similar a la lista ordenada individualmente enlazada O(n)

3. Mejor caso: árbol binario equilibrado O(㏒₂n)

4. Proceso de búsqueda: similar a la búsqueda binaria, pero el árbol de decisión de la búsqueda binaria es único.

1. Árbol binario equilibrado: el valor absoluto de la diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo no supera 1

2. Factor de equilibrio: la diferencia de altura entre los subárboles izquierdo y derecho del nodo -1,0,1

1. El objeto de cada ajuste es el subárbol mínimo desequilibrado

2.LL rotación equilibrada (rotación única derecha)

3.Rotación equilibrada RR (rotación única izquierda)

4.Rotación equilibrada LR (doble rotación primero hacia la izquierda y luego hacia la derecha)

5.RL rotación equilibrada (doble rotación derecha y luego izquierda)

1. La profundidad máxima de un árbol binario equilibrado que contiene n nodos es O (㏒₂n) y la longitud de búsqueda equilibrada es O (㏒₂n).

1. La longitud de ruta ponderada (WPL) del nodo

2. Longitud ponderada del camino del árbol.

3. Árbol de Huffman (árbol binario óptimo)

1.Proceso de construcción

2.Características

1. Codificación de longitud fija

2. Codificación de longitud variable

3. Codificación de prefijo

4.Proceso de codificación de Huffman

<v,w>: arco de v a w (v es adyacente a w/w es adyacente a v) v: cola del arco w: cabeza del arco

(v,w)=(w,v)

No hay aristas duplicadas y no hay aristas desde el vértice hacia sí mismo.

Hay aristas duplicadas y hay aristas desde el vértice hacia sí mismo.

1. Gráfico completo no dirigido: hay n (n-1)/2 aristas entre dos vértices cualesquiera.

2. Gráfico completo dirigido: dos vértices cualesquiera tienen dos arcos en direcciones opuestas, n (n-1)

Generar subgrafo: subgrafo con el mismo conjunto de vértices

1. Subgrafo conectado al máximo (componente conectado): un subgrafo conectado contiene todos los bordes, no necesariamente todos los vértices (no necesariamente un gráfico conectado)

2. Subgrafo mínimamente conectado: un subgrafo que mantiene la conectividad del gráfico mientras minimiza el número de aristas (puede ser un solo vértice)

Mínimo, máximo relativo al lado

1. Árbol de expansión de un gráfico conectado; un subgrafo conectado mínimo que contiene todos los vértices (n vértices tienen n-1 aristas)

2. En un gráfico no conexo, el árbol de expansión de componentes conectados constituye el bosque de expansión del gráfico no conexo.

1. Grado de un vértice: el número de aristas con el vértice como punto final

2. En un gráfico no dirigido: la suma de grados de todos los vértices = número de aristas * 2

3. En un gráfico dirigido: el grado de un vértice = grados de entrada y de salida, la suma de los grados de entrada de todos los vértices = la suma de los grados de salida = el número de aristas

1. Imagen ponderada (neta): una imagen con pesos en el costado

1. Bucle/Bucle: la ruta donde el primer vértice y el último vértice son iguales

1. Camino simple: un camino en el que los vértices no aparecen repetidamente

2. Bucle simple: excepto el primer vértice y el último vértice, los demás vértices no aparecen repetidamente.

1. Si existe el camino más corto de v a w, es una distancia. Si no existe, se registra como infinito.

1. Un gráfico dirigido en el que el grado de entrada de un vértice es 0 y el grado de entrada de los otros vértices es 1.

1. Una matriz unidimensional almacena información de vértices y una matriz bidimensional almacena información de bordes.

1. Gráfico no dirigido/gráfico dirigido: el número de elementos distintos de cero en la i-ésima fila es el grado/grado exterior del i-ésimo vértice

2. Es fácil determinar si hay aristas, pero es difícil determinar cuántas aristas hay.

3. Los gráficos densos son adecuados para utilizar matrices de adyacencia.

4.Aⁿ[i][j]: El número de caminos de longitud n desde el vértice i hasta el vértice j

1. Combine el almacenamiento secuencial y vinculado para crear una lista vinculada individualmente para cada vértice i

2. Tabla de vértices: puntero del campo de vértice (datos) a la primera lista de adyacencia (firstarc)

3. Tabla de borde: campo de punto de adyacencia (adjvex) Campo de puntero que apunta a la siguiente lista de adyacencia (nextarc)

1. Gráfico no dirigido: espacio de almacenamiento O (|V| 2|E|) gráfico dirigido: O(|V| |E|)

2. Utilice el método de lista de adyacencia para ahorrar espacio en gráficos dispersos.

1. ArcNode: 5 dominios

2. Puntero de vértice (VNode): 3 campos

3. Nota: los nodos Vertex se almacenan secuencialmente

1. Es fácil encontrar el arco con vi como cola y el arco con vi como cabeza. Es fácil encontrar el grado exterior/interior del vértice.

2. Quiere decir que no es único, pero determina una gráfica.

1. Cada borde está representado por un nodo.

2. El vértice está representado por un nodo.

1. Los bordes adjuntos al mismo vértice están conectados en la misma lista vinculada y cada nodo de borde está vinculado en dos listas vinculadas al mismo tiempo.

2. Cada borde tiene un solo nodo

Un algoritmo transversal jerárquico similar a un árbol binario, que da prioridad al nodo descubierto más temprano.

1. Primero visite el vértice inicial v

2. Visite todos los vértices adyacentes no visitados de v en secuencia

3. Luego comience desde estos vértices y visite todos sus nodos no visitados.

1. Búsqueda jerárquica, accediendo a un lote de nodos hacia adelante, a diferencia de la profundidad primero donde hay una situación hacia atrás, no es recursiva

2. Utilice la matriz de marcas auxiliares de la cola (ya sea que se visite el vértice)

3. Implementación del algoritmo

1. Complejidad espacial: O(|V|)

2. Complejidad del tiempo

1. Definición: árbol transversal obtenido durante el recorrido en amplitud

2. Características: Único en la matriz de adyacencia, no único en la lista de adyacencia

De manera similar al recorrido de un árbol en orden anticipado, se le da prioridad al último nodo descubierto.

1. Primero visite el vértice inicial v

2. Visite cualquier vértice adyacente no visitado w de v

3. Luego visite cualquier vértice adyacente no visitado w2 de w

4. Repita hasta que ya no pueda acceder hacia abajo y regrese sucesivamente al vértice visitado más recientemente.

1. Partiendo de un vértice, usando forma recursiva

2. Implementación del algoritmo

1. Complejidad espacial: O(|V|)

2. Complejidad del tiempo

1. Conectado: visite todos los vértices en un recorrido

2. No conectado: visite todos los vértices de los componentes conectados en un recorrido

1. Si hay una ruta desde el vértice inicial hasta cada vértice, se puede acceder a todos los vértices; de lo contrario, no

El primer bucle for inicializa los vértices a FLASE

El árbol de expansión con la suma más pequeña de pesos de aristas.

1. La forma del árbol no es única, la suma de los pesos de los bordes es única.

2. Número de aristas = número de vértices - 1

Cuando T no forma un árbol de expansión, encuentre un borde de costo mínimo y no se generará ningún bucle después de agregar T

1.Algoritmo Prim (Prim)

2.Algoritmo Kruskal (Kruskal)

1. Variables auxiliares

2. Pensamientos

3.Características

1. Pensamientos

2.Características

No hay ciclos en grafos dirigidos.

El gráfico DAG representa un proyecto, los vértices representan actividades y los bordes dirigidos <vi, vj> representan esa actividad i que debe preceder a la actividad j.

1.Definición

2. Método de implementación

3.Características

4.Atención

1.Definición

2. Dos propiedades

1. Vértice inicial (punto de origen): solo hay un vértice con grado de entrada 0, el comienzo de todo el proyecto

2. Vértice final (sumidero): solo hay un vértice con un grado de salida de 0, que es el final de todo el proyecto.

3. Ruta crítica: la ruta con la longitud máxima de ruta.

4. Actividades Críticas: Actividades en la ruta crítica

5. Tiempo mínimo: longitud del camino crítico

1. El momento de aparición más temprano Ve(k) del evento vk

2. La última hora de aparición Vl(k) del evento vk

3. El momento de aparición más temprana e(i) de la actividad ai

4. El último momento de aparición l(i) de la actividad ai

5. La diferencia de actividades d(i)=l(i)-e(i)

Las actividades con la diferencia d()=0 entre todas las actividades constituyen el camino crítico

1. Características del algoritmo

2. Ventajas y desventajas

3.Rendimiento

1. Árbol de decisión: los nodos circulares son nodos de existencia, los nodos rectangulares son nodos de falla (intervalo), n éxitos deben tener n 1 nodo de falla

2. La longitud de búsqueda para llegar al nodo fallido = el número de capas de un nodo circular encima de él

3. Sólo la falla de ASL es diferente = (1 2 ... n n)/n 1

1. Condición de bucle: bajo≤alto garantiza que todos apunten al mismo valor al final; de lo contrario, habrá un número menos para buscar.

2.mid=(low high)/2 equivale a eliminar los límites

1. Complejidad del tiempo: O (log₂n)

2.ASL: Número de capas por capa * número de nodos por capa / número de puntos de resumen, n capa tiene 2ⁿ﹣¹ nodos

1. Absorba las ventajas respectivas de la búsqueda secuencial y la búsqueda binaria, tiene una estructura dinámica y es adecuada para búsquedas rápidas.

1. Dividido en varios subbloques, los bloques se pueden desordenar y los bloques se pueden ordenar.

2. La palabra clave más grande en el primer bloque <todos los registros en el segundo bloque, y así sucesivamente.

3. Cree una tabla de índice que contenga la palabra clave más grande de cada bloque y la dirección del primer elemento de cada bloque, ordenada por palabra clave.

1. Determine el bloque en la tabla de índice y busque secuencialmente/por la mitad

2. Buscar secuencialmente dentro del bloque

ASL=tabla de índice ASL intrabloque ASL

1. La velocidad de la media búsqueda ahora es generalmente más rápida. En casos especiales, la búsqueda secuencial puede ser más rápida.

2. Rendimiento temporal de la búsqueda binaria y el árbol de clasificación binaria

3. Cuando se busca por la mitad, el valor medio está acotado

1. La altura del árbol de decisión binario: ┎log₂(n 1)┒ o ┕log₂n┙ 1

2. La longitud de bloque óptima de la tabla de secuencia de índice de n registros:

3. Búsqueda secuencial ASL=(n 1)/2, búsqueda de índice ASL=tabla de índice ASL ASL intrabloque

1. Determinar si un árbol es un árbol de decisión de búsqueda binaria.

2. Utilice una idea similar para bloquear la búsqueda directamente en la lista ordenada: W252

Método de búsqueda de 1.k puntos: la complejidad temporal del éxito y el fracaso es O (logk (n))

2. Cuando las probabilidades de búsqueda son diferentes, la forma más eficaz es utilizar la búsqueda secuencial.

0.B-tree (un árbol de búsqueda equilibrado de múltiples rutas con un factor de equilibrio de 0 para todos los nodos), el número máximo de nodos secundarios es el orden del árbol B (m)

1. Cada nodo tiene como máximo m subárboles (como máximo m-1 palabras clave)

2. Si el nodo raíz no es un nodo terminal, hay al menos dos subárboles y 1 palabra clave.

3. Todos los nodos que no son hoja, excepto el nodo raíz, tienen al menos ┎m/2┒ subárboles y al menos ┎m/2┒-1 palabras clave.

4. Todas las estructuras de nodos que no son hojas.

5. Todos los nodos hoja están al mismo nivel, sin información (nodos externos/nodos de falla)

1. Altura mínima

2. Altura máxima

Similar a un árbol de búsqueda binario

1. Posicionamiento: debe insertarse en un nodo que no sea hoja en el nivel más bajo

2.Insertar

1. En el nodo terminal

2. No en el nodo terminal

1. Cada nodo de rama tiene como máximo m subárboles (nodos secundarios)

2. El nodo raíz no hoja tiene al menos dos subárboles, y todos los nodos no hoja, excepto el nodo raíz, tienen al menos ┎m/2┒ subárboles

3. El número de subárboles de un nodo = el número de palabras clave

4. Todos los nodos hoja contienen todas las palabras clave (ordenadas) y punteros a los registros correspondientes, y los nodos hoja adyacentes están vinculados entre sí según el tamaño.

5. Todos los nodos de rama (índices que pueden considerarse índices) solo contienen el valor máximo de las palabras clave en cada uno de sus nodos secundarios y punteros a los nodos secundarios.

1. Dos punteros principales: uno apunta al nodo raíz y el otro apunta al nodo hoja con la palabra clave más pequeña.

2. Dos operaciones de búsqueda: búsqueda desde el orden mínimo de palabras clave/búsqueda multidireccional desde el nodo raíz

3. Nota: Al buscar, la búsqueda no finaliza cuando el nodo que no es hoja es igual al valor dado. La búsqueda continúa hacia abajo hasta el nodo hoja. Independientemente de si la búsqueda es exitosa o no, es una ruta desde el nodo raíz hasta el nodo hoja.

1. Cuando el número de palabras clave en un nodo ≠ el número de subárboles, no debe ser un árbol B

2. Todos los nodos que no son hoja, excepto el nodo raíz, tienen al menos ┎m/2┒ subárboles y al menos ┎m/2┒-1 palabras clave.

3. Cuando el árbol B se divide después de la inserción, siempre que el nodo raíz no se divida, la altura no será 1

1. Altura mínima: h≥logm(n 1)

2. Altura máxima: n 1≥2┎m/2┒^(h-1)

1. Para un árbol B de tercer orden: cuando el número de nodos es el más pequeño, es similar a un árbol binario completo; cuando el número de nodos es el más grande, es similar a un árbol ternario completo;

2.El árbol B se utiliza para el índice de archivos/índice de bases de datos

La función que asigna palabras clave a las direcciones correspondientes se registra como Hash(clave)=dirección (puede ser subíndice de matriz/índice/dirección de memoria)

Dos o más palabras clave diferentes se asignan a la misma dirección

Colisión de diferentes palabras clave

Una estructura de datos a la que se accede directamente en función de palabras clave, idealmente O(1)

1. El dominio de definición debe contener todas las palabras clave y el rango de valores depende del tamaño/rango de direcciones de la tabla hash.

2. Las direcciones deben ser igualmente probables y estar distribuidas uniformemente.

3. Haz la función lo más simple posible y calcúlala en poco tiempo.

1. Función: H(tecla)=a*tecla b

2. Características: sin conflictos, adecuado para una distribución básicamente continua de palabras clave

1. Función: H(tecla)=tecla%p

2. Selección de P: el número primo p que no es mayor que m (longitud de la tabla hash) pero más cercano o igual a m

1. Seleccione una cantidad de bits con una distribución digital relativamente uniforme como dirección hash

2. Características: Adecuado para colecciones de palabras clave conocidas

1. Los dígitos del medio del valor cuadrado se utilizan como dirección hash.

2. Aplicable a situaciones donde los valores de cada bit no son lo suficientemente uniformes/son menores que la cantidad de bits requeridos para la dirección hash.

1. Divida la palabra clave en varias partes con el mismo número de dígitos y tome la suma de superposición como dirección hash.

2. Adecuado para una gran cantidad de dígitos y los dígitos de cada bit están distribuidos de manera aproximadamente uniforme.

0.Definición

1. Método de detección lineal

2. Método de detección de cuadrados (método de detección secundario)

3.Método de repetición (método de doble hash)

4. Método de secuencia pseudoaleatoria

5.Atención

1. Definición: todos los sinónimos se almacenan en una lista enlazada lineal, identificada de forma única mediante una dirección hash.

2. Adecuado para situaciones frecuentes de inserción y eliminación, y puede eliminarse físicamente directamente

0.Inicialización: Dirección=Hash(clave)

1. Verifique si hay un registro en Addr

2. Calcule la "siguiente dirección hash" utilizando el método de manejo de conflictos proporcionado, establezca Addr en esta dirección y transfiérala a 1.

1. Depende de: función hash, método de manejo de colisiones, factor de carga

2. Factor de llenado (α): define qué tan llena está una tabla

3. La duración promedio de la búsqueda depende de α y no depende directamente de n o m.

1. K sinónimos se completan en la tabla hash mediante detección lineal, lo que requiere K (K 1)/2 veces de detección.

2. La probabilidad de conflicto es proporcional al tamaño del factor de carga.

3. La función hash no se puede construir utilizando una función de número aleatorio y no se pueden realizar búsquedas normales.

1. Causas de la acumulación

2. Número medio de detecciones = duración media de la búsqueda

1.Éxito en ASL

2.ASL falló

1. Similar al almacenamiento secuencial de tablas lineales, asigne matrices de longitud fija

2. Truncamiento: los valores de cadena que excedan la longitud predefinida se descartarán.

1. Utilice malloc() y free() para asignar y eliminar dinámicamente

1. Almacenamiento vinculado similar a una lista lineal, cada nodo puede contener uno o más caracteres

1.Asignación de cadena: StrAssigh

2. Comparación de cadenas: StrCompare

3. Conexión de cadena: Concat

4. Encuentra la longitud de la cuerda: StrLength

5. Buscar subcadena: SubString

1. A partir del carácter pos de la cadena principal, compárelo con el primer carácter de la cadena del patrón.

2. Si son iguales, continúe comparando los caracteres siguientes uno por uno.

3. Si no es igual, comience la comparación nuevamente desde el siguiente carácter de la cadena principal.

Peor complejidad de tiempo: O (mn)

1. Prefijo: todas las subcadenas del encabezado excepto el último carácter (solo puede comenzar desde la primera posición)

2. Sufijo: todas las subcadenas finales excepto el primer carácter (solo puede comenzar desde la última posición)

3. Valor de coincidencia parcial: las longitudes de prefijo y sufijo más largas son iguales

1. Complejidad del tiempo: O (m n)

1.siguiente valor de matriz = longitud del mismo prefijo y sufijo más largo 1

2. La cadena en sí no se puede utilizar como prefijo o sufijo.

3. Por lo general, siguiente [1] = 0 (depende de la pregunta específica, si es -1, aún use 0 para el cálculo y, finalmente, todos los números son -1)

4. Cuando el elemento i-ésimo en el siguiente [i] no coincide, la longitud de la cadena es i-1, excluyendo el elemento i-ésimo.

5. Cuando la cadena es larga, solo puedes contar las primeras para obtener la respuesta.

1.La mayor ventaja del algoritmo KMP

1. Una forma rápida de resolver next[], suponiendo que next[n] se esté resolviendo actualmente, next[n-1]=m

2.Proceso de coincidencia de KMP

1. Durante el examen, debes distinguir si el siguiente [] valor comienza en 0 o 1

1. Es posible que el algoritmo de clasificación implementado en la lista de secuencia no se implemente en la lista vinculada.

2. Si utiliza diferentes métodos de clasificación para ordenar la misma tabla lineal, los resultados de clasificación obtenidos pueden ser diferentes.

1. El número mínimo de comparaciones para ordenar n palabras clave es ┍log₂(n!)┑

1. Supongamos que el primer elemento ha sido ordenado.

2. A partir del segundo elemento, compárelo con el anterior en secuencia. Si no se satisface el intercambio inmediato, clasifique en su lugar y mueva repetidamente los elementos ya organizados hacia atrás.

1. Copie A [0] como centinela para evitar subíndices fuera de límites, facilitar la asignación y eliminar la necesidad de solicitar variables temporales.

2. Compara y mueve al mismo tiempo

1. Eficiencia del tiempo

2. Aplicabilidad

1. Primero doblar por la mitad para encontrar la posición donde se insertará el elemento.

2. Mueva todos los elementos después de la posición a insertar uniformemente

1. Solo se reduce el número de elementos de comparación y el número de movimientos no ha cambiado.

2. El número de comparaciones no tiene nada que ver con el estado inicial, solo n

1. Complejidad del tiempo: O (n²)

2. Estable

1. Primero, tome el tamaño del paso como n/2, divídalo en varios grupos y utilice la clasificación por inserción directa en cada grupo.

2. Reduzca el tamaño del paso a la mitad y continúe hasta que el tamaño del paso sea 1.

1. Aún no se ha encontrado la mejor secuencia incremental y no se puede calcular la complejidad del tiempo.

1. Eficiencia del tiempo

2. inestable

1. La complejidad temporal de la ordenación por media inserción es O (n²)

1. A partir del último elemento, compare los dos elementos adyacentes. Si están en orden inverso, intercámbielos.

2. Una operación de burbujeo dará como resultado el intercambio del elemento más pequeño a la primera posición.

3. En la siguiente ronda de burbujeo, el elemento más pequeño determinado en la ronda anterior ya no participará y la columna a ordenar se reducirá en un elemento.

4. El resultado de cada burbuja es que el elemento más pequeño de la secuencia se coloca en la posición final y se completa hasta n-1.

1. La subsecuencia ordenada generada mediante la clasificación de burbujas debe estar ordenada globalmente, lo cual es diferente de la clasificación por inserción directa.

1. Eficiencia del tiempo

1. Cada vez, el primer elemento de la tabla actual se toma como pivote base (valor de pivote) para dividir la tabla.

2.i apunta al primer elemento (base), j apunta al último elemento

3. Comience con j, busque el primer elemento más pequeño que la línea de base de atrás hacia adelante. j apunta a la posición de este elemento y reemplace el elemento señalado por i con este elemento.

4. A partir de i, busque el primer elemento más grande que la línea de base de adelante hacia atrás. i apunta a la posición de este elemento y reemplace el elemento señalado por j con este elemento.

5. Comience desde j nuevamente y repita hasta que se detenga el contacto entre i y j. Coloque el valor de referencia en la posición de contacto y divida la secuencia en dos partes. El frente es menor que el valor de referencia y el último es mayor que el valor de referencia. .

6. Tome el primer elemento de las dos subsecuencias como valor de referencia y repita la operación.

1. No se genera una subsecuencia ordenada, pero se colocará un elemento en la posición final después de cada pasada de clasificación.

2. Cuanto más ordenado sea el algoritmo, menor será la eficiencia y cuanto más desordenado sea el algoritmo, mayor será la eficiencia.

1. Eficiencia espacial

2. Eficiencia del tiempo

4. inestable

1. Cuando la subsecuencia obtenida por división recursiva es pequeña, ya no es necesaria la recursividad y se utiliza la clasificación por inserción directa para el trabajo posterior.

2. Intente elegir un punto de referencia que pueda dividir los datos.

1. La situación más rápida cuando un grupo de números se ordena mediante clasificación rápida

2. Al buscar posibles secuencias, se deben considerar ambos órdenes (de grande a pequeño, de pequeño a grande)

1. La clasificación rápida es más adecuada para el almacenamiento secuencial.

1. Algoritmo para mover todos los números impares delante de todos los números pares (mínimo tiempo/espacio)

2. Problema de la bandera holandesa: una secuencia de bloques que consta únicamente de rojo, blanco y azul, de modo que los bloques estén organizados en el orden de rojo, blanco y azul, y el tiempo es O (n)

3. Encuentre el késimo elemento más pequeño en la matriz L[1...n]

4. n números constituyen un conjunto A, que se divide en dos subconjuntos disjuntos A1 y A2. Los números son n1 y n2, y la suma de los elementos es s1 y s2. Satisfacer |n1-n2| mínimo y |s1-s2|

1. Encuentre el elemento más pequeño en la primera pasada e intercambie este elemento con el primer elemento.

1. Encuentre el elemento más pequeño en la segunda pasada, intercambie este elemento con el segundo elemento y repita n-1 veces.

1. Cada pasada de clasificación puede determinar la posición final de un elemento.

1. La complejidad del tiempo es siempre O (n²)

2. inestable

1. Definición de montón

1.1 operaciones de montón

2. Construya el montón inicial (montón raíz grande)

3. Genere el elemento superior (valor máximo) del montón, coloque el último elemento en la parte superior del montón y ajuste la parte superior del montón hacia abajo para convertirse en un montón superior grande.

4. Repita la operación hasta que solo quede un elemento en el montón.

1. La complejidad del tiempo es siempre O(n㏒₂n)

2. inestable

3. Complejidad espacial: O (1)

1. Cada elemento tiene dos elementos de datos k1 y k2. Ordene: mire primero k1, con el más pequeño primero; k1 tiene el mismo valor, luego mire k2, con el más pequeño primero.

1. Número de comparaciones al insertar/eliminar elementos del montón

2. Solo quiero obtener la secuencia ordenada parcial antes del késimo (k≥5) elemento más pequeño

3. Determinar si una secuencia de datos es un pequeño montón raíz

1. Primero divida en n subtablas con longitud 1 y combínelas en pares.

2. Obtenga las sublistas con longitud 2 y combínelas de dos en dos nuevamente, y repita

1. Complejidad espacial: O (n)

2. Complejidad del tiempo: O (n㏒₂n)

1. Menos significativo primero (LSD)

2. Bit más significativo primero (MSD)

1. Sin comparar, adopte la idea de clasificación de varias palabras clave

1. Complejidad espacial: O (r)

2. Complejidad del tiempo: O (d (n r))

3. Estable

1. ¿Qué método se debe utilizar para ordenar archivos de datos de 10 TB?

1. Fusionar dos listas ordenadas con n elementos cada una en una lista ordenada

1. ¿Cuántas comparaciones de códigos de clasificación se realizan en la clasificación por base?

1.n es más pequeño

1.1 Escala media (n<1000)

2. n es muy grande (elige el que tenga menos tiempo)

3.n es muy grande, la cantidad de palabras clave es pequeña y se puede descomponer

4. La secuencia está básicamente en orden.

5.El resultado después de varias clasificaciones.

6. Varios de los más

7.0 El tiempo del algoritmo es independiente de la secuencia inicial.

7.1 El número de pasadas de clasificación no tiene nada que ver con la secuencia inicial.

7.2 El número de movimientos no tiene nada que ver con la secuencia inicial.

La clasificación Radix no tiene nada que ver con la secuencia inicial.

8. Encuentre la estructura de datos menos eficiente

9. Si el almacenamiento secuencial se reemplaza por el almacenamiento en cadena, se reducirá la eficiencia del tiempo.

Combinado con ordenación por inserción directa: primero use la inserción directa para obtener subsecuencias ordenadas más largas y luego fusionarlas en pares, aún estables

El proceso de decisión de comparación se puede describir mediante un árbol binario, por lo que lleva al menos O (n㏒₂n) tiempo

El uso de listas vinculadas como estructuras de almacenamiento puede evitar perder mucho tiempo moviendo registros

Aumentar el número de rutas de fusión/reducir el número de segmentos de fusión

árbol perdedor

clasificación por selección de permutación

mejor árbol de fusión

1. Obtenga el segmento/cadena de serie fusionados

2. Fusione los segmentos fusionados uno por uno, de modo que los segmentos fusionados aumenten de pequeño a grande hasta que se completen.

n-el número de segmentos de fusión iniciales m-el número de rutas de fusión ┌┐-redondear hacia arriba

1. Compensa los beneficios obtenidos al reducir el número de accesos a la memoria externa debido al aumento de m.

2. No se puede utilizar la clasificación de combinación interna ordinaria

1. Nodo hoja

2. Nodos internos

3. Nodo raíz

A medida que m aumenta, el búfer de entrada aumenta, su capacidad disminuye y aumenta el número de intercambios de datos entre la memoria interna y externa.

1. Primero tome el número más pequeño a en el área de trabajo.

2. Luego, tome el número más pequeño entre los números mayores que a y colóquelo en esta sección de fusión, y el número menor que a se coloca en la siguiente sección de fusión.

1. Nodo hoja

2. Peso del nudo de la hoja.

3. Longitud del camino desde el nodo hoja hasta el nodo raíz

4.Nodos que no son hojas

5. Longitud de ruta ponderada del árbol de fusión

Deje que los segmentos de combinación con menos registros se combinen primero y los que tengan más registros se combinen al final.

1. Si el último elemento que falta no es suficiente para formar un árbol m-ario estricto, agregue un "segmento virtual" con una longitud de 0 y combínelo primero.

2. Número de segmentos de fusión vacíos = m-u-1

1. Hay n registros en total, el espacio de trabajo puede acomodar registros y se realiza una fusión equilibrada de m vías.

2,5 segmentos de combinación iniciales, cada uno con 20 registros, utilizando una combinación equilibrada de 5 vías, Número de comparaciones sin árbol perdedor y con árbol perdedor

3. Realice una fusión equilibrada de m vías, el número de buffers de entrada y salida

4. El número total de archivos de entrada/salida disponibles al mismo tiempo no supera los 15