Atividade Semana 6 - Projeto e Análise de Algoritmos

Prévia do material em texto

Fazer teste: Atividade para Avaliação - Semana 6Projeto e Análise de Algoritmos - EEM002 - Turma 002 6 - Grafos e algoritmos clássicos (partes 1 e 2)
Fazer teste: Atividade para Avaliação - Semana 6 
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 1.
Forçar conclusão Este teste pode ser salvo e retomado posteriormente.
Suas respostas foram salvas automaticamente.
Atividade para avaliação
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 �m da página e pressione “Enviar teste”.
3. A cada tentativa, as perguntas e alternativas são embaralhadas
Consulte os gabaritos dessa disciplina no menu lateral.
Olá, estudante!
Pronto! Sua atividade já está registrada no AVA.
PERGUNTA 1
Um grafo possui 40 vértices e 100 arestas. Nessa situação, assinale a alternativa correta.
Representar o grafo usando coleção de listas de adjacências é mais e�ciente em se tratando de espaço de armazenamento, mas é
menos e�ciente que matrizes de adjacências em se tratando do tempo necessário para veri�car se um determinado vértice é
adjacente a outro.
Representar o grafo usando matrizes de adjacência é mais e�ciente do que representar o grafo usando coleção de listas de
adjacências tanto no critério de tempo para veri�car se um determinado vértice é adjacente a outro, quanto no critério de
armazenamento.
Representar o grafo usando coleção de listas de adjacências é mais e�ciente do que representar o grafo usando matrizes de
adjacências quando levamos em conta o tempo para veri�car se um vértice é adjacente a outro.
Representar o grafo usando coleção de listas de adjacênciasé mais e�ciente do que representar o grafo usando matrizes de
adjacências tanto no critério de tempo para veri�car se um determinado vértice é adjacente a outro, quanto no critério de
armazenamento.
Representar o grafo usando matrizes de adjacência é mais e�ciente do que representar o grafo usando coleção de listas de
adjacências quando usamos como critério o espaço de armazenamento utilizado.
1 pontos   Salva
PERGUNTA 2
Sobre as cores para marcação de vértices durante o algoritmo de busca em largura, é correto a�rmar que.
vértices brancos são aqueles que ainda não foram descobertos, vértices pretos são vértices já descobertos e com a vizinhança
analisada e vértices cinzas já foram descobertos, mas ainda não tiveram os vizinhos examinados.
vértices cinzas são aqueles que ainda não foram descobertos, vértices pretos são vértices já descobertos e com a vizinhança
analisada e vértices brancos já foram descobertos, mas ainda não tiveram os vizinhos examinados.
vértices pretos são aqueles que ainda não foram descobertos, vértices cinzas são vértices já descobertos e com a vizinhança
analisada e vértices brancos já foram descobertos, mas ainda não tiveram os vizinhos examinados.
vértices brancos são aqueles que ainda não foram descobertos, vértices cinzas são vértices já descobertos e com a vizinhança
analisada e vértices pretos já foram descobertos, mas ainda não tiveram os vizinhos examinados.
vértices cinzas são aqueles que ainda não foram descobertos, vértices brancos são vértices já descobertos e com a vizinhança
analisada e vértices pretos já foram descobertos, mas ainda não tiveram os vizinhos examinados.
1 pontos   Salva
PERGUNTA 3
Seja o grafo dado pela matriz de adjacências a seguir:
1 pontos   Salva
? Estado de Conclusão da Pergunta:
https://ava.univesp.br/webapps/blackboard/execute/courseMain?course_id=_2042_1
https://ava.univesp.br/webapps/blackboard/content/listContent.jsp?course_id=_2042_1&content_id=_353815_1&mode=reset
Assinale a opção que apresenta uma ordem de visitação dos vértices em um caminhamento em largura que inicia no vértice A.
A, G, F, B, C, D, E.
A, F, D, G, C, E, B.
A, G, F, C, D, B, E.
A, G, C, E, B, F, D.
A, F, G, C, B, D, E.
PERGUNTA 4
Sobre os algoritmos de busca em largura e profundidade aplicados a um grafo com |V| vértices e |E| arestas representadas com
coleção de listas de adjacências, é correto a�rmar que os seus tempos computacionais, respectivamente, são da ordem de:
O(|V|2), O(|V| + |E|)
O(|V|2), O(|V|2)
O(|V| + |E|), (|V|2)
O(|V| + |E|), O(|V| + |E|)
O(|V|), O(|V|+|E|)
1 pontos   Salva
PERGUNTA 5
Sobre a de�nição de grau de um vértice, é correto a�rmar que: 
o grau de um vértice em grafos direcionados é o número de arestas que chegam em um vértice somado com o número de arestas
que saem dele. 
o grau de um vértice em grafos não direcionados é o número de arestas que chegam em um vértice somado com o número de
arestas que saem dele.
o grau de um vértice em um grafo direcionado é o número de arestas que incidem sobre ele, ou seja, número de arestas de
entrada.
o grau de um vértice em grafos não direcionados é o número de arestas que chegam em um vértice subtraído do número de
arestas que saem dele.
o grau de um vértice em grafos direcionados é o número de arestas que chegam em um vértice subtraído do número de arestas
que saem dele.
1 pontos   Salva
PERGUNTA 6
Um grafo G é criado para conectar nomes de pessoas. O conjunto de vértices do grafo é formado por: V = {"pedro", "paulo", "anie",
"ulisses", "luis", "regina"}
Sejam "u" e "v" dois vértices diferentes pertencentes a V, uma aresta entre "u" e "v" existe se o nome que corresponde a "u" e o nome
que corresponde a "v" compartilham no mínimo duas letras. Em outras palavras, temos uma ligação entre pedro e paulo por
compartilharem as letras "p" e "o", mas não temos ligações entre pedro e ulisses, pois eles só compartilham a letra "e".
Sobre o grafo G, assinale a alternativa correta:
No grafo, três vértices possuem grau 3.
O vértice "ulisses" é o que possui maior grau.
O grafo possui apenas 10 arestas.
O vértice de maior grau possui grau 5.
Uma matriz de adjacências para o grafo é:
1 pontos   Salva
PERGUNTA 7
Sobre o grafo mostrado na �gura a seguir, assinale a alternativa correta: 
1 pontos   Salva
 Estado de Conclusão da Pergunta:
O vértice 3 tem grau 0.
O vértice 2 tem grau 1.
O vértice 5 tem grau 3.
Três vértices possuem o mesmo grau.
O vértice 5 tem grau 4.
PERGUNTA 8
Sobre os algoritmos de ordenação, assinale a alternativa que inclui apenas algoritmos de ordenação lineares: 
Bucketsort, Contagem, Radixsort
Quicksort, Mergesort, Heapsort.
Bucketsort, Contagem, Heapsort.
Radixsort, Mergesort, Inserionsort.
Radixsort, HeapSort, Bucketsort
1 pontos   Salva
PERGUNTA 9
Seja o grafo dado pela matriz de adjacência a seguir:
Assinale a opção que apresenta uma ordem de visitação dos vértices em um caminhamento em profundidade que inicia no vértice A.
A, B, D, E, G, F, C.
A, B, C, D, E, F, G.
A, D, E, B, G, F, C.
A, G, F, B, C, D, E.
A, C, D, E, F, G, B.
1 pontos   Salva
PERGUNTA 10
Sobre a representação computacional de grafos G = (V, E), onde V é o conjunto de vértices e E é o conjunto de arestas, é possível a�rmar
1 pontos   Salva
 Estado de Conclusão da Pergunta:
 Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
que:
se quisermos representar um grafo esparso G, podemos usar a representação em matriz de adjacência por questões de economia
de espaço de armazenamento. O espaço necessário para armazenar os elementos é da ordem de O(|E| + |V|).
se quisermos representar um grafo denso G, podemos usar a representação em matriz de adjacência por questões de e�ciência,
dado que o tempo necessário para acessar um vértice adjacente a outro é da ordem de O(log(|V|)).
se quisermos representar um grafo denso G, podemos usar a representação em coleção de listas de adjacências por questões de
e�ciência, dado que o tempo necessário para acessar um vértice adjacente a outro é da ordem de O(log(|V|)).
se quisermos representar um grafo esparso G, podemos usar a representação em coleção de listas de adjacências, por questões de
economia de espaçode armazenamento. O espaço necessário para armazenar os elementos é da ordem de O(|E| + |V|).
o tempo de acesso a um vértice adjacente a outro e o espaço de armazenamento ocupado não mudam quando representamos um
grafo por meio de coleção de listas de adjacências ou por meio de matriz de adjacências, dado que as duas representações são
intercambiáveis.
Salvar todas as respostas Salvar e Enviar
 Estado de Conclusão da Pergunta: