Estrutura de dados

• Qual a diferença de acesso a elementos entre um Array e uma Lista Encadeada?

O Array permite acesso direto/aleatório via índice em O(1) A Lista Encadeada permite apenas acesso sequencial (percorrendo nó por nó) em O(n)

É eficiente realizar Busca Binária em uma Lista Encadeada ordenada? Por quê?

Não, pois a lista encadeada não suporta acesso direto ao elemento central em O(1). A busca nela será sempre Sequencial O(n)

• Quais as vantagens e desvantagens de uso de memória de uma Lista Encadeada frente a um Array?

• Vantagem: Inserção/remoção dinâmica rápida no início/fim da lista em O(1) sem precisar realocar a estrutura inteira.

• Desvantagem: Consome mais memória, pois cada nó precisa armazenar o dado físico mais o ponteiro de referência (next) para o próximo elemento

Quais sequencias são seguidas pela Pilha e pela Fila.

Pilha: (Letras alternadas):

LIFO(Last in first out)

FILO(First in last out)

Fila: (Letra repetidas):

FIFO(First in first out)

LILO(Last in last out)

• O que é: Uma estrutura linear onde você pode inserir e remover elementos tanto no início quanto no fim (ela quebra a regra rígida de que Fila só insere no fim e remove no início).

• Nomes das operações: insertFront(), insertLast(), deleteFront(), deleteLast().

Uma lista sequencial pode ser implementada de forma estática em

Array, vetores ou arranjos

O percurso In-ordem (Ordem Simétrica) pode ser aplicado de forma padrão em uma Árvore Geral (com N filhos)?

• Não. O percurso In-ordem (Esquerda —→ Raiz ——→ Direita) exige uma divisão binária estrita para posicionar a raiz no meio. Árvores gerais utilizam apenas Pré-ordem, Pós-ordem ou Varredura em Largura.

Qual a principal limitação física de uma Árvore Binária?

Cada nó pode possuir, no máximo, 2 nós filhos (grau de saída 0, 1 ou 2).

Em qual percurso a Raiz é visitada entre as subárvores?

In-ordem (Ordem Simétrica): Esquerda → Raiz → Direita. É de uso exclusivo em árvores binárias.

O que acontece se lermos uma Árvore Binária de Busca (BST) em Ordem Simétrica?

Os elementos serão listados em ordem crescente exata.

Qual o percurso de árvore cuja raiz principal é o último nó processado?

Pós-ordem (Esquerda → Direita → Raiz)

O que é uma árvore binária de busca degenerada?

Uma árvore sem balanceamento que se assemelha a uma lista encadeada sequencial, elevando a complexidade de busca para O(n)

Qual a complexidade de busca e inserção em uma árvore AVL no pior caso?

O(log n), devido ao seu sistema ativo de balanceamento via rotações.

Qual estrutura de dados auxiliar é usada para implementar a busca Em Largura?

Uma Fila auxiliar (comportamento FIFO).

Quais são os tipos de árvore binária e suas respectivas notações BiG O

Busca binária.(BST) e

Árvore AVL / Vermelho-Preto

Qual o único algoritmo de ordenação quadrático (O(n^2)) que possui complexidade de melhor caso linear (O(n)) quando o vetor já está ordenado?

Insertion Sort (ele apenas varre o vetor confirmando que já está ordenado).

Qual a complexidade de tempo (Melhor, Médio e Pior caso) do Selection Sort?

O(n^2) em todos os casos (ele sempre varre o vetor inteiro buscando o menor elemento, independente do estado inicial dos dados).

O que significa dizer que um algoritmo de ordenação é Estável (como o Bubble e o Insertion)?

Significa que ele preserva a ordem original de elementos que possuem chaves com valores iguais.

Dentre os algoritmos quadráticos simples (Bubble, Selection e Insertion), qual deles NÃO é estável?

Selection Sort.

Qual a complexidade de tempo (Melhor, Médio e Pior caso) do Merge Sort?

O(n log n) em todos os casos (divisão e conquista pura).

Qual a complexidade de pior caso do Quick Sort e quando ela ocorre?

• O(n^2). Ocorre quando o pivô escolhido é pessimamente posicionado (geralmente o maior ou menor elemento de um vetor já ordenado ou inversamente ordenado).

Qual o ponto fraco do Merge Sort em termos de complexidade de espaço?

Ele exige memória auxiliar de O(n) para fazer a fusão dos subvetores (não é In-place).

Qual algoritmo de ordenação avançada garante tempo O(n log n) no pior caso e consumo de espaço auxiliar constante O(1) (In-place)?

Heap Sort.

É possível aplicar de forma eficiente a Busca Binária em uma Lista Encadeada Ordenada?

NÃO! A busca binária requer Acesso Direto (por índice) em O(1) para achar o elemento do meio. Na lista encadeada, o acesso é sequencial O(n), o que destruiria a eficiência do algoritmo.

Qual o único algoritmo de busca que funciona em dados não ordenados?

A Busca Sequencial (Linear). Ela varre elemento por elemento, não exigindo qualquer organização prévia da estrutura de dados.

Qual a complexidade do algoritmo Insertion Sort no melhor caso (vetor já ordenado)?

É O(n) (tempo linear). Ele realiza apenas n-1 comparações e nenhuma movimentação/troca física de dados

Qual a complexidade do algoritmo Selection Sort no melhor caso? Por quê?

É O(n^2 ) (quadrática). O Selection Sort faz uma varredura cega para achar o menor elemento a cada iteração, sendo incapaz de aproveitar se o vetor já estiver ordenado.

Qual a principal vantagem de processamento do algoritmo Merge Sort e sua principal desvantagem física?

• Vantagem: Garante tempo de execução O(n log n) mesmo no pior caso e é estável.

• Desvantagem: Não é In-place, exigindo O(n) de espaço de memória auxiliar.

Em qual cenário o algoritmo Quick Sort atinge o seu pior caso de complexidade O(n^2 )?

Quando o elemento escolhido como pivô é péssimo (geralmente o menor ou o maior elemento) em um vetor que já está ordenado ou inversamente ordenado, forçando divisões totalmente desbalanceadas.

O que significa dizer que um algoritmo de ordenação é Estável?

Significa que ele preserva a ordem relativa original de elementos que possuem chaves de ordenação com valores idênticos.

Qual algoritmo garante complexidade temporal de O(n log n) no pior caso consumindo apenas O(1) de memória auxiliar?

O Heap Sort. Ele une a garantia temporal do Merge Sort com a economia de espaço de memória do Selection/Insertion Sort.

Qual a diferença da Busca linear otimizada pra normal e com lista desordenada?

A otimizada assim que encontra um valor maior que o buscado, encerra a pesquisa. pior caso O(n). melhor caso O(1).

caso a lista esteja desordenada vai percorrer todos os elementos sendo assim, sempre O(n)

Como se comporta o número de comparações por rodada no Insertion Sort à medida que o algoritmo avança?

• O número de comparações (no pior caso) aumenta a cada rodada (começa em apenas 1 e pode chegar até N-1), pois a sublista ordenada da esquerda vai crescendo e o elemento a ser inserido tem cada vez mais cartas para comparar.

Como se comporta o número de comparações por rodada no Selection e no Bubble Sort à medida que o algoritmo avança?

O número de comparações diminui a cada rodada (começa em N-1 e vai caindo até 1), pois a área não ordenada do vetor vai encolhendo a cada elemento fixado no seu lugar definitivo.

No Bubble Sort, qual é o gatilho físico que determina o fim de uma rodada principal (iteração do loop externo)?

A rodada principal acaba quando o maior elemento restante ("coelho") flutua através de trocas consecutivas de vizinhos adjacentes e se assenta no seu lugar definitivo à direita (atingindo o limite matemático programado para aquela rodada: N - 1 - i).

No Selection Sort, qual é o gatilho físico que determina o fim de uma rodada principal (iteração do loop externo)?

A rodada principal acaba após o "Garimpeiro" varrer todo o restante do vetor apenas com os olhos (sem mover nada) e fazer uma única troca física direta: ele pega o menor elemento encontrado e o deposita na posição de destino da rodada.

No Insertion Sort, qual é o gatilho físico que determina o fim de uma rodada principal (iteração do loop externo)?

• A rodada principal acaba quando a "carta da vez" (o primeiro elemento logo após a fronteira ordenada |) acha o seu vão correto na sublista da esquerda, as cartas maiores terminam de escorregar e a carta é inserida ali. Tudo que está à direita dessa carta fica congelado e intocado.