O portador da informação é uma coleção de números, caracteres e todos os símbolos que podem ser reconhecidos e processados ​​por computadores que descrevem os atributos de coisas objetivas.

A unidade básica de dados, composta por itens de dados, a menor unidade indivisível

Uma coleção de elementos de dados com as mesmas propriedades, um subconjunto de dados

Uma coleção de valores e um conjunto de operações definidas na coleção.

1. Definição: Um modelo matemático e um conjunto de operações definidas no modelo

2. Características: A definição depende apenas do seu conjunto de características lógicas e nada tem a ver com a forma como é representado e implementado dentro do computador.

3. Representação: (objetos de dados, relacionamentos de dados, conjuntos de operações básicas)

1. Estrutura: a relação entre os elementos de dados

2. Definição: Uma coleção de elementos de dados que possuem um ou mais relacionamentos específicos entre si.

3. Conteúdo: Estrutura lógica, estrutura de armazenamento, operações de dados

1. Definição: A relação lógica entre os elementos de dados, que nada tem a ver com armazenamento e é independente do computador.

2. Classificação

1. Definição: Representação da estrutura de dados em computador (também chamada de imagem/estrutura física)

2. Incluindo: representação de elementos de dados e representação de relacionamentos

3. Classificação

1. Definição de operação: Aponte a função da operação de acordo com a estrutura lógica

2. Implementação da operação: Aponte as etapas específicas da operação de acordo com a estrutura de armazenamento.

1. Pertence a uma estrutura lógica

2. Uma fila circular é uma fila representada por uma tabela de sequência. É uma estrutura de dados, não uma estrutura de dados abstrata.

3. Os espaços de armazenamento de diferentes nós podem ser descontínuos, mas os espaços de armazenamento dentro dos nós devem ser contínuos.

4. Duas estruturas de dados diferentes, a estrutura lógica e a estrutura física podem ser exatamente iguais, mas as operações de dados são diferentes.

1. Finitude

2.Certeza

3. Viabilidade

4. Entrada

5.Saída

1. Correção

2. Legibilidade

3. Robustez

4. Eficiência e baixos requisitos de armazenamento

Definição: Mede a rapidez com que o tempo de execução de um algoritmo aumenta à medida que o tamanho do problema aumenta.

1. Definição: Mede a rapidez com que o espaço exigido pelo algoritmo aumenta à medida que o tamanho do problema aumenta.

2. O algoritmo funciona no local: o espaço auxiliar exigido pelo algoritmo é constante, ou seja, O(1)

1. Mesclar duas listas vinculadas ascendentes de comprimento m, n em uma lista vinculada descendente de m n (pegue o elemento menor, método de interpolação principal)

2. Cálculo da complexidade do tempo

3. Para o mesmo algoritmo, quanto maior o nível da linguagem implementada, menor será a eficiência de execução.

A posição inicial do espaço de armazenamento

Espaço máximo de armazenamento da tabela de sequência

O comprimento atual da tabela de sequência

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

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

1. A tabela linear deve ser uma sequência finita

2. Insira um número na i-ésima posição da tabela de sequência. O valor legal de i é: 1≤i≤n 1.

1. Inverta todos os elementos da lista de sequências

1.1 No array A[m n], existem duas tabelas de sequências com comprimentos m e n, e as posições são trocadas.

2. Lista sequencial (não ordenada) exclui todos os elementos de dados com valor x

2.1 Lista sequencial (não ordenada) exclui todos os elementos com valores entre s e t

3. A lista de sequência ordenada exclui todos os elementos entre os valores fornecidos s e t

4. Remova todos os elementos com valores duplicados da lista ordenada

4.1 Alterar lista ordenada para lista não ordenada

5. Mesclar duas listas ordenadas em uma lista ordenada e retornar o resultado pela função

6. Uma sequência ascendente S de comprimento L, a mediana é ┍L/2┑ Encontre a mediana de duas sequências ascendentes de comprimento igual A e B

7. Se o número de elementos com valor x > n/2, é chamado de elemento principal. Encontre o elemento principal de A.

8. Encontre o menor número inteiro positivo que não aparece na matriz, menos tempo

1. Independentemente de haver ou não um nó principal, o ponteiro principal sempre aponta para o primeiro nó da lista vinculada.

2. O nó principal é o primeiro nó na lista vinculada com o nó principal e geralmente não armazena informações.

1. A operação na primeira posição da lista vinculada é consistente com a operação nas demais posições.

2. Independentemente de a lista vinculada estar vazia ou não, o ponteiro principal aponta para o ponteiro não nulo do nó principal, e as listas vazias e as listas não vazias são tratadas da mesma forma

Operação de inserção direta: Encontre primeiro o nó anterior, a complexidade de tempo é O (n)

Extensão: Converta a operação de inserção direta em uma operação de inserção reversa e, em seguida, troque os dados dos dois nós. A complexidade de tempo é O (1).

Encontre primeiro o nó predecessor e, em seguida, exclua o nó, O(n)

Extensão: primeiro troque dados com o nó sucessor e, em seguida, exclua o nó sucessor, O(1)

Conte o número de nós de dados

1. Condição nula: se o ponteiro do nó principal aponta para o ponteiro principal

2. Ao operar no início e no final de uma lista vinculada individualmente: não defina o ponteiro principal e apenas defina o ponteiro final, que é mais eficiente.

3. Você pode percorrer toda a lista vinculada começando em qualquer nó

Condição nula: o campo anterior e o próximo campo do nó principal apontam para o ponteiro principal.

1. Assim como a tabela de sequência, um espaço de memória contínua deve ser alocado antecipadamente

2. A inserção e exclusão requerem apenas a modificação do ponteiro e não requerem movimentação de elementos.

3. Muito inteligente em linguagens de alto nível (Básica) que não suportam ponteiros

A lista de sequência pode ser acessada sequencialmente ou aleatoriamente. A lista vinculada só pode ser acessada sequencialmente a partir do cabeçalho.

1. Pesquise por valor

2. Pesquise por número de série

1. Considerações sobre armazenamento

2. Considerações baseadas nas operações

3. Considerações ambientais

1. A estrutura de armazenamento em cadeia é mais conveniente do que a estrutura de armazenamento sequencial para representar várias estruturas lógicas.

2. O armazenamento sequencial não pode ser usado apenas para armazenar estruturas lineares, mas também estruturas de gráficos e árvores (árvores binárias completas)

3. As listas vinculadas estáticas precisam alocar um grande espaço contínuo e a inserção e exclusão não requerem elementos móveis.

4. Se uma lista vinculada individualmente for usada para representar a fila, uma lista vinculada circular com um ponteiro final deverá ser usada.

5. Dada uma matriz unidimensional, o tempo mínimo para construir uma lista ordenada unida individualmente é O (nlog₂n)

6. As operações comumente usadas em listas vinculadas são inserir após o último elemento e excluir o primeiro elemento. A operação que economiza mais tempo é.

1. Ponteiro superior da pilha: S.top Elemento superior da pilha: S.data[S.top]

2. Empurre para a pilha: O ponteiro é primeiro incrementado em 1 e, em seguida, o valor é enviado para o elemento superior da pilha.

3. Abrir a pilha: primeiro pegue o valor do elemento no topo da pilha e, em seguida, diminua o ponteiro no topo da pilha em 1

4. Condições para julgamento vazio e julgamento completo: variam devido às diferentes condições reais.

1. Definição: Coloque os fundos das duas pilhas em ambas as extremidades do espaço compartilhado e os topos das duas pilhas se estendam em direção ao meio.

2. Julgamento em branco: top0=-1 top1=MaxSize

3. Frase completa: top1-top0=1

4. Empurre para dentro da pilha: top0 primeiro adiciona 1 e depois atribui um valor, top1 primeiro decrementa 1 e depois atribui um valor, e o oposto é verdadeiro ao sair da pilha.

1. Elemento superior da pilha

2. O próximo elemento do elemento superior da pilha

3. As condições de julgamento para pilha vazia e pilha cheia também serão alteradas.

Para aumentar sequências

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

1. A pilha e a fila têm a mesma estrutura lógica, não uma estrutura de armazenamento

2. A lista vinculada não possui um nó principal e todas as operações são realizadas no início da lista. É a pilha de links mais inadequada.

3. Insira um nó x em uma pilha de cadeia (sem o nó principal) cujo ponteiro superior está no topo

4. A sequência push é 1,2,...,n, e a sequência pop é P1, P2,...,Pn Se P2=3, o número de valores possíveis de P3 é n-1.

5. Ao reescrever um programa recursivo de forma não recursiva, a pilha pode não ser aplicável

6. As definições dos ponteiros no topo da pilha, no início da fila e no final da fila não são exclusivas. Certifique-se de revisar a questão com cuidado.

1. Determine se uma lista vinculada é centralmente simétrica

1. Dois ponteiros: front aponta para o elemento principal da fila e traseiro aponta para a próxima posição do elemento final da fila.

2. Estado inicial (equipe vazia): Q.front==Q.rear==0

3. Entre na fila: primeiro envie o valor para o último elemento da fila e depois adicione 1 ao último ponteiro da fila.

4. Desenfileirar: primeiro pegue o valor do elemento principal e, em seguida, adicione 1 ao ponteiro principal

5. Existe um falso estouro

6. Digite a descrição

1. Estado inicial (equipe vazia): Q.front==Q.rear==0

2. Avance o ponteiro frontal: Q.front=(Q.front 1)%MaxSize

3. Avance o ponteiro final da fila: Q.rear=(Q.rear 1)%MaxSize

4. Comprimento da fila: (Q.rear MaxSize-Q.front)%MaxSize

5. Distinguir entre equipes vazias e completas

1. Digite a descrição

2. Lista vinculada única com nó principal: operações unificadas de inserção e exclusão

3. Adequado para situações em que os elementos de dados mudam muito. Não há estouro de fila ou alocação de armazenamento irracional em múltiplas filas.

1. Ao usar uma fila de armazenamento encadeada para executar uma operação de exclusão, os ponteiros inicial e final podem ser modificados.

2. Na fila em cadeia, quando o elemento apontado por x entra na fila, execute a operação

1. Determine o status inicial e completo da fila circular

2. Determine a sequência que não pode ser obtida pela fila dupla restrita de entrada/saída

1. Configure uma pilha vazia e leia os parênteses sequencialmente

2. Se for ), ele será retirado da pilha se estiver emparelhado com o topo da pilha (ou é ilegal).

3. Se for ( , coloque-o na pilha como uma nova expectativa mais urgente

4. O algoritmo termina e a pilha fica vazia, caso contrário, a sequência de colchetes não corresponde

1. Adicione parênteses a todos os operadores e seus operandos de acordo com a precedência do operador (não há necessidade de adicionar parênteses se eles existirem originalmente)

2. Mova o operador após os parênteses correspondentes

3. Remova os colchetes

Nota: A expressão de prefixo coloca o operador na frente dos parênteses e os demais são iguais.

1. Números: adicionados diretamente à expressão do sufixo

2. Se for (: empurrar para empilhar

3. Se for): Adicione os operadores da pilha à expressão pós-fixada em sequência até (e exclua o (na pilha

4.Se - */

5. A travessia é concluída Se a pilha não estiver vazia, abra todos os elementos em sequência.

1. Digitalize cada termo da expressão sequencialmente

2. Operando: Empurre para a pilha

3. Operador <op>: Sai continuamente de dois operandos x e y da pilha para formar uma instrução de operação x<op>y e coloca o resultado do cálculo de volta na pilha

1. Expressão recursiva (corpo recursivo)

2. Condições de limite (saída recursiva)

1. Configure um buffer de dados de impressão, pause a saída quando estiver cheio, faça outras coisas e aguarde a impressora enviar uma solicitação

1. Organize cada solicitação em uma fila de acordo com a ordem de tempo e aloque a CPU para o primeiro usuário da fila a cada vez.

1. Matriz simétrica

2. Matriz triangular

3. Matriz tridiagonal

O número de nós filhos de um nó

O grau máximo de um nó em uma árvore

Começando no nó raiz e acumulando camada por camada, de cima para baixo.

Começando pelos nós folha e acumulando camada por camada, de baixo para cima.

O número máximo de níveis de nós na árvore

A sequência de nós passando entre dois nós

O número de arestas passadas no caminho

Os galhos da árvore são direcionados (os pais apontam para os filhos), o caminho é de cima para baixo e não há caminho entre dois filhos.

Soma das séries geométricas

1. As subárvores podem ser divididas em esquerda e direita e a ordem não pode ser invertida arbitrariamente.

2. A diferença entre uma árvore binária e uma árvore ordenada de grau 2

1. Árvore binária completa

2. Árvore binária completa

3. Árvore de classificação binária

4. Árvore binária balanceada

1.n0=n₂ 1

2. A enésima camada tem no máximo 2 ^ (n-1) nós

3. Uma árvore binária com altura h possui no máximo 2 ^ h-1 nós.

4. Para árvores binárias completas

5. A altura de uma árvore binária completa com n nós é ㏒₂n (retirado do limite) 1

1. Adequado para árvores binárias completas e árvores binárias completas

2. Geralmente, alguns nós vazios que não existem são adicionados à árvore binária.

3. Nota: Somente iniciando o armazenamento a partir do subscrito 1 da matriz as propriedades acima podem ser satisfeitas.

4. Distinguir entre armazenamento sequencial de árvores e árvores binárias

1. A lista vinculada binária possui três campos: dados, lchild, rchild

2. Uma lista vinculada binária com n nós possui n 1 campos de link vazios (o nó raiz não usa um ponteiro) para formar uma lista vinculada de dicas.

1. Pensamentos

2. Implementação de algoritmo

3. A eficiência de execução de algoritmos não recursivos é maior do que a de algoritmos recursivos

1. Pensamentos

2. Implementação de algoritmo

1. Pré-encomenda e pedido intermediário

2. Pós-pedido e pedido intermediário

3. O primeiro pedido e o último pedido não são permitidos

1. Objetivo: Agilizar a busca por predecessores e sucessores de nós

2. Regulamentos

3.Pista: Indicadores para antecessores e sucessores

4. Threading: O processo de percorrer uma árvore binária em uma determinada ordem para transformá-la em uma árvore binária encadeada.

1. A essência da pista

2. Implementação de travessia em ordem encadeada

3. Às vezes, um nó principal também é adicionado à lista vinculada de dicas para formar uma lista vinculada de dicas bidirecional.

1. Um algoritmo não recursivo para travessia de árvores binárias pode ser implementado usando árvores binárias de pistas.

2. Implementação de algoritmo

1. Definição: armazenamento em espaço contínuo, cada nó adiciona um pseudoponteiro para indicar a posição dos pais na matriz, o subscrito do nó raiz é 0 e seu pseudoponteiro é -1

2. Características: Os pais podem ser obtidos rapidamente, mas a criança deve percorrer toda a estrutura.

1. Definição: Conecte os filhos de cada nó em uma estrutura linear usando uma única lista vinculada

2. Características: É conveniente perguntar pelos filhos, mas inconveniente perguntar pelos pais.

1. Definição: O ponteiro esquerdo aponta para o primeiro filho, o ponteiro direito aponta para o primeiro irmão e a lista vinculada binária é usada como estrutura de armazenamento

2. Vantagens: Conveniente para converter árvore em árvore binária, fácil de encontrar filhos

3. Desvantagens: É difícil encontrar os pais. Será conveniente adicionar os pais para apontar para os pais.

O ponteiro esquerdo aponta para o primeiro filho, o ponteiro direito aponta para o primeiro irmão, a raiz não tem irmãos e a árvore binária não tem subárvore direita.

A raiz de cada árvore binária serve como subárvore direita da árvore binária anterior.

1. A raiz e a subárvore esquerda da árvore binária são usadas como a forma de árvore binária da primeira árvore e depois convertidas em uma árvore (o filho direito se torna um irmão)

2. A subárvore direita da raiz e seu filho esquerdo servem como a segunda árvore, e o filho direito serve como a terceira árvore, e assim por diante.

Visite a raiz primeiro e, em seguida, percorra cada subárvore da esquerda para a direita, o que é o mesmo que percorrer a raiz da árvore binária correspondente.

Percorra cada subárvore da esquerda para a direita e, em seguida, visite a raiz, que é igual à travessia da raiz intermediária da árvore binária correspondente.

O mesmo que a travessia pela raiz de uma árvore binária

Igual ao percurso raiz na árvore binária

1.Union(S,Root1,Root2): Mesclar duas subcoleções e conectar root Root2 a root Root1

2.Find(S,x): Encontre a raiz da árvore que contém x até que um número negativo seja encontrado

3.Inital(s): Cada elemento do conjunto S é inicializado como um subconjunto com apenas um único elemento (todos os elementos recebem um valor de -1)

1. As chaves de todos os nós na subárvore esquerda são menores que o nó raiz

2. As palavras-chave de todos os nós na subárvore direita são maiores que o nó raiz

3. As subárvores esquerda e direita são, cada uma, uma árvore de classificação binária.

A travessia em ordem pode obter sequência ordenada crescente

1. Implementação não recursiva, a recursão é simples, mas ineficiente

1. O novo nó inserido deve ser um nó folha (só será inserido quando a árvore estiver vazia)

1. Mesmo que os elementos inseridos sejam iguais, mas em ordens diferentes, o BST construído será diferente.

1. Nó folha: exclua diretamente

2.i tem apenas uma subárvore esquerda/direita: deixe a subárvore de i se tornar a subárvore do nó pai de i, substituindo a posição de i

3.i tem duas subárvores à esquerda e à direita: substitua i pelo sucessor/predecessor direto de i, em seguida, exclua o sucessor/predecessor direto e converta para o caso 1,2

1. Comprimento médio de pesquisa ASL = (número de cada camada * número de camadas correspondentes) / número total

2. Pior caso: semelhante à lista vinculada simples ordenada O (n)

3. Melhor caso: árvore binária balanceada O(㏒₂n)

4. Processo de pesquisa: semelhante à pesquisa binária, mas a árvore de decisão da pesquisa binária é única

1. Árvore binária balanceada: O valor absoluto da diferença de altura entre as subárvores esquerda e direita de qualquer nó não excede 1

2. Fator de equilíbrio: A diferença de altura entre as subárvores esquerda e direita do nó -1,0,1

1. O objeto de cada ajuste é a subárvore desbalanceada mínima

2. rotação balanceada LL (rotação única direita)

3.RR rotação equilibrada (rotação única esquerda)

4.Rotação balanceada LR (rotação dupla primeiro para a esquerda e depois para a direita)

5.RL rotação equilibrada (rotação dupla direita e depois esquerda)

1. A profundidade máxima de uma árvore binária balanceada contendo n nós é O(㏒₂n), e o comprimento da pesquisa balanceada é O(㏒₂n)

1. O comprimento do caminho ponderado (WPL) do nó

2. Comprimento ponderado do caminho da árvore

3. Árvore Huffman (árvore binária ideal)

1. Processo de construção

2.Recursos

1. Codificação de comprimento fixo

2. Codificação de comprimento variável

3. Codificação de prefixo

4. Processo de codificação Huffman

<v,w>: arco de v a w (v é adjacente a w/w é adjacente a v) v: cauda do arco w: cabeça do arco

(v,c)=(c,v)

Não há arestas duplicadas e não há arestas do vértice para ele mesmo.

Existem arestas duplicadas e existem arestas do vértice até ele mesmo.

1. Grafo completo não direcionado: Existem n(n-1)/2 arestas entre quaisquer dois vértices.

2. Grafo completo direcionado: quaisquer dois vértices possuem dois arcos em direções opostas, n(n-1)

Gerar subgrafo: subgrafo com o mesmo conjunto de vértices

1. Subgrafo maximamente conectado (componente conectado): Um subgrafo conectado contém todas as arestas, não necessariamente todos os vértices (não necessariamente um gráfico conectado)

2. Subgrafo minimamente conectado: um subgrafo que mantém a conectividade do gráfico enquanto minimiza o número de arestas (pode ser um único vértice)

Mínimo, máximo em relação ao lado

1. Árvore geradora de um grafo conectado; um subgrafo conectado mínimo contendo todos os vértices (n vértices têm n-1 arestas)

2. Em um grafo não conectado, a árvore geradora de componentes conectados constitui a floresta geradora do grafo não conectado.

1. Grau de um vértice: o número de arestas com o vértice como ponto final

2. Em um gráfico não direcionado: a soma dos graus de todos os vértices = número de arestas * 2

3. Em um gráfico direcionado: o grau de um vértice = grau de entrada e grau de saída, a soma dos graus de entrada de todos os vértices = a soma dos graus de saída = o número de arestas

1. Imagem ponderada (líquida): uma imagem com pesos nas laterais

1. Loop/Loop: O caminho onde o primeiro vértice e o último vértice são iguais

1. Caminho simples: um caminho no qual os vértices não aparecem repetidamente

2. Loop simples: Exceto o primeiro vértice e o último vértice, os outros vértices não aparecem repetidamente.

1. Se o caminho mais curto de v a w existir, é uma distância. Se não existir, é registrado como infinito.

1. Um gráfico direcionado no qual o grau de entrada de um vértice é 0 e o grau de entrada dos outros vértices é 1.

1. Uma matriz unidimensional armazena informações de vértice e uma matriz bidimensional armazena informações de borda.

1. Gráfico não direcionado/gráfico direcionado: O número de elementos diferentes de zero na i-ésima linha é o grau/grau externo do i-ésimo vértice

2. É fácil determinar se existem arestas, mas é difícil determinar quantas arestas existem.

3. Gráficos densos são adequados para usar matrizes de adjacência

4.Aⁿ[i][j]: O número de caminhos de comprimento n do vértice i ao vértice j

1. Combine armazenamento sequencial e vinculado para criar uma lista vinculada individualmente para cada vértice i

2. Tabela de vértices: ponteiro do campo de vértice (dados) para a primeira lista de adjacências (primeiro arco)

3. Tabela de borda: Campo de ponto de adjacência (adjvex) Campo de ponteiro apontando para a próxima lista de adjacência (nextarc)

1. Gráfico não direcionado: espaço de armazenamento O(|V| 2|E|) gráfico direcionado: O(|V| |E|)

2. Use o método de lista de adjacências para economizar espaço em gráficos esparsos

1. ArcNode: 5 domínios

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

3. Nota: os nós do vértice são armazenados sequencialmente

1. É fácil encontrar o arco com vi como cauda e o arco com vi como cabeça. É fácil encontrar o grau de saída/entrada do vértice.

2. Significa que não é único, mas determina um gráfico.

1. Cada aresta é representada por um nó

2. O vértice é representado por um nó

1. As arestas anexadas ao mesmo vértice são conectadas na mesma lista vinculada e cada nó da aresta é vinculado em duas listas vinculadas ao mesmo tempo.

2. Cada aresta possui apenas um nó

Um algoritmo de passagem hierárquica semelhante a uma árvore binária, dando prioridade ao primeiro nó descoberto.

1. Primeiro visite o vértice inicial v

2. Visite todos os vértices adjacentes não visitados de v em sequência

3. Em seguida, comece a partir desses vértices e visite todos os seus nós não visitados.

1. Pesquisa hierárquica, acessando um lote de nós para frente, ao contrário da busca em profundidade, onde há uma situação inversa, não é recursiva

2. Use a matriz de marcas auxiliares da fila (se o vértice é visitado)

3. Implementação de algoritmo

1. Complexidade do espaço: O(|V|)

2. Complexidade de tempo

1. Definição: Uma árvore transversal obtida durante a travessia em largura

2. Características: Único na matriz de adjacência, não único na lista de adjacência

Semelhante à travessia de pré-ordem de uma árvore, o último nó descoberto recebe prioridade.

1. Primeiro visite o vértice inicial v

2. Visite qualquer vértice adjacente não visitado w de v

3. Em seguida, visite qualquer vértice adjacente não visitado w2 de w

4. Repita até que você não consiga mais acessar para baixo e retornar ao vértice visitado mais recentemente.

1. Partindo de um vértice, usando forma recursiva

2. Implementação de algoritmo

1. Complexidade do espaço: O(|V|)

2. Complexidade de tempo

1. Conectado: visite todos os vértices em uma travessia

2. Não conectado: visite todos os vértices de componentes conectados em uma travessia

1. Se houver um caminho do vértice inicial para cada vértice, todos os vértices poderão ser acessados, caso contrário não será possível

O primeiro loop for inicializa os vértices para FLASE

A árvore geradora com a menor soma de pesos de aresta

1. A forma da árvore não é única, a soma dos pesos das arestas é única

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

Quando T não forma uma árvore geradora, encontre uma aresta de custo mínimo e nenhum loop será gerado após adicionar T

1.Algoritmo Prim (Prim)

2.Algoritmo Kruskal (Kruskal)

1. Variáveis ​​auxiliares

2. Pensamentos

3.Recursos

1. Pensamentos

2.Recursos

Não há ciclos em gráficos direcionados

O gráfico DAG representa um projeto, os vértices representam atividades e as arestas direcionadas <vi, vj> representam que a atividade i deve preceder a atividade j

1.Definição

2. Método de implementação

3.Recursos

4.Atenção

1.Definição

2. Duas propriedades

1. Vértice inicial (ponto de origem): Existe apenas um vértice com grau 0, o início de todo o projeto

2. Vértice final (sink): Existe apenas um vértice com grau de saída 0, que é o final de todo o projeto.

3. Caminho crítico: o caminho com o comprimento máximo

4. Atividades Críticas: Atividades no caminho crítico

5. Tempo mínimo: comprimento do caminho crítico

1. O primeiro tempo de ocorrência Ve(k) do evento vk

2. O último horário de ocorrência Vl(k) do evento vk

3. O primeiro momento de ocorrência e(i) da atividade ai

4. O último horário de ocorrência l(i) da atividade ai

5. A diferença nas atividades d(i)=l(i)-e(i)

As atividades com diferença d()=0 entre todas as atividades constituem o caminho crítico

1. Características do algoritmo

2. Vantagens e Desvantagens

3.Desempenho

1. Árvore de decisão: nós circulares são nós de existência, nós retangulares são nós de falha (intervalo), n sucessos devem ter n 1 nós de falha

2. O comprimento da pesquisa para alcançar o nó com falha = o número de camadas de um nó circular acima dele

3. Apenas a falha ASL é diferente = (1 2 ... n n)/n 1

1. Condição do loop: baixo≤alto garante que todos apontem para o mesmo valor no final, caso contrário, haverá um número a menos para pesquisar.

2.mid=(low high)/2 é equivalente a remover os limites

1. Complexidade de tempo: O(log₂n)

2.ASL: Número de camadas por camada * número de nós por camada / número de pontos de resumo, n camada tem 2ⁿ﹣¹ nós

1. Absorvem as respectivas vantagens da pesquisa sequencial e da pesquisa binária, possuem uma estrutura dinâmica e são adequadas para pesquisa rápida.

1. Divididos em vários subblocos, os blocos podem ser desordenados e os blocos podem ser ordenados.

2. A maior palavra-chave no primeiro bloco <todos os registros no segundo bloco e assim por diante

3. Crie uma tabela de índice contendo a maior palavra-chave de cada bloco e o endereço do primeiro elemento de cada bloco, organizados em ordem por palavra-chave

1. Determine o bloco na tabela de índices e pesquise sequencialmente/pela metade

2. Pesquise sequencialmente dentro do bloco

ASL = tabela de índice ASL intra-bloco ASL

1. A velocidade da meia pesquisa agora é geralmente mais rápida. Em casos especiais, a pesquisa sequencial pode ser mais rápida.

2. Desempenho temporal da pesquisa binária e da árvore de classificação binária

3. Ao pesquisar pela metade, o valor do meio é limitado

1. A altura da árvore de decisão binária: ┎log₂(n 1)┒ ou ┕log₂n┙ 1

2. O comprimento ideal do bloco da tabela de sequência de índice de n registros:

3. Pesquisa sequencial ASL=(n 1)/2, pesquisa de índice ASL=tabela de índice ASL intra-bloco ASL

1. Determine se uma árvore é uma árvore de decisão de pesquisa binária

2. Use uma ideia semelhante para bloquear a pesquisa diretamente na lista ordenada: W252

Método de pesquisa de 1.k pontos: A complexidade de tempo de sucesso e falha é O (logk (n))

2. Quando as probabilidades de pesquisa são diferentes, a forma mais eficaz é usar a pesquisa sequencial

0.B-tree (uma árvore de pesquisa balanceada de múltiplos caminhos com um fator de equilíbrio de 0 para todos os nós), o número máximo de nós filhos é a ordem da árvore B (m)

1. Cada nó possui no máximo m subárvores (no máximo m-1 palavras-chave)

2. Se o nó raiz não for um nó terminal, existem pelo menos duas subárvores e 1 palavra-chave

3. Todos os nós não-folha, exceto o nó raiz, têm pelo menos ┎m/2┒ subárvores e pelo menos ┎m/2┒-1 palavras-chave.

4. Todas as estruturas de nós não-folha

5. Todos os nós folha estão no mesmo nível, sem informações (nós externos/nós com falha)

1. Altura mínima

2. Altura máxima

Semelhante a uma árvore de pesquisa binária

1. Posicionamento: deve ser inserido em um nó não folha no nível mais baixo

2.Inserir

1. No nó terminal

2. Não no nó terminal

1. Cada nó de ramificação possui no máximo m subárvores (nós filhos)

2. O nó raiz não folha tem pelo menos duas subárvores, e todos os nós não folha, exceto o nó raiz, têm pelo menos ┎m/2┒ subárvores

3. O número de subárvores de um nó = o número de palavras-chave

4. Todos os nós folha contêm todas as palavras-chave (organizadas em ordem) e ponteiros para os registros correspondentes, e os nós folha adjacentes são vinculados entre si de acordo com o tamanho.

5. Todos os nós de ramificação (índices que podem ser considerados índices) contêm apenas o valor máximo das palavras-chave em cada um de seus nós filhos e ponteiros para os nós filhos.

1. Dois ponteiros principais: um aponta para o nó raiz e o outro aponta para o nó folha com a menor palavra-chave

2. Duas operações de pesquisa: pesquisa a partir da ordem mínima de palavras-chave/pesquisa multidirecional a partir do nó raiz

3. Nota: Ao pesquisar, a pesquisa não termina quando o nó não folha é igual ao valor fornecido. A pesquisa continua descendente até o nó folha. Independentemente de a pesquisa ser bem-sucedida ou não, é um caminho do nó raiz até o nó folha.

1. Quando o número de palavras-chave em um nó ≠ o número de subárvores, não deve ser uma árvore B

2. Todos os nós não-folha, exceto o nó raiz, têm pelo menos ┎m/2┒ subárvores e pelo menos ┎m/2┒-1 palavras-chave.

3. Quando a árvore B é dividida após a inserção, desde que o nó raiz não seja dividido, a altura não será 1

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

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

1. Para uma árvore B de terceira ordem: quando o número de nós é menor, é semelhante a uma árvore binária completa; quando o número de nós é maior, é semelhante a uma árvore ternária completa;

A árvore 2.B é usada para índice de arquivo/índice de banco de dados

A função que mapeia palavras-chave para endereços correspondentes é registrada como Hash(key)=addr (pode ser subscrito/índice/endereço de memória da matriz)

Duas ou mais palavras-chave diferentes são mapeadas para o mesmo endereço

Colisão de palavras-chave diferentes

Uma estrutura de dados que é acessada diretamente com base em palavras-chave, de preferência O(1)

1. O domínio de definição deve conter todas as palavras-chave e o intervalo de valores depende do tamanho/intervalo de endereços da tabela hash

2. Os endereços devem ser igualmente prováveis ​​e distribuídos uniformemente.

3. Torne a função o mais simples possível e calcule-a em pouco tempo

1. Função: H(chave)=a*chave b

2. Recursos: Sem conflito, adequado para distribuição basicamente contínua de palavras-chave

1. Função: H(chave)=chave%p

2. Seleção de P: O número primo p que não é maior que m (comprimento da tabela hash), mas mais próximo ou igual a m

1. Selecione um número de bits com uma distribuição digital relativamente uniforme como endereço hash

2. Recursos: Adequado para coleções de palavras-chave conhecidas

1. Os dígitos do meio do valor quadrado são usados ​​como endereço hash

2. Aplicável a situações em que os valores de cada bit não são suficientemente uniformes/são inferiores ao número de bits necessários para o endereço hash.

1. Divida a palavra-chave em várias partes com o mesmo número de dígitos e tome a soma da superposição como endereço hash.

2. Adequado para um grande número de dígitos e os dígitos em cada bit são distribuídos de maneira aproximadamente uniforme.

0.Definição

1. Método de detecção linear

2. Método de detecção quadrada (método de detecção secundário)

3. Método de rehashing (método de hash duplo)

4. Método de sequência pseudo-aleatória

5.Atenção

1. Definição: Todos os sinônimos são armazenados em uma lista linear vinculada, identificada exclusivamente por um endereço hash

2. Adequado para situações frequentes de inserção e exclusão e pode ser excluído fisicamente diretamente

0.Inicialização: Addr=Hash(chave)

1. Verifique se existe um registro no Addr

2. Calcule o "próximo endereço hash" usando o método de tratamento de conflitos fornecido, defina Addr para este endereço e transfira para 1

1. Depende de: função hash, método de tratamento de colisões, fator de carga

2. Fator de preenchimento (α): Define o quão cheia uma tabela está

3. O comprimento médio da pesquisa depende de α e não depende diretamente de n ou m.

1. K sinônimos são preenchidos na tabela hash usando detecção linear, que requer K (K 1)/2 vezes de detecção.

2. A probabilidade de conflito é proporcional ao tamanho do fator de carga

3. A função hash não pode ser construída usando uma função de número aleatório e pesquisas normais não podem ser realizadas.

1. Causas de acumulação

2. Número médio de detecções = duração média da pesquisa

1.Sucesso ASL

2.ASL falhou

1. Semelhante ao armazenamento sequencial de tabela linear, aloque matrizes de comprimento fixo

2. Truncamento: Valores de string que excedam o comprimento predefinido serão descartados.

1. Use malloc() e free() para alocar e excluir dinamicamente

1. Armazenamento vinculado semelhante a uma lista linear, cada nó pode conter um ou mais caracteres

1. Atribuição de string: StrAssigh

2. Comparação de strings: StrCompare

3. Conexão de string: Concat

4. Encontre o comprimento da string: StrLength

5. Encontre substring: SubString

1. Começando pelo caractere pos da string principal, compare-o com o primeiro caractere da string padrão

2. Se forem iguais, continue a comparar os caracteres subsequentes um por um.

3. Se não for igual, inicie a comparação novamente a partir do próximo caractere da string principal.

Pior complexidade de tempo: O(mn)

1. Prefixo: todas as substrings do cabeçalho, exceto o último caractere (só pode começar na primeira posição)

2. Sufixo: todas as substrings finais, exceto o primeiro caractere (só pode começar na última posição)

3. Valor de correspondência parcial: os comprimentos mais longos do prefixo e do sufixo são iguais

1. Complexidade de tempo: O(m n)

1.próximo valor da matriz = mesmo comprimento de prefixo e sufixo mais longo 1

2. A string em si não pode ser usada como prefixo ou sufixo.

3. Geralmente next[1]=0 (depende da questão específica, se for -1, ainda use 0 para cálculo e, finalmente, todos os números são -1)

4. Quando o i-ésimo elemento em next[i] não corresponde, o comprimento da string é i-1, excluindo o i-ésimo elemento.

5. Quando a sequência for longa, você só poderá contar as primeiras para obter a resposta.

1.A maior vantagem do algoritmo KMP

1. Uma maneira rápida de resolver next[], assumindo que next[n] esteja sendo resolvido no momento, next[n-1]=m

2. Processo de correspondência KMP

1. Durante o exame, você deve distinguir se o valor next[] começa em 0 ou 1

1. O algoritmo de classificação implementado na lista de sequências não pode ser implementado na lista vinculada.

2. Se você usar métodos de classificação diferentes para classificar a mesma tabela linear, os resultados de classificação obtidos poderão ser diferentes.

1. O número mínimo de comparações para classificar quaisquer n palavras-chave é ┍log₂(n!)┑

1. Suponha que o primeiro elemento foi classificado

2. A partir do segundo elemento, compare-o com o anterior em sequência. Se a troca imediata não for satisfeita, classifique no lugar e mova repetidamente os itens já organizados para trás.

1. Copie A[0] como sentinela para evitar subscritos fora dos limites, facilitar a atribuição e eliminar a necessidade de aplicar variáveis ​​temporárias.

2. Compare e mova-se ao mesmo tempo

1. Eficiência de tempo

2. Aplicabilidade

1. Primeiro dobre ao meio para encontrar a posição onde o elemento será inserido.

2. Mova todos os elementos após a posição a ser inserida uniformemente

1. Apenas o número de elementos de comparação foi reduzido, o número de movimentos não mudou

2. O número de comparações não tem nada a ver com o estado inicial, apenas n

1. Complexidade de tempo: O(n²)

2. Estável

1. Primeiro considere o tamanho do passo como n/2, divida-o em vários grupos e use a classificação por inserção direta em cada grupo.

2. Reduza o tamanho do passo pela metade e continue até que o tamanho do passo seja 1

1. A melhor sequência incremental ainda não foi encontrada e a complexidade do tempo não pode ser calculada.

1. Eficiência de tempo

2. Instável

1. A complexidade de tempo da classificação de meia inserção é O (n²)

1. A partir do último elemento, compare os dois elementos adjacentes. Se estiverem na ordem inversa, troque-os.

2. Uma operação de bolha resultará na troca do menor elemento para a primeira posição.

3. Na próxima rodada de borbulhamento, o menor elemento determinado na rodada anterior não participará mais e a coluna a ser ordenada será reduzida em um elemento.

4. O resultado de cada bolha é que o menor elemento da sequência é colocado na posição final e até n-1 é concluído.

1. A subsequência ordenada gerada pela classificação por bolha deve ser ordenada globalmente, o que é diferente da classificação por inserção direta.

1. Eficiência de tempo

1. Cada vez, o primeiro elemento da tabela atual é considerado o pivô base (valor do pivô) para dividir a tabela.

2.i aponta para o primeiro elemento (base), j aponta para o último elemento

3. Comece com j e encontre o primeiro elemento menor que a linha de base de trás para frente j aponta para a posição deste elemento e substitua o elemento apontado por i por este elemento.

4. A partir de i, encontre o primeiro elemento maior que a linha de base da frente para trás i aponta para a posição deste elemento e substitua o elemento apontado por j por este elemento.

5. Comece de j novamente e repita até que o contato entre i e j pare. Coloque o valor de referência na posição de contato e divida a sequência em duas partes. A frente é menor que o valor de referência e a última é maior que o valor de referência. .

6. Tome o primeiro elemento das duas subsequências como valor de referência e repita a operação.

1. Nenhuma subsequência ordenada é gerada, mas um elemento será colocado na posição final após cada passagem de classificação

2. Quanto mais ordenado for o algoritmo, menor será a eficiência, e quanto mais desordenado for o algoritmo, maior será a eficiência.

1. Eficiência de espaço

2. Eficiência de tempo

4. Instável

1. Quando a subsequência obtida pela divisão recursiva é pequena, a recursão não é mais necessária e a classificação por inserção direta é usada para o trabalho subsequente.

2. Tente escolher um benchmark que possa dividir os dados.

1. A situação mais rápida quando um grupo de números é classificado usando classificação rápida

2. Ao procurar sequências possíveis, ambas as ordens devem ser consideradas (do grande para o pequeno, do pequeno para o grande)

1. A classificação rápida é mais adequada para armazenamento sequencial.

1. Algoritmo para mover todos os números ímpares na frente de todos os números pares (menos tempo/espaço)

2. Problema da bandeira holandesa: uma sequência de blocos consistindo apenas de vermelho, branco e azul, de modo que os blocos sejam organizados na ordem de vermelho, branco e azul, e o tempo seja O(n)

3. Encontre o k-ésimo menor elemento na matriz L[1...n]

4. N números constituem um conjunto A, que é dividido em dois subconjuntos disjuntos A1 e A2. Os números são n1 e n2, e a soma dos elementos é s1 e s2. Satisfaça |n1-n2| mínimo e |s1-s2|

1. Encontre o menor elemento na primeira passagem e troque este elemento pelo primeiro elemento

1. Encontre o menor elemento na segunda passagem, troque este elemento pelo segundo elemento e repita n-1 vezes

1. Cada passagem de classificação pode determinar a posição final de um elemento.

1. A complexidade do tempo é sempre O(n²)

2. Instável

1. Definição de pilha

1.1 Operações de heap

2. Construa o heap inicial (heap raiz grande)

3. Produza o elemento superior (valor máximo) do heap, coloque o último elemento no topo do heap e ajuste o topo do heap para baixo para se tornar um grande heap superior.

4. Repita a operação até que reste apenas um elemento na pilha

1. A complexidade do tempo é sempre O(n㏒₂n)

2. Instável

3. Complexidade do espaço: O(1)

1. Cada elemento possui dois itens de dados k1 e k2. Classificar: olhe primeiro para k1, com o menor primeiro tendo o mesmo valor, depois olhe para k2, com o menor primeiro;

1. Número de comparações ao inserir/excluir elementos do heap

2. Só quero obter a sequência ordenada parcial antes do k-ésimo (k≥5) menor elemento

3. Determine se uma sequência de dados é um pequeno heap raiz

1. Primeiro divida em n subtabelas com comprimento 1 e mescle-as em pares.

2. Obtenha as sublistas com comprimento 2 e mescle-as duas a duas novamente e repita

1. Complexidade do espaço: O(n)

2. Complexidade de tempo: O(n㏒₂n)

1. Menos Significativo Primeiro (LSD)

2. Primeiro o bit mais significativo (MSD)

1. Não baseado em comparação, adote a ideia de classificação multi-palavras-chave

1. Complexidade espacial: O(r)

2. Complexidade de tempo: O(d(n r))

3. Estável

1. Qual método deve ser usado para classificar arquivos de dados de 10 TB?

1. Mesclar duas listas ordenadas com n elementos cada em uma lista ordenada

1. Quantas comparações de código de classificação são realizadas na classificação radix?

1.n é menor

1.1 Média escala (n<1000)

2. n é muito grande (escolha aquele com menos tempo)

3.n é muito grande, o número de palavras-chave é pequeno e pode ser decomposto

4. A sequência está basicamente em ordem

5.O resultado após várias classificações

6. Vários dos mais

7.0 O tempo do algoritmo é independente da sequência inicial

7.1 O número de passagens de classificação não tem nada a ver com a sequência inicial

7.2 O número de movimentos não tem nada a ver com a sequência inicial

A classificação Radix não tem nada a ver com a sequência inicial

8. Encontre a estrutura de dados menos eficiente

9. Se o armazenamento sequencial for substituído pelo armazenamento em cadeia, a eficiência do tempo será reduzida.

Combinado com classificação por inserção direta: primeiro use a inserção direta para obter subsequências ordenadas mais longas e depois mescle-as em pares, ainda estáveis

O processo de decisão de comparação pode ser descrito por uma árvore binária, portanto leva pelo menos O(n㏒₂n) tempo

Usar listas vinculadas como estruturas de armazenamento pode evitar gastar muito tempo movendo registros

Aumentar o número de caminhos de mesclagem/reduzir o número de segmentos de mesclagem

árvore perdedora

classificação de seleção de permutação

melhor árvore de mesclagem

1. Obtenha o segmento/string serial mesclado

2. Mescle os segmentos mesclados um por um, de modo que os segmentos mesclados aumentem de pequeno para grande até serem concluídos.

n-o número de segmentos iniciais de fusão m-o número de caminhos de fusão ┌┐-arredondado

1. Compensa os benefícios obtidos com a redução do número de acessos à memória externa devido ao aumento de m.

2. A classificação por mesclagem interna comum não pode ser usada

1. Nó folha

2. Nós internos

3. Nó raiz

À medida que m aumenta, o buffer de entrada aumenta, sua capacidade diminui e o número de trocas de dados entre a memória interna e externa aumenta.

1. Primeiro pegue o menor número a na área de trabalho

2. Em seguida, pegue o menor número entre os números maiores que a e coloque-o nesta seção de mesclagem, e o número menor que a é colocado na próxima seção de mesclagem.

1. Nó folha

2. Peso do nó folha

3. Comprimento do caminho do nó folha ao nó raiz

4. Nós não-folha

5. Comprimento do caminho ponderado da árvore de mesclagem

Deixe que os segmentos de mesclagem com menos registros sejam mesclados primeiro e aqueles com mais registros sejam mesclados por último.

1. Se o último item faltante não for suficiente para formar uma árvore m-ária estrita, adicione um "segmento virtual" com comprimento 0 e mescle-o primeiro.

2. Número de segmentos de mesclagem vazios = m-u-1

1. Há n registros no total, o espaço de trabalho pode acomodar registros e a mesclagem balanceada de m vias é executada.

2,5 segmentos de mesclagem iniciais, cada um com 20 registros, usando mesclagem balanceada de 5 vias, Número de comparações sem árvore perdedora e com árvore perdedora

3. Faça a fusão balanceada m-way, o número de buffers de entrada e saída

4. O número total de arquivos de entrada/saída disponíveis ao mesmo tempo não excede 15