Questão 10462

• Banca: ESAF
• Órgão: CGU
• Ano: 2006
• Provas: ESAF - 2006 - CGU - Analista de Finanças e Controle - Tecnologia da Informação - Prova 3
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

Analise as seguintes afirmações relacionadas a conceitos básicos de estruturas de dados.

I. Em uma árvore genérica, não binária, cada nó pode ter qualquer quantidade de nós filhos.

II. Em uma árvore binária de pesquisa, a busca é feita de tal forma que se o dado procurado está na raiz a pesquisa será encerrada. Caso contrário, a busca continua e deve ser feita em apenas uma das duas sub-árvores.

III. Uma árvore binária é considerada balanceada quando, para cada nó, a altura das duas sub-árvores diferem, no máximo, da somatória da quantidade de nós existentes nos níveis pares, dividido pela quantidade de níveis considerados.

IV. Um circuito em um grafo é um caminho único que tem origem no primeiro nó e se encerra no último nó.

Indique a opção que contenha todas as afirmações verdadeiras.

• A. I e II
• B. II e III
• C. III e IV
• D. I e III
• E. II e IV

Gabarito: A

Comentários

• Discordo da questao II, pois o atravessamento em arvores binarias pode ser feito de quatro maneiras:
  -Em ordem (Esquerda, Raiz, Direita - E,R,D)
  -pre-ordem(Raiz, Esquerda, Direita - R,E,D)
  -pos-ordem(Esquerda, Direita, Raiz - E,D,R)
  -em nivel (de acordo com os niveis da esquerda para a direita)
• ABP = Árvore Binária de Pesquisa
  
  PesquisaABP(Item P, Arvore T) {
  
  Se T.Item = P retorne T
  
  Se T.Item > P PesquisaABP(P, T.Esquerda)
  
  Senão PesquisaABP(P, T.Direita)
  }
  
• Acho que o ítem II deixa claro a opção por iniciar a busca pela raiz. Se o algoritmo já sabe o valor da raiz, ele sabe em qual das duas árvores filhas continuar a busca. Qual o sentido de procurar nas duas? Acho que a questão está correta sim.
• O Item II fala da árvore binária de pesquisa... os nós estão ordenados, não faz sentido buscar nas duas sub-árvores. Imagina que o nó raiz é 8 e o dado que se deseja encontrar é 4. A subárvore esquerda possui os números menores que 8. A subárvore direita os dados maiores que 8. Pra que irei procurar o número 4 no lado direito? Por isso que o Item II está correto.
• II. Em uma árvore binária de pesquisa, a busca é feita de tal forma que se o dado procurado está na raiz a pesquisa será encerrada. Caso contrário, a busca continua e deve ser feita em apenas uma das duas sub-árvores.
  
  Arvore binária de pesquisa ou busca construída de tal forma que, para cada nó:
  
  1) nós com chaves menores estão na sub-árvore esquerda
  
  2) nós com chaves maiores (ou iguais) estão na sub-árvore direita
  
  3) Inserção dos nós da árvore deve satisfazer a essa propriedade