Algoritmos e Estrutura de Dados · COPESE - UFPI · 2024 | Questão sqc-qg107581

Algoritmos e Estrutura de DadosEstrutura de Dados

Código: qg107581
Banca: COPESE - UFPI
Órgão: UFPI
Ano: 2024
Nível: Superior

Cargo: COPESE - - Analista de Tecnologia da Informação: Infraestrutura

Árvores binárias são uma das estruturas de dados mais fundamentais, sendo usadas em diversas aplicações, desde a implementação de expressões matemáticas até a construção de tabelas de símbolos. Além disso, compreender a complexidade das operações nessas estruturas é essencial para escolher a melhor árvore para um determinado problema. Considere as seguintes afirmações sobre árvores binárias, AVL, B, B+ e a complexidade das operações associadas a essas estruturas:I. A complexidade da busca, inserção e remoção em uma árvore binária de busca desbalanceada no pior caso é O(n), mas, em uma árvore AVL, essas operações sempre têm complexidade O(log n) no pior caso;II. Em uma árvore AVL, a rotação simples e a rotação dupla são operações fundamentais para manter a árvore balanceada após inserções e remoções, mas essas rotações podem fazer com que o tempo de execução de uma inserção ou remoção se degrade para O(n) em casos específicos;III. Árvores B são ideais para sistemas de banco de dados porque permitem que várias operações de busca, inserção e remoção sejam realizadas em tempo O(log n), com a vantagem adicional de minimizar o número de acessos a disco devido à estrutura de nós de múltiplas chaves;IV. Em uma árvore B+, ao contrário de uma árvore B, todas as chaves estão armazenadas apenas nos nós folha, o que significa que as buscas por chaves sempre resultam em acessos aos nós folha. Embora isso possa tornar a busca ligeiramente menos eficiente em comparação com uma árvore B, na qual a busca pode ser resolvida em um nó interno, a árvore B+ oferece outras vantagens, como uma estrutura mais simples e suporte eficiente para operações de intervalo e varreduras de dados;V. Apesar de as árvores B e B+ serem amplamente usadas em bancos de dados, uma desvantagem das árvores B+ em relação às árvores B é que a estrutura de encadeamento entre os nós folha pode aumentar significativamente o tempo de execução das operações de inserção e remoção, devido à necessidade de reorganização frequente dos nós folha.Assinale a opção CORRETA:

AApenas I, III e IV estão corretas.
BApenas II, IV e V estão corretas.
CApenas I, III e V estão corretas.
DApenas I, II e IV estão corretas.
EApenas III, IV e V estão corretas.

Revelar gabarito e comentário

GabaritoA — Apenas I, III e IV estão corretas.

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”.

Árvores binárias, AVL, B e B+ — complexidade e características

Gabarito: letra A. As afirmações corretas são I, III e IV. A afirmação II erra ao dizer que rotações em AVL podem degradar a complexidade para O(n); na verdade, são O(1) e as operações permanecem O(log n). A afirmação V erra ao afirmar que o encadeamento entre folhas em B+ aumenta significativamente o tempo de inserção/remoção; tal encadeamento não altera a complexidade assintótica (O(log n)) e é uma vantagem para operações de intervalo.

Afirmação I — ✅ Correta

Em uma árvore binária de busca desbalanceada, no pior caso (árvore degenerada), a altura é O(n), levando a busca/inserção/remoção a O(n). Já em uma árvore AVL, o balanceamento garante altura O(log n), portanto todas as operações têm complexidade O(log n) no pior caso. Fonte: definição de árvore AVL (balanceada) e complexidade de BST.

Afirmação II — ❌ Incorreta

As rotações simples e duplas em uma árvore AVL são operações de custo constante (O(1)), e não degradam o tempo de execução para O(n). A inserção e remoção em AVL já incluem eventuais rotações e permanecem O(log n) no pior caso. A afirmação de que "podem fazer com que o tempo se degrade para O(n)" é falsa.

Afirmação III — ✅ Correta

Árvores B são projetadas para sistemas de banco de dados: cada nó contém múltiplas chaves, reduzindo a altura (O(log n) com base no grau) e minimizando acessos a disco, pois cada nó corresponde a um bloco. As operações de busca, inserção e remoção têm complexidade O(log n) no pior caso.

Afirmação IV — ✅ Correta

Em uma árvore B+, as chaves estão armazenadas apenas nos nós folha, e os nós folha são ligados em lista. Isso faz com que toda busca precise atingir a folha, enquanto em uma árvore B a busca pode parar em um nó interno. Apesar disso, a árvore B+ oferece vantagens como suporte eficiente a operações de intervalo e varreduras sequenciais, além de estrutura mais simples para indexação.

Afirmação V — ❌ Incorreta

Em árvores B+, o encadeamento entre os nós folha é uma característica que facilita a varredura sequencial, sem aumentar significativamente o custo das operações de inserção e remoção. Tanto B quanto B+ têm complexidade O(log n) para essas operações; a reorganização de nós ocorre em ambas quando um nó fica cheio ou abaixo da ocupação mínima. Portanto, não é uma desvantagem relevante.

Afirmação	Conteúdo	Correção	Justificativa
I	Complexidade de busca, inserção e remoção em árvore binária desbalanceada (pior caso) é O(n); em AVL é O(log n)	✅ Correta	Árvore degenerada tem altura O(n); AVL garante altura O(log n)
II	Rotações em AVL podem degradar tempo para O(n)	❌ Incorreta	Rotações são O(1); operações permanecem O(log n)
III	Árvores B são projetadas para banco de dados, com múltiplas chaves por nó e altura O(log n)	✅ Correta	Reduz acessos a disco; operações O(log n)
IV	Em B+, chaves só nos nós folha, que são ligados em lista; busca sempre vai até a folha	✅ Correta	Diferencia de B; vantagem para operações de intervalo
V	Encadeamento entre folhas em B+ aumenta significativamente tempo de inserção/remoção	❌ Incorreta	Não altera complexidade assintótica O(log n); é vantagem

Árvores de busca: BST desbalanceada (Pior caso: O(n)); AVL (balanceada) (Rotação: O(1), Busca/inserção/remoção: O(log n)); Árvore B (Múltiplas chaves por nó, Acessos a disco reduzidos, Busca/inserção/remoção: O(log n)); Árvore B+ (Chaves só nas folhas, Folhas encadeadas, Varredura sequencial eficiente, Busca/inserção/remoção: O(log n))

Gabarito: letra A — apenas as afirmações I, III e IV estão corretas.

Link permanente: /questoes/qg107581