Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FAURGS 2023

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qq875013
Banca
FAURGS
Órgão
UFRGS
Ano
2023
Nível
Superior
Cargo
Analista de Tecnologia da Informação Área - Sistemas de Informação
Considere as afirmações abaixo sobre estruturas de dados.I - Em uma árvore genérica, no caminhamento pré-fixado de uma árvore T, a raiz de T é visitada primeiro e, então, as subárvores, cujas raízes são seus filhos, são percorridas recursivamente. Se a árvore está ordenada, então as subárvores são percorridas de acordo com a ordem dos filhos.II - Uma árvore binária é uma árvore ordenada com as seguintes propriedades: (a) todos os nodos têm no máximo dois filhos; (b) cada nodo-filho é rotulado como sendo um filho da direita ou um filho da esquerda; (c) o filho da esquerda precede o filho da direita na ordenação dos filhos de um nodo.III - Dois nodos que são filhos de um mesmo pai são irmãos. Um nodo v é interno se v não tem filhos. Um nodo v é externo se tem um ou mais filhos. Nodos internos também são conhecidos como folhas.Quais estão corretas?
  1. AApenas I.
  2. BApenas II.
  3. CApenas III.
  4. DApenas I e II.
  5. EI, II e III.
Revelar gabarito e comentário

GabaritoD — Apenas I e II.

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: definições e caminhamento

Gabarito: letra D — apenas as afirmativas I e II estão corretas. A questão testa conceitos fundamentais de árvores: caminhamento pré-fixado, propriedades de árvores binárias e nomenclatura de nós. O erro na afirmativa III é clássico: inverte as definições de nó interno e externo (folha).

1Irmãos
Mesmo pai
2Interno
Tem ≥1 filho
Afirmativa III: "não tem filhos"
3Externo (folha)
Não tem filhos
Afirmativa III: "tem ≥1 filho"
Nós da árvore
LEVELsoulevel.com.br
Nós da árvore: Irmãos (Mesmo pai); Interno (Tem ≥1 filho, Afirmativa III: "não tem filhos"); Externo (folha) (Não tem filhos, Afirmativa III: "tem ≥1 filho")

Item I — ✅ Correta

O caminhamento pré-fixado (pré-ordem) visita a raiz da árvore primeiro e, em seguida, percorre recursivamente cada subárvore na ordem dos filhos. Em árvores ordenadas, a ordem dos filhos é respeitada. Essa definição é padrão e está correta.

Item II — ✅ Correta

Uma árvore binária é uma árvore ordenada onde cada nó tem no máximo dois filhos, cada filho é rotulado como esquerdo ou direito, e o filho esquerdo precede o direito na ordenação dos filhos de um nó. A afirmativa reproduz exatamente essa definição.

Item III — ❌ Incorreta

O erro está na classificação dos nós. Na terminologia padrão:

  • Nó interno: possui pelo menos um filho (não é folha).

  • Nó externo (folha): não possui filhos.

A afirmativa III inverte os conceitos: diz que "nó v é interno se v não tem filhos" (na verdade é externo) e que "nó v é externo se tem um ou mais filhos" (na verdade é interno). Além disso, afirma que nós internos são conhecidos como folhas, quando o correto é que nós externos (folhas) não têm filhos. A parte sobre irmãos (dois nodos com mesmo pai) está correta, mas o erro central invalida a afirmativa.

Termo

Definição correta

Afirmativa III diz

Nó interno

Tem ≥1 filho

Não tem filhos

Nó externo (folha)

Não tem filhos

Tem ≥1 filho

NÃO CAIA NESSA!

A banca troca as definições de nó interno e externo. Lembre-se: interno = tem filhos; externo = folha (sem filhos). Fixe associando "externo" a "extremidade", ou seja, as folhas estão nas bordas da árvore, sem filhos.

Gabarito: letra D — corretas apenas as afirmativas I e II.

Link permanente: /questoes/qq875013