Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — UEM 2025

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qg617006
Banca
UEM
Órgão
UEM
Ano
2025
Nível
Superior
Cargo
Analista de Informática - Edital nº 175
Sobre as estruturas de dados, assinale a alternativa correta.
  1. APodemos dizer que a estrutura de dados do tipo pilha é vista como uma especialização da estrutura de dados do tipo fila e que essas duas estruturas de dados são vistas como especializações da estrutura de dados do tipo lista.
  2. BUma lista encadeada deve ser implementada como uma estrutura de dados dinâmica, na qual os elementos são alocados dinamicamente na memória e os endereços dos elementos são utilizados para uns apontarem para os outros.
  3. CA busca sequencial de um elemento em um vetor de n elementos ordenados possui uma complexidade de ordem O(n) no pior caso, enquanto a busca binária de um elemento no mesmo vetor possui uma complexidade de ordem O(log de n) no pior caso. Na árvore binária de busca balanceada AVL com n elementos, a busca de um elemento também possui complexidade O(log de n).
  4. DNas árvores binárias de busca balanceadas AVL e Rubro-Negra, as subárvores esquerda e direita de cada nó podem diferir em, no máximo, 1 nível na altura ou uma cor na quantidade, respectivamente.
  5. ENa árvore binária de busca balanceada AVL, quando a inserção ou a remoção de um nó em uma subárvore, à esquerda ou à direita de sua raiz, provoca o desbalanceamento dessa subárvore, a execução de uma rotação apropriada nessa subárvore resolverá o problema, e a árvore voltará a ficar balanceada, e não será necessário ainda balancear outra(s) subárvore(s) mais acima.
Revelar gabarito e comentário

GabaritoC — A busca sequencial de um elemento em um vetor de n elementos ordenados possui uma complexidade de ordem O(n) no pior caso, enquanto a busca binária de um elemento no mesmo vetor possui uma complexidade de ordem O(log de n) no pior caso. Na árvore binária de busca balanceada AVL com n elementos, a busca de um elemento também possui complexidade O(log de n).

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Estruturas de Dados

Gabarito: letra C. A alternativa C está correta ao afirmar que a busca sequencial em um vetor ordenado tem complexidade O(n) no pior caso, a busca binária O(log n) e a busca em uma árvore AVL também O(log n). Essas são complexidades clássicas da análise de algoritmos. As demais alternativas apresentam erros conceituais conforme detalhado a seguir.

Complexidade de busca (pior caso)
  • 1Vetor ordenado
    • Busca sequencial: O(n)
    • Busca binária: O(log n)
  • 2Árvore AVL balanceada
    • Busca: O(log n)
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que a pilha é uma especialização da fila e ambas são especializações da lista. Na verdade, pilha (LIFO) e fila (FIFO) são estruturas distintas, cada uma com seu próprio comportamento; não há relação de especialização entre elas. Ambas podem ser implementadas a partir de listas, mas não são hierarquicamente derivadas uma da outra.

Alternativa B — ❌ Incorreta

Diz que uma lista encadeada deve ser implementada como estrutura dinâmica. Embora a implementação mais comum seja dinâmica (com alocação por nós e ponteiros), é possível implementar uma lista encadeada de forma estática (usando um array e índices simulando ponteiros). O termo "deve" torna a afirmação absoluta e, portanto, incorreta.

Alternativa C — ✅ Correta ⟵ GABARITO

A descrição das complexidades está correta:

  • Busca sequencial em vetor ordenado: O(n) no pior caso (percorre todos os elementos).

  • Busca binária no mesmo vetor: O(log n) (divisão sucessiva do intervalo).

  • Busca em árvore AVL (balanceada): O(log n) (altura máxima logarítmica).

Essas são definições fundamentais da ciência da computação.

Alternativa D — ❌ Incorreta

Mistura condições de balanceamento de AVL e Rubro-Negra. Em árvores AVL, a diferença de altura entre subárvores esquerda e direita de cada nó é no máximo 1. Em árvores Rubro-Negra, o balanceamento é baseado em cores (vermelho/preto) e na propriedade de que nenhum caminho raiz-folha tem mais que o dobro do comprimento de outro, não em uma diferença de nível de 1 ou em "uma cor na quantidade".

Alternativa E — ❌ Incorreta

Afirma que, após uma rotação local, não é necessário balancear subárvores acima. Em árvores AVL, uma inserção ou remoção pode causar desbalanceamento que exige rotações em vários pontos da árvore, subindo até a raiz. Uma rotação local pode resolver o desbalanceamento imediato, mas o efeito pode propagar-se para ancestrais, exigindo novas rotações. A afirmação de que "não será necessário ainda balancear outra(s) subárvore(s) mais acima" é falsa.

Gabarito: letra C

Link permanente: /questoes/qg617006