Questões de Concurso Público UFSM 2025 para Professor EBTT - Área: Ciências Exatas e da Terra/Ciência da Computação/ Metodologia e Técnicas da Computação

Considere um grafo dirigido G=(N, A) em que o conjunto N é composto por seis nós, numerados de 1 a 6. O conjunto de arcos A é o apresentado a seguir na forma de lista de adjacência:

1 → 2, 4, 5
2 → 3
3 → 2
4 → 2, 3
5 → 4
6 → 1, 5

Tendo em vista a estrutura desse grafo, considere as afirmativas a seguir.

I  →  Trata-se de um grafo conexo, porém não fortemente conexo.
II  →  A sequência de nós 6, 1, 5, 2, 4, 3 representa uma possível ordem de visita aos nós para um percurso em amplitude.
III  →  A sequência de nós 6, 1, 2, 4, 3, 5 representa uma possível ordem de visita aos nós para um percurso em profundidade.
IV  →  Existe um caminho ligando os nós 6 e 2 composto por uma sequência de 5 arcos distintos entre si.

Estão corretas

A figura representa a estrutura padrão de uma Árvore Binária de Busca. Considere que a árvore é organizada de acordo com valores numéricos armazenados nos nós, mas omitidos na figura. Há um valor por nó, sem repetição de valor.



As letras colocadas abaixo da representação de alguns nós têm propósito exclusivo de identificar esses nós, não apresentando qualquer relação com os valores armazenados na árvore.

Como a árvore possui 15 valores distintos, armazenados em 15 nós, é possível definir que o segundo maior valor da árvore é aquele maior do que 13 dos outros valores armazenados e menor do que apenas um. De forma semelhante, o segundo menor valor da árvore é aquele menor do que 13 dos outros valores e maior do que apenas um. 

Assinale a alternativa que apresenta as letras que identificam os nós que armazenam, respectivamente, o segundo menor e o segundo maior valores dentre os 15 valores armazenados nos nós da árvore.