Estruturas de Dados e Algoritmos Flashcards
O que é busca sequencial?
É um algoritmo que percorre cada elemento de uma estrutura linear (como um vetor) até encontrar o valor desejado ou atingir o final da estrutura.
Qual a complexidade de tempo da busca sequencial?
O(n)
Quando é vantajoso usar busca sequencial?
Quando a estrutura é pequena ou não está ordenada.
Qual é o pré-requisito para usar a busca binária?
A estrutura de dados precisa estar ordenada.
Como funciona a busca binária?
Divide o intervalo de busca ao meio a cada passo, comparando o valor do meio com o valor buscado.
Qual a complexidade de tempo da busca binária?
O(log n), onde n é o número de elementos.
Na busca binária, o que acontece se o valor buscado não estiver na estrutura?
Os limites do intervalo se cruzam, indicando que o valor não está presente.
Como funciona o Bubble Sort?
Compara pares adjacentes de elementos e os troca de posição se estiverem na ordem errada, repetindo até que o vetor esteja ordenado. (isso faz com que a cada iteração o elemento mais alto da lista acabe no final dela “subindo como uma bolha”)
Qual a complexidade de tempo do Bubble Sort no pior caso?
O(n²)
Como funciona o Selection Sort?
Encontra o menor elemento da parte não ordenada do vetor e o coloca na posição correta (início do vetor), repetindo esse processo para todos os elementos.
Qual a complexidade de tempo do Selection Sort?
O(n²) em todos os casos (melhor, médio e pior).
Qual é a vantagem do Selection Sort?
Realiza o mínimo possível de trocas: no máximo n - 1.
Como funciona o Insertion Sort?
Insere cada elemento na posição correta da parte já ordenada do vetor, como se estivesse organizando cartas na mão.
Qual a complexidade do Insertion Sort no pior caso?
O(n²), quando o vetor está em ordem inversa.
O que é uma lista encadeada?
É uma estrutura de dados composta por nós, onde cada nó armazena um valor e uma referência (ponteiro) para o próximo nó.
Quais são as vantagens de uma lista encadeada em relação a um vetor?
Inserções e remoções em qualquer posição são mais eficientes, pois não é necessário realocar a estrutura.
Quais são os tipos principais de listas encadeadas?
Simples, duplamente encadeada e circular.
O que é uma pilha?
É uma estrutura de dados do tipo LIFO (Last In, First Out), onde o último elemento inserido é o primeiro a ser removido.
Quais são as principais operações de uma pilha?
push (inserir), pop (remover) e peek ou top (ver o topo da pilha).
O que é uma fila?
É uma estrutura de dados do tipo FIFO (First In, First Out), onde o primeiro elemento inserido é o primeiro a sair.
Quais são as operações básicas de uma fila?
enqueue (inserir no final) e dequeue (remover do início).
O que é uma fila circular?
É uma implementação otimizada de fila onde o último elemento se conecta ao primeiro, reaproveitando espaço.
O que é uma árvore binária?
É uma estrutura hierárquica onde cada nó possui no máximo dois filhos: esquerdo e direito.
Quais são os principais tipos de árvore binária?
Árvore binária comum, árvore binária de busca (BST), árvore balanceada (AVL), árvore completa, árvore cheia.
O que caracteriza uma árvore binária de busca (BST)?
Para cada nó, os valores à esquerda são menores e os valores à direita são maiores.
Quais são os principais percursos em uma árvore binária?
Pré-ordem (preorder), em ordem (inorder), pós-ordem (postorder) e em largura (BFS).
Qual a complexidade média de busca, inserção e remoção em uma BST?
O(log n), mas no pior caso (desequilibrada), pode chegar a O(n).
