Atividade 3 – ADSIS – Estruturas de Dados – 52/2025

ATIVIDADE 3 – ADSIS – ESTRUTURAS DE DADOS – 52/2025

QUESTÃO 1
Em Python, a manipulação e implementação de grafos podem ser eficientemente realizadas usando estruturas de dados fornecidas pelo módulo collections. Uma dessas estruturas é o defaultdict, que é uma subclasse do dicionário padrão de Python. O defaultdict facilita a criação de listas de adjacências para representar grafos, pois ele automaticamente inicializa qualquer chave acessada com um valor default, eliminando a necessidade de verificar se uma chave está presente no dicionário. Isso simplifica significativamente o código para adicionar arestas e vértices ao grafo, tornando o defaultdict uma escolha popular para implementações de grafos em Python.

Fonte: Elaborado pelo professor, 2024.

Ao usar collections.defaultdict para implementar um grafo em Python, qual das seguintes afirmações melhor descreve uma prática eficaz?

Alternativas
Alternativa 1 – Para criar grafos ponderados, defaultdict é ineficaz, pois não pode armazenar pares de valores como pesos de arestas junto aos vértices.
Alternativa 2 – O defaultdict deve ser utilizado com o tipo list como valor padrão para armazenar arestas de forma eficiente em grafos direcionados e não direcionados.
Alternativa 3 – Ao implementar grafos, é uma prática recomendada usar defaultdict com o valor padrão sendo outro defaultdict, para facilitar a criação de matrizes de adjacência.
Alternativa 4 – O defaultdict elimina a necessidade de qualquer outra estrutura de dados auxiliar para a representação de grafos, como listas ou conjuntos, independentemente do tipo de grafo.
Alternativa 5 – O uso de defaultdict é recomendado apenas para grafos pequenos, sendo inadequado para grafos com um grande número de vértices e arestas devido à sua alta complexidade de memória.

QUESTÃO 2
Carolina está desenvolvendo um sistema para controlar o atendimento de clientes em uma clínica. Para isso, ela precisa garantir que os pacientes sejam atendidos na mesma ordem em que chegaram. Durante sua pesquisa, ela descobriu o conceito de fila FIFO (First In, First Out) e soube que é possível implementá-lo em Python usando diferentes estruturas de dados, como listas ou coleções especializadas. Agora, Carolina quer entender melhor como o comportamento FIFO se aplica na linguagem.

Com base no funcionamento de filas FIFO (First In, First Out) em Python, qual das alternativas a seguir descreve corretamente esse conceito?

Alternativas
Alternativa 1 – FIFO é um modelo de acesso onde o último elemento inserido é o primeiro a ser removido.
Alternativa 2 – Em uma fila FIFO, os elementos são removidos aleatoriamente, sem ordem definida de entrada.
Alternativa 3 – O modelo FIFO garante que o primeiro elemento adicionado à fila seja o primeiro a ser retirado, respeitando a ordem de entrada.
Alternativa 4 – O comportamento FIFO em Python só pode ser implementado utilizando estruturas de arquivos externos, como bancos de dados.
Alternativa 5 – Python não permite a implementação de filas com comportamento FIFO, pois suas estruturas de dados são todas baseadas em pilhas (LIFO).

QUESTÃO 3
A busca em largura é uma técnica para realizar buscas a fim de ter um vértice de início e um vértice de destino. Por meio de um algoritmo, encontrar o vértice navegando pelas arestas. Utilizando a busca em largura, analise o grafo a seguir e considere a início no vértice 1 e o destino no vértice 6. Assinale a alternativa que contém a ordem correta em que será verificado cada vértice, seguindo a busca em largura.

Alternativas
Alternativa 1 – 1, 2, 4, 8, 9, 5, 6
Alternativa 2 – 1, 2, 4, 5, 3, 7, 8, 9, 6
Alternativa 3 – 1, 3, 7, 2, 4, 8, 9, 5, 6
Alternativa 4 – 1, 2, 3, 4, 5, 7, 8, 9, 6
Alternativa 5 – 1, 3, 2, 4, 7, 8, 9, 5, 6

QUESTÃO 4
Em grafos a forma que os vértices se conectam definem a sua classificação, permitindo assim que possamos identificá-los por esta característica. Considerando a classificação de grafos, analise o grafo a seguir e assinale a alternativa correta.

Alternativas
Alternativa 1 – a aresta (V5,V2) é válido
Alternativa 2 – o Grafo é considerado conexo
Alternativa 3 – o vértice V3 NÃO faz parte do Grafo
Alternativa 4 – a aresta (V4,V3) é considerado virtual
Alternativa 5 – o Grafo pode ser classificado como desconexo