Algoritmos e Estrutura de Dados · AOCP · 2018 | Questão sqc-qq314502

Algoritmos e Estrutura de DadosEstrutura de Dados

Código: qq314502
Banca: AOCP
Órgão: FUNPAPA
Ano: 2018
Nível: Superior

Cargo: Analista de Sistemas

Na computação, uma estrutura de dados é um modo particular de armazenamento e organização de dados em um computador, de modo que possam ser usados eficientemente, facilitando sua busca e modificação. Sobre estrutura de dados, é correto afirmar que

Auma lista duplamente ligada é uma sequência de elementos em que cada elemento, com exceção do primeiro e último, contém um valor e referências para o elemento anterior e o elemento seguinte.
Buma Árvore Rubro-Negra é uma sequência de elementos em que cada elemento, com exceção do primeiro e último, contém um valor e referências para o elemento anterior e o elemento seguinte.
Cuma Árvore Rubro-Negra é uma Árvore Binária de Busca com dois bits extras de armazenamento por nó que indicam sua cor no nodo, PRETA e VERMELHA.
Duma lista duplamente ligada é uma Árvore Binária de Busca com um bit extra de armazenamento por nó que indica sua cor, PRETA ou VERMELHA.
Eem uma Árvore Rubro-Negra, referente a sua profundidade, todos os nodos externos têm a mesma profundidade preta, que é definida como o número de ancestrais pretos menos 2.

Revelar gabarito e comentário

GabaritoA — uma lista duplamente ligada é uma sequência de elementos em que cada elemento, com exceção do primeiro e último, contém um valor e referências para o elemento anterior e o elemento seguinte.

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: Lista Duplamente Ligada e Árvore Rubro-Negra

Gabarito: letra A. A alternativa A descreve corretamente uma lista duplamente ligada: cada nó (exceto primeiro e último) possui um valor e dois ponteiros, um para o anterior e outro para o próximo. As demais alternativas misturam conceitos ou trazem definições incorretas sobre árvores rubro-negras.

NÃO CAIA NESSA!

A banca explora dois erros numéricos frequentes: (C) afirma que a árvore rubro-negra usa dois bits para a cor, quando na verdade basta um bit (vermelho/preto); (E) define a profundidade preta como "número de ancestrais pretos menos 2", mas o correto é que todos os nodos externos têm a mesma quantidade de ancestrais pretos (black height), sem o "menos 2". Fique atento a esses detalhes numéricos.

Alternativa A — ✅ Correta ⟵ GABARITO

A definição está exata. Em uma lista duplamente ligada, cada elemento (nó) contém um valor e duas referências: prev (anterior) e next (próximo). O primeiro nó não tem anterior e o último não tem próximo, exatamente como descrito.

Alternativa B — ❌ Incorreta

A descrição dada é de uma lista duplamente ligada, não de uma árvore rubro-negra. Uma árvore rubro-negra é uma árvore binária de busca balanceada com propriedades de cores, não uma sequência linear.

Alternativa C — ❌ Incorreta

O erro está em "dois bits extras de armazenamento por nó". Na verdade, uma árvore rubro-negra utiliza apenas um bit por nó para indicar a cor (PRETA ou VERMELHA). Dois bits permitiriam quatro cores, o que é desnecessário.

Alternativa D — ❌ Incorreta

Inverte completamente os conceitos: uma lista duplamente ligada não é uma árvore binária de busca e não possui atributo de cor. A descrição seria aplicável (com correções) a uma árvore rubro-negra.

Alternativa E — ❌ Incorreta

Em árvores rubro-negras, todos os nodos externos (NIL) têm a mesma profundidade preta (black height), que é o número de ancestrais pretos no caminho até a raiz. A definição dada com "menos 2" está incorreta — não há subtração desse valor.

Gabarito: letra A

Link permanente: /questoes/qq314502