Atividade Projeto e Analise de Algoritmos Semana 4

Prévia do material em texto

11/08/2025, 19:45 Fazer teste: Semana 4 Atividade Avaliativa Projeto e... Estado de Conclusão da Pergunta: leste. 4 Informações do teste Descrição Instruções Olá, estudante! 1. Para responder a esta atividade, selecione a(s) alternativa(s) que você considerar correta(s); 2. Após selecionar a resposta correta em todas as questões, vá até o fim da página e pressione "Enviar teste". 3. A cada tentativa, as perguntas e alternativas são embaralhadas Pronto! Sua atividade já está registrada no AVA. Várias Este teste permite 3 tentativas. Esta é a tentativa número 1. tentativas Forçar Este teste pode ser salvo e retomado posteriormente. conclusão Suas respostas foram salvas automaticamente. PERGUNTA 1 1,2 pontos Salva Os grafos podem ser implementados de duas formas típicas, por matriz de adjacências ou por matriz de adjacências. Em uma implementação por lista de adjacências, cada um dos vértices contém uma lista com quais os vértices conectados. Em um grafo direcionado, cada vértice representa a origem e a lista de vértices são os destinos contemplados pelas arestas. Um determinado gráfico, representado por listas de adjacências, contem as seguintes informações. Lista de Vértice adjacências A [B, F] [] [E, D] D [E] E [C] 1/711/08/2025, 19:45 Fazer teste: Semana 4 Atividade Avaliativa Projeto e... esse grafo. a. Existe pelo menos um nó isolado, por exemplo nó F. b. Existe um caminho de comprimento 2 entre e D. Existe um vértice que possui um laço. d. Existe uma aresta que retirada gera um subgrafo não conexo. e. Existe um ciclo contendo os nós A e B. PERGUNTA 2 1,2 pontos Salva A busca em amplitude é um tipo de busca em grafos em que os vértices são visitados de uma forma em que se encontra os menores caminhos entre os vértices. Em sua implementação, a dinâmica de exploração é baseada em uma estrutura em fila, em que os vértices são enfileirados para serem explorados um a um. Considerando grafo a seguir, que em cada nível os nós são explorados pela ordem alfabética e que a busca começará pelo vértice assinale a alternativa correta com a ordem em que vértice F será visitado, considerando inclusive nó A D C E F G H Figura: Grafo ilustrativo Fonte: O autor Descrição: A figura mostra um grafo com 8 vértices dispostos formando um quadrado com 3 vértices num primeiro nível, 3 vértices num segundo nível e e vértices no último nível, com canto inferior esquerdo vazio. No primeiro nível, o vértice está no canto superior esquerdo com arestas para E e No primeiro nível, o vértice está no canto superior esquerdo com arestas para E e No meio deste nível está vértice A e com arestas para B,C, E, F e D. No canto superior direito está vértice D com arestas para E e F. No segundo nível, à esquerda, está 0 vértice com arestas para e NO meio está vértice E com arestas G, H, F, D e Ainda no nível 2 na direita está vértice F com arestas para D, E e H. No último nível, terceiro nível, não há nada na esquerda. No meio está o vértice G com arestas para E e H. Na direita está 0 vértice H 2/711/08/2025, 19:45 Fazer teste: Semana 4 Atividade Avaliativa Projeto e... a. nó F será o sexto nó a ser visitado. b. nó F será terceiro nó a ser visitado. nó F será quarto nó a ser visitado. d. O nó F será sétimo nó a ser visitado. e. O nó F será o quinto nó a ser visitado. PERGUNTA 3 1,2 pontos Salva Os grafos podem representar diversas informações, por exemplo, ligação entre cidades em um mapa rodoviário, países e vizinhanças em um mapa colorido, pessoas e elos de amizades em uma rede social, computadores e seus links em uma rede de computadores. Enfim, existem diversos cenários que podem ser representados por grafos. A sua implementação pode acontecer por meio de matrizes ou listas de adjacências. Em uma implementação de um grafo direcionado de vias de uma cidade por matrizes, os pontos de A a da cidade possuem as seguintes ligações. A D E F A X X X X X X X D X E X F Analise as sentenças a respeito deste grafo. I. Os pontos da cidade rotulados por Ce E são vértices adjacentes. II. grau do ponto da cidade representado pelo vértice E é 5. III. grafo desta parte da cidade é um grafo cíclico. IV. A distância entre os pontos da cidade A e é 2. Está correto que se afirma em: a. e IV, apenas. 3/711/08/2025, 19:45 Fazer teste: Semana 4 Atividade Avaliativa Projeto e... d. II, III e IV, apenas. e. e III, apenas. PERGUNTA 4 1,7 pontos Salva O algoritmo de busca em largura (BFS) é conhecido por sua eficiência em termos de tempo de execução. Além de ser fundamental em teoria dos grafos, a BFS é amplamente utilizada em diversas aplicações práticas, como na determinação de caminhos mínimos em redes de comunicação e na exploração de grafos sociais. Considerando um grafo não ponderado e conexo, a BFS garante que cada vértice seja visitado uma única vez, assim como cada aresta, assegurando um processamento eficiente. Analise a complexidade temporal do BFS e assinale a alternativa que determina como ela é afetada pelo número de vértices (V) e arestas (E) em um grafo: a. b.O(V+E) d. V log E) PERGUNTA 5 1,7 pontos Salva A busca em grafos é um procedimento comum em diversos tipos de aplicações com esta estrutura de dados. Por exemplo, em uma rede de computadores, pode-se pensar em encontrar uma rota com um conjunto de roteadores entre dois computadores da rede. Em uma implementação, um programador utilizou seguinte algoritmo baseado no tipo de dados Lista. A função Anexa insere um elemento ao final da lista e a função Retiralnicio retira o primeiro elemento da lista. Estas operações de inserir ao final e retirar do início são O(1). Linha Código 1 Algoritmo Busca(Grafo G, vertice s) 2 s.visitado 3 cria lista vazia L 4 AdicionaFinal(L, s) 5 enquanto F.tamanho > 0 faça 6 u = Retiralnicio(L) 7 para todo vertice V em Adj[u] faça 8 se v.visitado == 0 então 9 v.visitado = 1 10 v.pred = 11 AdicionaFinal(L, v) 4/711/08/2025, 19:45 Fazer teste: Semana 4 Atividade Avaliativa Projeto e... A respeito deste algoritmo, analise as sentenças a seguir: I. A estrutura de dados que mantem os vértices sendo explorados está se comportando como uma LIFO. II. Usando esta estratégia, para buscar um caminho entre dois vértices, será encontrado sempre menor caminho. III. algoritmo, ao manter os predecessores, acaba originando uma árvore que tem como raiz o vértice S. IV. A execução do algoritmo envolve uma passagem pelos vértices e seus adjacentes uma vez por isso tem tempo linear. É CORRETO o que se afirma em a. III, apenas. b.1, e III, apenas. C. IV, apenas. d. II, III e IV, apenas. e. e IV, apenas. PERGUNTA 6 1 pontos Salva Em teoria dos grafos, os ciclos desempenham um papel importante na estrutura e análise dos grafos. Um ciclo é um tipo específico de caminho que pode ajudar a identificar propriedades críticas em redes e sistemas representados por grafos. Grafos que não possuem ciclos são conhecidos como grafos acíclicos. Assinale a alternativa que descreve ciclo em um grafo. a. Um caminho fechado onde nenhuma aresta ou vértice aparece mais de uma vez, exceto vértice inicial e final, é visitado duas vezes, uma no início e outra no fim do percurso. b. Um caminho aberto entre dois vértices, sem repetição de qualquer aresta ou vértice no percurso, sendo que cada vértice é visitado uma única vez durante trajeto. C. Um caminho fechado onde arestas e vértices podem se repetir livremente, permitindo múltiplas visitas aos mesmos vértices e reutilização das arestas sem restrições. d. Um caminho que passa por todos os vértices do grafo sem repetição, visitando cada vértice uma única vez e cobrindo todos os vértices disponíveis no grafo. e. Uma sequência de vértices desconectados, onde não há arestas ligando os vértices, e cada vértice é completamente 5/711/08/2025, 19:45 Fazer teste: Semana 4 Atividade Avaliativa Projeto e... PERGUNTA 7 1 pontos Salva Os grafos são estruturas fundamentais em ciência da computação e matemática, usados para modelar diversas situações do mundo real. Eles consistem em nós (ou vértices) conectados por arestas. Existem diferentes tipos de grafos, como os grafos rotulados e os grafos com pesos. A distinção entre esses dois tipos de grafos é importante para entender como cada um pode ser aplicado em diferentes contextos. Assinale a alternativa que apresenta a diferenciação entre um grafo rotulado e um grafo com pesos. a. Em grafos rotulados, as arestas têm valores numéricos, enquanto em grafos com pesos, os nós têm identificadores. b. Em grafos rotulados, todos os nós são iguais, enquanto em grafos com pesos, as arestas são todas iguais. C. Em grafos rotulados, os nós não se conectam, enquanto em grafos com pesos, as arestas não se conectam. d. Em grafos rotulados, os nós têm identificadores, enquanto em grafos com pesos, as arestas têm valores numéricos. e. Em grafos rotulados, as arestas são ordenadas, enquanto em grafos com pesos, os nós são ordenados. PERGUNTA 8 1 pontos Salvar resposta Leia trecho a seguir: Os grafos são estruturas que contém vértices conectados por arestas e podem representar diversas aplicações. Em [preencher 1] conjunto de arestas contém um ponto inicial e um ponto final e pode indicar os voos entre origem e destino da malha aérea, por exemplo. Em um [preencher 2] um valor numérico é associado às arestas e podem representar, por exemplo, os tempos de entre as cidades. Nos grafos, [preencher 3] de um nó é número de extremidades de arcos ou arestas naquele nó e pode representar quantos voos existe a partir de certa cidade. Neste contexto, identifique os termos de [preencher 1] [preencher 2] e [preencher 3] que são substituídos por: a. 1 um Dígrafo; 2 Grafo com comprimentos; 3 Nível. b. 1 um Grafo simples; 2 - Dígrafo; 3 Grau. C. 1 um Grafo simples; 2 Grafo com pesos; 3 Grau. um Dígrafo; 2 Grafo com pesos; 3 Grau. e. 1 uma Árvore; 2 Grafo com comprimentos; 3 Nível. 6/711/08/2025, 19:45 Fazer teste: Semana 4 - Atividade Avaliativa - Projeto e... Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas. Salvar todas as respostas Salvar e Enviar 7/7