Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P2 2015

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

GABARITO
PCS3110 - Algoritmos e Estrutura de Dados para Engenharia Elétrica Prova 2 - 13/10/2015
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: �. Não use �.
1 Anna 2 Fábio 3 Anarosa 4 Romero
Marque as caixas ao lado para formar o seu número USP e escreva seu nome
abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instruções para a prova
1 Esta prova contém 2 questões dissertativas e 8 testes. Verifique atentamente se todas elas estão presentes. Em
caso de dúvida chame o professor.
2 Preencha seu nome e número USP. Provas não identificadas não serão corrigidas.
3 Resolva as questões dissertativas apenas no espaço a elas reservado. Respostas fornecidas fora do local a elas
destinadas não serão corrigidas.
4 A duração total da prova é de 100 minutos.
5 É proibido o uso de calculadoras e qualquer outro aparelho eletrônico.
6 É proibido retirar o grampo da prova.
7 A interpretação da questão faz parte da avaliação dos alunos. Caso considere alguma hipótese que não esteja
explicitada no enunciado, indique claramente na resposta.
8 A prova é SEM CONSULTA.
Boa Sorte!
GABARITO
A seguir você encontra os algoritmos usados na prova:
BFS (G)
1 for each u ∈ G.V - {s }
2 u.cor = BRANCO
3 u.pred = NIL
4 s.cor = CINZA
5 s.pred = NIL
6 Seja Q uma nova Fila // Q = ∅
7 Enqueue(Q,s)
8 while not Queue-Emty(Q) // Q 6= ∅
9 u = Dequeue(Q)
10 for each v ∈ G.Adjacencia[u]
11 if v.cor == BRANCO
12 v.cor = CINZA
13 v.pred = u
14 Enqueue(Q,v)
15 u.cor = PRETO
DFS-Recursiva (G,s)
1 for each v ∈ G.V
2 v.cor = BRANCO
3 v.pred = NIL
4 DFS-Visit(G,s)
DFS-Visit (G,u)
1 u.cor = CINZA
2 for each v ∈ G.Adjacencia[u]
3 if v.cor == BRANCO
4 v.pred = u
5 DFS-Visit(G,v)
6 u.cor = PRETO
Topological-Sort (G)
1 DFS-rec-comTempo (G) // para obter
v.fim
// de cada vértice v
2 Seja L uma nova Lista Ligada
3 for each v ∈ G.V
4 Insert(L, v)
5 Sort-Decrescente(L) // fim é a chave
6 return L
DFS-rec-comTempo (G)
1 for each v ∈ G.V
2 v.cor = BRANCO; v.pred = NIL
3 tempo = 0
4 for each v ∈ G.V
5 if v.cor == BRANCO
6 tempo = Dfs-comTempo(G, v, tempo)
Dfs-comTempo (G, u, tempo)
1 tempo = tempo + 1
2 u.cor = CINZA
3 for each v ∈ G.Adjacencia[u]
4 if v.cor == BRANCO
5 v.pred = u
6 tempo = Dfs-comTempo(G, v, tempo)
7 u.cor = PRETO
8 tempo = tempo + 1
9 u.fim = tempo
10 return tempo
GABARITO
Preorder-Tree-Walk (x)
1 if x 6= NIL
2 print = x.chave
3 Preorder-Tree-Walk(x.filho-esquerda)
4 Preorder-Tree-Walk(x.filho-direita)
Inorder-Tree-Walk (x)
1 if x 6= NIL
2 Inorder-Tree-Walk(x.filho-esquerda)
3 print = x.chave
4 Inorder-Tree-Walk(x.filho-direita)
Postorder-Tree-Walk (x)
1 if x 6= NIL
2 Postorder-Tree-Walk(x.filho-esquerda)
3 Postorder-Tree-Walk(x.filho-direita)
4 print = x.chave
MST-Prim (G,inicial)
1 Seja A um Conjunto de arestas
2 A = ∅
3 for each u ∈ G.V
4 u.chave =∞
5 u.adajcente = NIL
6 inicial.chave = 0
7 Seja Q uma Fila de Prioridade
8 Q = G.V // coloca em Q todos os vértices
9 while not Queue-Empty(Q)
10 menor = Extrai-Menor(Q)
11 if menor 6= inicial
12 A = A ∪ (menor,menor.adjacente)
13 for each v ∈ G.Adjacencia[menor]
14 if v ∈ Q and peso(G,menor,v) < v.chave
15 v.adjacente = menor
16 v.chave = peso(G,menor,v)
17 Altera-Prioridade(Q,v)
18 return A
Dijkstra (G, origem)
1 for each u ∈ G.V // inicialização
2 u.caminho = ∞
3 u.predecessor = NIL
4 origem.caminho = 0
5 Seja Q uma Fila de Prioridade
6 Q = G.V // coloca em Q todos os vértices
7 while not Queue-Empty(Q)
8 menor = Extrai-Menor(Q) // Q = Q-menor
9 for each v ∈ G.Adjacencia[menor]
10 if v.caminho > peso(G,menor,v) +
menor.caminho
11 v.predecessor = menor
12 v.caminho = peso(G,menor,v) +
menor.caminho
13 Altera-Prioridade(Q,v)
Huffman (C)
1 n = |C| // número de caracteres
2 Seja Q uma Fila de Prioridade
3 Q = C // coloca em Q todos os caracteres
4 for i = 1 to n-1 // tira 1 elemento a
cada iteração
5 Seja z um novo Nó
6 x = Extrai-Menor(Q)
7 y = Extrai-Menor(Q)
8 z.filho-esquerdo = x
9 z.filho-direito = y
10 z.frequencia = x.frequencia + y.frequencia
11 Insert(Q,z)
12 return Extrai-Menor(Q)
GABARITO
[2,6 pontos] Questão 1
(a) [0,4 pontos] Para o grafo G da figura obtenha uma árvore geradora de G que, percorrida em pós ordem, imprime
a expressão cb+ 2 ∗ ad+ /. Apresente-a na árvore binária do espaço à direita de G, indicando em cada vértice
seu valor e ligando cada vértice filho a seu pai. Devem sobrar vértices não preenchidos.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 8
GABARITO
(b) [1,6 pontos] Dado o grafo G1, construa uma árvore geradora utilizando o método da busca em largura (BFS),
adotando a ordenação alfabética de vértices e iniciando a busca pelo vértice a.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 6
Aceitei duas respostas porque o algoritmo não foi dado, considerei raciocínio sobre o grafo
GABARITO
(c) [0,6 pontos] Considere o grafo G2 mostrado a seguir. Para efeito de ordenação dos vértices e arestas dos
algoritmos, suponha que os vértices estão ordenados de acordo com a ordem alfabética e as arestas seguem a
ordem (a,b), (a,h), (b,c), (b, h), (c,d), (c,f), (c,i), (d,e), (d,f), (e,f), (f,g), (g,h), (g,i), (h,i). Considerando o uso
do Algoritmo MST-Prim com chamada (G2, c) para a obtenção da árvore geradora de custo mínimo, indique
a ordem de inserção de vértices e arestas de G2 durante sua execução.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 8 12
Sequência de inserção de vértices
Sequência de inserção de arestas (pode não ser necessário preencher todos os campos)
Custo do caminho: 45
GABARITO
[2,6 pontos] Questão 2
Para a questão, considere os grafos G1 e G2 dados abaixo:
(a) [0,4 pontos] Utilize a busca em largura (BFS) em
G1 iniciando no vértice 1 e desenhe a correspon-
dente árvore de busca gerada. Sempre que possível,
escolha a ordem numérica crescente dos vértices.
. . . . . . . Para uso do professor: 0 1 2 3 4
Altura da árvore: 4
(b) [0,4 pontos] Utilize a busca em profundidade
(DFS) em G1 iniciando no vértice 1 e desenhe a
correspondente árvore de busca gerada. Sempre
que possível, escolha a ordem numérica crescente
dos vértices.
. . . . . . . Para uso do professor: 0 1 2 3 4
Altura da árvore: 5
GABARITO
(c) [0,4 pontos]] Uma aplicação relevante de DFS é a Busca de Articulação. Um vértice em um grafo não
direcionado simples e conexo é um vértice de corte (ou articulação) se sua remoção torna o grafo resultante
desconexo. A identificação de articulação pode ser importante em redes de computadores para identificar os
pontos frágeis de uma rede. Um grafo é dito biconexo se ele não contém nenhuma articulação. Para os grafos
G1 e G2, indique quais são os vértices de corte, caso existam:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4
G1: 4, 6
G2: C, H
(d) [0,7 pontos] Desenhe a respectiva árvore geradora definida pela DFS (sempre que
possível utilize a ordem
alfabética) em G2, considerando os vértices A como raiz (quadro à esquerda) e C como raiz (quadro à direita).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 7
GABARITO
(e) [0,7 pontos] No algoritmo de Busca Articulação, os seguintes atributos de um vértice v são usados: v.cor, que
indica se o vértice já foi processado (PRETO) ou não (BRANCO) e v.nfilhos, que indica o número de filhos de
v. Uma ideia muito simples do algoritmo consiste em iniciar a DFS por cada um dos vértices do grafo e verificar
se a árvore resultante tem a raiz com dois ou mais filhos. Se tiver, o vértice raiz da árvore será uma articulação
de G. É importante ressaltar que há algoritmos muito mais eficientes do que este apresentado. Complete os
algoritmos abaixo para que Encontra-Articulacao(G) imprima os vértices de articulação de um grafo G.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 7
Encontra-Articulacao(G)
1 for each v ∈ G.V
2 for each v ∈ G.V
3 v.cor = BRANCO
4 v.nfilhos = 0
5 DFS-Art(G,v)
6 if v.filhos > 1
7 print (v “é articulação")
DFS-Art(G,v)
1 v.cor = PRETO
2 for each u ∈ G.Adjacencia[v]
3 if u.cor == BRANCO
4 v.nfilhos = v.nfilhos + 1
5 DFS-Art(G,u)
GABARITO
Teste 1 Sobre a ordenação topológica, assinale a alternativa VERDADEIRA, considerando os algoritmos Dfs-
comTempo, DFS-rec-comTempo e Topological-Sort:
A O algoritmo também retornaria uma ordem topológica válida se fosse usada a busca em largura ao invés de em
profundidade.
B A condição da linha 5 de Dfs-rec-comTempo não pode ser trocada por v.cor 6= PRETO porque se o vértice v
for CINZA o tempo de fim dele será recalculado.
C Se o tempo for inicializado com -1 na linha 3 de DFS-rec-comTempo, o algoritmo não obterá uma ordem
topológica correta.
D Se a linha 7 de Dfs-comTempo for retirada, o algoritmo nunca terminará.
E O algoritmo retorna uma ordem topológica válida independente da ordem como os vértices são processados no
for da linha 4 de DFS-rec-comTempo.
Teste 2 Considerando o seguinte grafo em que cada vértice representa um ator e cada
aresta representa um filme em que ambos os atores participaram, assinale a alternativa ERRADA:
Edward 
Norton
Woody 
Harrelson
Jennifer 
Lawrence
Jogos Vorazes
Morgan 
Freeman
Christian Bale TrapaçaLiam NeesonCruzada Batman Begins
Truque de Mestre
Batman Begins Tudo por Justiça
O Ilusionista
Batman Begins
A O grafo é bipartido.
B O grau de Christian Bale é 5 e de Liam Neeson é 3.
C Um ciclo de Hamilton nesse grafo é (Edward Norton, Christian Bale, Jennifer Lawrence, Woody Harrelson,
Morgan Freeman, Liam Neeson, Edward Norton)
D A matriz de adjacência para esse grafo deveria ter 6 linhas e 6 colunas.
E O grafo é conexo, não dirigido e simples.
Teste 3 Suponha as frequências de ocorrência de vogais, em determinado contexto, como sendo a = 50%, e = 25%,
i = 12%, o = 7%, u = 6%. Após aplicar o algoritmo de Huffman para codificar as vogais, podemos afirmar que:
A A vogal o será codificada com 3 bits.
B A vogal u será codificada com 5 bits.
C A vogal o será codificada com 3 bits.
D O número máximo de bits necessários para codificar cada vogal é 3.
E A palavra aeiou será codificada com 14 bits.
GABARITO
Teste 4 Com relação aos algoritmos gulosos, assinale a alternativa falsa.
A Os algoritmos gulosos podem gerar soluções ótimas.
B Num algoritmo guloso deve-se, a cada passo, avaliar as consequências que cada possibilidade de escolha provocará
no resultado final.
C O algoritmo guloso não necessariamente avalia todas as possibilidades para tomar decisão.
D Nem sempre um algoritmo guloso gera a melhor solução possível.
E Os algoritmos gulosos podem priorizar a velocidade de execução em detrimento da precisão do resultado.
Teste 5 Como devem ser preenchidas as linhas 3, 4, 5, 6, 10 e 12 para que seja implementado um algoritmo de
busca em profundidade iterativo em uma árvore binária?
DFS-Arvore (raiz, valorProcurado)
1 if raiz == NIL
2 return FALSE
3
4
5
6
7 if no.chave == valorProcurado
8 return TRUE
9 if no.filho-direita 6= NIL
10
11 if no.filho-esquerda 6= NIL
12
13 return FALSE
A 3 Seja Q uma nova Fila
4 Enqueue(Q, raiz)
5 while not Queue-Empty(Q)
6 no = Dequeue(Q)
10 Enqueue(Q, no.filho-direita)
12 Enqueue(Q, no.filho-esquerda)
B 3 // Nada
4 // Nada
5 if raiz 6= NIL
6 no = raiz
10 DFS-Arvore(no.filho-direita, valorProcurado)
12 DFS-Arvore(no.filho-esquerda, valorProcurado)
C 3 Seja S uma nova Pilha
4 Push(S, raiz)
5 while raiz 6= NIL
6 no = raiz
10 Push(S, no.filho-direita)
12 Push(S, no.pai.filho-esquerda)
D 3 Seja S uma nova Pilha
4 Push(S, raiz)
5 while not Stack-Empty(S)
6 no = Pop(S)
10 Push(S, no.filho-direita)
12 Push(S, no.filho-esquerda)
E 3 Seja Q uma nova Fila
4 Enqueue(Q, raiz)
5 while raiz 6= NIL
6 no = raiz
10 Enqueue(Q, no.filho-direita)
12 Enqueue(Q, no.filho-esquerda)
GABARITO
Teste 6 Seja G um grafo conexo. Sabendo-se que, dado v ∈ G.V , o algoritmo de Dijkstra calcula o menor custo para
se chegar de v a qualquer outro vértice u de G.V , além de registrar, em cada vértice u seu predecessor v.predecessor
no possível caminho mínimo de v a u indique qual das afirmações é verdadeira.
A Nenhuma das demais alternativas é correta.
B Após execução do algoritmo Dijkstra não é possível que mais de um nó possua o mesmo predecessor.
C O algoritmo Dijkstra pode ser aplicado apenas a grafos não-dirigidos.
D Após execução do algoritmo Dijkstra não é possível que mais de um nó possua o mesmo custo.
E O algoritmo Dijkstra não é um algoritmo guloso.
Teste 7 Com relação ao percurso em árvores binárias assinale a alternativa verdadeira.
A Ao fazer o percurso de uma árvore binária em “pós-ordem” todas as folhas dessa árvore são impressas antes de
todos os seus nós internos.
B O método “ordem-simétrica” só pode ser aplicado em árvores binárias cheias.
C Pelo método “pré-ordem” o nó raiz da árvore binária será sempre o último a ser impresso.
D Nenhuma das demais alternativas é correta.
E Qualquer que seja a topologia de uma árvore binária, se o percurso em “pré-ordem” gerar a sequência 1,2,3,4,5,6
o percurso em “pós-ordem” gerará a sequência 2,1,4,3,6,5.
Teste 8 Assinale a alternativa que indica como devem ser preenchidas as linhas 7 e 8 para que o algoritmo abaixo
insira um nó em uma árvore binária de busca (ABB) de tal forma que a árvore continue sendo ABB.
ABB-Insere (raiz, novo)
1 if raiz == NIL
2 return novo
3 atual = raiz
4 while atual 6= NIL
5 x = atual
6 if novo.chave > atual.chave
7
8
9 if novo.chave > x.chave
10 x.filho-direita = novo
11 else x.filho-esquerda = novo
12 return raiz
A 7. atual = raiz.filho-esquerda
8. else atual = raiz.filho-direita
B 7. atual = atual.filho-esquerda
8. else atual = atual.filho-direita
C 7. atual = atual.filho-direita
8. else atual = atual.filho-esquerda
D 7. atual = atual.pai
8. // Não faz nada
E 7. t = atual.chave; atual.chave = novo.chave; novo.chave = t
8. else atual = atual.pai