Atividade 3 – Estruturas de Dados I – 52/2025

ATIVIDADE 3 – ESTRUTURAS DE DADOS I – 52/2025

QUESTÃO 1
Um grafo G pode ser definido a partir de dois sub-conjuntos. O primeiro, é o chamado conjunto V, no qual temos os vértices do grafo. Já o segundo, o conjunto E, é o conjunto de arestas e ele representa as conexões entre os respectivos vértices do grafo. Um grafo, assim, pode ser representado modelado e implementado seguindo diferentes diretrizes conceituais no que tange suas estruturas de dados.

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.

Conhecendo as formas de se representar grafos computacionalmente, observe a matriz a seguir:

Levando em conta que a matriz a cima representa um grafo com 4 vértices V = {a, b, c, d}, avalie as afirmações a seguir:

I – A matriz acima pode ser utilizada para representar um grafo não-orientado.
II – Pode-se afirmar que não existe aresta conectando o vértice “a” ao vértice “c”.
III – Pode-se dizer, olhando para tal matriz, que as arestas têm pesos distintos.

De acordo com as afirmações acima, é possível dizer que está(ão) correta(s) a(s) afirmativa(s):

Alternativas
Alternativa 1 – I, apenas.
Alternativa 2 – II, apenas.
Alternativa 3 – I e II, apenas.
Alternativa 4 – I e III, apenas.
Alternativa 5 – II e III, apenas.

QUESTÃO 2
Em um programa que utiliza estrutura de dados em pilha para gerenciar o histórico de páginas visitadas em um navegador web, considere que essa pilha é implementada de forma estática com capacidade máxima para 10 elementos.

Fonte: Elaborado pelo professor, 2024.

Qual operação deve ser realizada quando um usuário acessa uma nova página?

Alternativas
Alternativa 1 – IsEmpty: Verificar se a pilha está vazia.
Alternativa 2 – Push: Adicionar a nova página no topo da pilha.
Alternativa 3 – Top: Visualizar a página atual sem removê-la da pilha.
Alternativa 4 – Pop: Remover a página mais recente do topo da pilha.
Alternativa 5 – IsFull: Verificar se a pilha atingiu sua capacidade máxima.

QUESTÃO 3
A busca em profundidade de baseia no conceito de pilha, no qual para cada nó que está no topo da pilha, é preciso visitar o seu próximo nó adjacente, empilhando-o, de maneira recorrente. Observe o algoritmo DFS(), abaixo:

Assim sendo, aplique o algoritmo acima no grafo representado abaixo, considerando que a busca se inicia no vértice 1.

A sequência de visitação que corresponde à resposta correta é:

Alternativas
Alternativa 1 – 1, 2, 5, 6, 7, 4, 3.
Alternativa 2 – 1, 2, 5, 3, 4, 7, 6.
Alternativa 3 – 1, 2, 3, 5, 4, 7, 6.
Alternativa 4 – 1, 3, 4, 7, 6, 5, 2.
Alternativa 5 – 1, 3, 5, 2, 4, 6, 7.

QUESTÃO 4
Segundo a bibliografia estudada, a teoria dos grafos engloba mais do que uma estrutura de dados. É uma forma matemática eficiente de tratar problemas reais de logística, custos, eficiência, dentre muitos outros.

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019

A respeito da teoria dos grafos, analise as afirmativas a seguir.

I – Pode ser utilizada para descoberta do caminho mais curto.
II – É utilizada em aplicativos tipo GPS para determinar o caminho a ser percorrido.
III – O problema das Sete Pontes de Königsberg é um exemplo clássico de sua utilização.
IV – Um GRAFO é uma estrutura baseadas em gráficos do tipo f(x)=y .
V – Euler é um dos maiores pesquisadores desta área.

Assim sendo, é correto o que se afirma em:

Alternativas
Alternativa 1 – I e II, apenas.
Alternativa 2 – I, II e V, apenas.
Alternativa 3 – II, III e V, apenas.
Alternativa 4 – I, II, III e V, apenas.
Alternativa 5 – I, II, III e IV, apenas.

QUESTÃO 5
“Muitos problemas podem ser descritos por meio de grafos, nos quais a solução para o problema requer que realizemos uma busca pelo grafo. As buscas, em geral, partem de um nó inicial em direção a um nó alvo, fazendo com que tenhamos que percorrer toda uma sequência ordenada de nós e arestas. Além disso, o próprio caminho, em si, pode ser objeto da busca, isto é, às vezes a solução reside no caminho percorrido, e não em um nó alvo específico.”

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.

Considerando tanto o algoritmo de busca em largura, quanto em profundidade, para que seja possível que tais algoritmos consigam navegar por todos os nós de um grafo, é imprescindível que o grafo seja:

Alternativas
Alternativa 1 – Um dígrafo.
Alternativa 2 – Orientado.
Alternativa 3 – Conexo.
Alternativa 4 – Ponderado.
Alternativa 5 – Um multigrafo.