Questão nº 49
Questão de Tecnologia da Informação · FGV STN 2024 (nº 49)
No contexto de uma Árvore B, estrutura comumente utilizada na indexação de tabelas relacionais, considere as seguintes propriedades numa árvore B de grau g.
- Todas as folhas estão no mesmo nível de profundidade na árvore.
- Todos os nós podem conter, no máximo, 2g - 1 chaves.
- Exceto pelo nó raiz, todos os demais nós devem conter, no mínimo, 3 chaves.
- Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n²).
- Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n).
Estão corretas apenas as afirmativas
- A1 e 2. (alternativa correta)
- B1, 2 e 3.
- C1, 2, 3 e 4.
- D1, 3, 4 e 5.
- E2, 4 e 5.
Resposta comentada
Gabarito Alternativa A
Uma Árvore B é uma estrutura de dados balanceada, otimizada para armazenar e recuperar grandes volumes de dados em sistemas de armazenamento em disco, como bancos de dados. Ela minimiza o número de acessos ao disco, mantendo os dados ordenados e garantindo que todas as operações (busca, inserção, remoção) tenham um desempenho logarítmico. O grau g de uma Árvore B geralmente se refere ao número mínimo de filhos que um nó não-raiz pode ter (e, consequentemente, o número mínimo de chaves é g-1).
- (A) Correta: A propriedade fundamental das Árvores B é que todas as folhas estão no mesmo nível de profundidade, garantindo que o tempo de busca seja sempre consistente. Além disso, em uma Árvore B de grau g (onde g é o grau mínimo), cada nó (exceto a raiz) deve ter entre g-1 e 2g-1 chaves. Portanto, o número máximo de chaves é 2g-1.
- (B) Incorreta: A afirmativa 3 está incorreta.
- (C) Incorreta: As afirmativas 3 e 4 estão incorretas.
- (D) Incorreta: As afirmativas 3, 4 e 5 estão incorretas.
- (E) Incorreta: As afirmativas 4 e 5 estão incorretas.
Comentário sobre os distratores:
- (A) Incorreta: (Esta é a alternativa correta, então não é um distrator)
- (B) Incorreta: A afirmativa 3 ("Exceto pelo nó raiz, todos os demais nós devem conter, no mínimo, 3 chaves") é o distrator mais tentador. A armadilha é que o número mínimo de chaves em um nó não-raiz é g-1, e não um valor fixo como 3. Se o grau g fosse 4, por exemplo, o mínimo seria 3 chaves. No entanto, se g fosse 2, o mínimo seria 1 chave. Portanto, "3 chaves" não é uma regra geral para qualquer grau g.
- (C) Incorreta: A afirmativa 4 ("Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n²)") está incorreta. A complexidade de inserção em uma Árvore B é logarítmica, ou seja, O(log N), não polinomial.
- (D) Incorreta: A afirmativa 5 ("Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(n)") está incorreta. Assim como a afirmativa 4, a complexidade é logarítmica, não linear.
Fonte: FGV STN 2024 Auditor Federal de Finanças e Controle - Tecnologia da Informação (Operação e Infraestrutura) (Caderno Tipo 1). Reproduzida para fins de estudo.