Buscar

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

Prévia do material em texto

Solução
PCS3110 - Algoritmos e Estrutura de Dados para Engenharia Elétrica Prova 2 - 14/10/2016
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
Romero
4
Anarosa
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.
Solução
[2,6 pontos] Questão 1
Seja D = (V,E) um dígrafo. Um passeio em um dígrafo é uma sequência de vértices (v0, v1, · · · , vk−1, vk) tais que,
para todo i, (vi−1, vi) é uma aresta, sendo v0 a origem do passeio e vk seu término. Dizemos que um vértice x ∈ V é
acessível a partir de v ∈ V se existe um passeio ligando v a x. Definimos território de um vértice v como o conjunto
X(v) ⊆ V que contém todos os vértices x ∈ V que são acessíveis a partir de v.
a [0,5 pontos] Seja Eh-acessivel(D,s,t) um algoritmo que verifica se um vértice t de um dígrafo D é acessível a
partir de s, devolvendo TRUE em caso positivo e FALSE caso contrário. Considere o algoritmo Territorio(D,s),
que calcula o território de s. Para o dígrafo da figura indique, marcando todos os seus vértices, os territórios
X(6), X(3).
Territorio(D,s)
1 X = ∅
2 for each t ∈ D.V
3 if Eh-acessivel(D,s,t)
4 X = X ∪ {t}
5 return X
X(6)
A
1
B
2
C
3
D
4
E
5
F
6
X(3)
A
1
B
2
C
3
D
4
E
5
F
6
b [0,6 pontos] Podemos afirmar que se X(v) é o território de um vértice v então nenhuma aresta sai de X(v).
Verdadeiro Falso
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4
Justifique se verdadeiro ou dê um contra-exemplo se falso.
Se existe t /∈ X(V ) então t não é acessível a partir de v. Suponhamos que exista x ∈ X(v) tal que
(x, t) ∈ D.E. Então existe o passeio (v, · · · , x, t) e t é acessível a partir de v e t ∈ X(v), contrariando
nossa hipótese inicial.
c [0,9 pontos] Escreva um algoritmo Fortemente-conexo(D) que tem como entrada o dígrafo D e retorna TRUE
se D é fortemente conexo ou FALSE caso contrário. Você pode usar o(s) algoritmo(s) Territorio(D,s) ou
Eh-acessivel(D,s,t) e, no máximo, 5 linhas de código (cada linha contendo uma instrução e comentários
pertinentes).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3 5 9
Dizemos que um dígrafo D é fortemente conexo se para cada vértice de D podemos acessar todos os
outros vértices de D.
Fortemente-conexo(D) Uma solução
1 for each v ∈ D.V
2 X = Territorio(D,v)
3 if |X| 6= |D.V|
4 return FALSE
5 return TRUE
Solução
d [0,6 pontos] O algoritmo Eh-acessivel(D,s,t) pode ser implementado através de pequenas alterações no algo-
ritmo BFS(G,s). Complete as linhas faltantes de Eh-acessivel(D,s,t) para que ele verifique se t é acessível a
partir de s.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3 6
Eh-acessível (D,s,t) Uma solução
1 for each u ∈ G.V - {s}
2 u.cor = BRANCO u.pred = NIL
3 s.cor = CINZA s.pred = NIL
4 Seja Q uma nova Fila // Q = ∅
5 Enqueue(Q,s)
6 while not Queue-Empty(Q) // Q 6= ∅
7 u = Dequeue(Q)
8 for each v ∈ G.Adjacencia[u]
9 if v == t
10 return TRUE
11 if v.cor == BRANCO
12 v.cor = CINZA
13 v.pred = u
14 Enqueue(Q,v)
15 u.cor = PRETO
16 return FALSE
BFS (G,s)
1 for each u ∈ G.V - {s }
2 u.cor = BRANCO u.pred = NIL
3 s.cor = CINZA s.pred = NIL
4 Seja Q uma nova Fila // Q = ∅
5 Enqueue(Q,s)
6 while not Queue-Empty(Q) // Q 6= ∅
7 u = Dequeue(Q)
8 for each v ∈ G.Adjacencia[u]
9 if v.cor == BRANCO
10 v.cor = CINZA
11 v.pred = u
12 Enqueue(Q,v)
13 u.cor = PRETO
Solução
[2,6 pontos] Questão 2
Em 2015, Max Howell, criador do software Homebrew (para Mac), publicou uma mensagem no seu Twitter alegando
que foi reprovado no processo seletivo do Google por não saber escrever um algoritmo para inverter uma Árvore Binária
durante uma entrevista.
No tweet original de Max Howell não está claro o que significa exatamente �inverter� uma Árvore Binária. Em um
tweet posterior ele explicou que, na verdade, era inverter uma Árvore Binária de Busca (ABB): os nós da ABB deveriam
ser alterados de posição de modo que o percurso em ordem simétrica imprima as chaves em ordem decrescente (do
maior para o menor) ao invés de imprimi-las em ordem crescente (que seria o normal).
a [0,4 pontos] Inverta a ABB apresentada abaixo.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 .5 1 2 3 4
Árvore Original
9
2
1 5
7 12
11 14
Árvore Invertida
9
12
14 11 2
5 1
7
b [0,3 pontos] Assinale as alternativas que indicam o percurso em pré-ordem da árvore original (não invertida).
1
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
2
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
3
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
4
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
5
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
6
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
7
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
8
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
c [0,3 pontos] Assinale as alternativas que indicam o percurso em pré-ordem da árvore invertida.
Solução
1
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
2
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
3
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
4
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
5
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
6
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
7
o
A
1
B
2
C
5
D
7
E
9
F
11
G
12
H
14
8
o
A
1
B
2C
5
D
7
E
9
F
11
G
12
H
14
d [1,0 ponto] Complete o algoritmo recursivo Inverte(raiz) que inverte uma ABB.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 .5 1 2 3 4 5 6 7 8 9 10
Inverte(raiz) Uma solução
1 if raiz == NIL
2 return
3 esquerda = no.filho-esquerda
4 no.filho-esquerda = no.filho-direita
5 no.filho-direita = esquerda
6 Inverte(no.filho-esquerda)
7 Inverte(no.filho-direita)
8
9
Antes que Max Howell explicasse o que significava �inverter uma árvore�, algumas pessoas imaginaram que o algoritmo
deveria colocar a árvore de cabeça para baixo, ou seja, o filho de um nó x deveria se tornar pai de x.
Solução
e [0,3 pontos] Coloque a ABB a seguir de cabeça para baixo.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 .5 1 2 3
Árvore Original
9
2
1 5
7 12
11 14
Árvore de cabeça para baixo
9
1 5
7 12
2 11 14
f [0,3 pontos] Considerando a definição de árvore, o grafo obtido com a árvore de cabeça para baixo ainda é uma
árvore? Justifique.
Sim Não
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 .5 1 2
Solução
[4,8 pontos] Testes
Teste 29 Com relação ao algoritmo de Kruskal e o grafo Q, assinale a alternativa correta.
Kruskal(G)
1 Seja A um conjunto de arestas
2 for each v ∈ G.V
3 Cria-Conjunto(v)
4 Seja Arestas uma lista de arestas
5 Arestas = G.E
6 Ordena-Crescente(Arestas) // pelo peso
7 for each (u,v) ∈ Arestas
8 if Encontra-Conjunto(u)6=Encontra-Conjunto(v)
9 A = A ∪ {(u,v)}
10 União(u,v)
11 return A
A
A linha 6 do algoritmo de Kruskal poderia ser dispensada; nesse caso o resultado poderia variar, em função da
ordem das arestas, mas sempre chegaria ao resultado correto.
B
Executando-se o algoritmo para o grafo Q, após executar 5 vezes o laço da linha 7, o conjunto A conterá duas
árvores, sendo que a soma dos pesos das arestas de uma delas será 7.
C
nenhuma das outras alternativas é correta.
D
Aplicando-se Kruskal no grafo Q obtém-se uma árvore, cuja soma dos pesos de suas arestas vale 29.
E
O algoritmo de Kruskal encontra os custos dos caminhos entre cada par de vértices do grafo G.
Teste 30 Considere o grafo H e assinale a alternativa correta.
A
se os vértices de H representarem cidades e as
arestas estradas, a solução do problema do cai-
xeiro viajante, a partir de a, seria um ciclo de
Euler
B
a sequência a,e,b,c,d,a define um ciclo de Euler
C
o grafo H não possui ciclo de Hamilton mas pos-
sui ciclo de Euler
D
a sequência a,d,c,b,e,a define um ciclo de Hamil-
ton
E
nenhuma das outras alternativas é correta
Teste 31 Considere o algoritmo X dado a seguir, aplicável a grafos conexos e ponderados. Assinale a alternativa
que corretamente indica o que X retorna:
A
Um ciclo euleriano máximo em G.
B
O caminho mínimo entre quaisquer dois
vértices em G.
C
Uma árvore geradora mínima de G.
D
Um ciclo hamiltoniano mínimo em G.
E
Nenhuma das outras alternativas é correta.
X(G)
1 Seja A um conjunto de arestas
2 A = G.E
3 Ordena-Decrescente(A) // ordena pelo peso
4 for each (u,v) ∈ A
5 A = A - {(u,v)}
6 if not Eh-Conexo(G.V, A) // verifica se
o grafo (G.V,A) não é conexo
7 A = A ∪ {(u,v)}
8 return (G.V, A)
Solução
Teste 32 O código de Huffman foi utilizado para representar textos com (somente) os seguintes caracteres:
α, β, χ, δ, �, ϕ. Para a geração do código ótimo, as frequências de ocorrência de cada caractere foi medida, sendo
fornecida na tabela a seguir (à esquerda). Assinale a alternativa que corresponde à Árvore de Huffman ótima gerada,
que tenha a menor altura. Cada árvore das alternativas está representada em seu percurso pré-ordem, com vértices
nomeados em ordem alfabética (da raiz para as folhas, da esquerda para a direita), com a aresta de peso 0 (com a
menor frequência) à esquerda do pai e a de peso 1 (com a maior frequência), à direita do pai. As folhas da árvore
possuem o respectivo caractere, dado entre parênteses. Por exemplo, a árvore a seguir (à direita) seria representada
por a, b(x), c(y) e corresponderia a dois caracteres, x e y, com respectivamente as frequências 2 e 3 de ocorrência.
caractere α β χ δ � ϕ
frequência 10 9 6 3 1 5
a
b c
0 1
x y
A
d(β), b, e(χ), a, f(α), c, h(ϕ), g, j(δ), i, k(�).
B
a, b, d(χ), e(β), c, f, h, j(�), k(δ), i(ϕ), g(α).
C
a, b, d(�), e(δ), c, f(ϕ), g, h(α), i, j(χ), k(β).
D
d(α), b, e(χ), a, f(β), c, h(ϕ), g, j(�), i, k(δ).
E
Nenhuma das outras alternativas é correta.
Teste 33 Considere o grafo G e assinale a alternativa correta.
A
não é possível obter, a partir do vértice 1 de G,
uma árvore geradora que seja binária e cheia
B
a menor altura possível para uma árvore gera-
dora de G, a partir do vértice 1, é 1
C
nenhuma das outras alternativas é correta
D
a busca em largura em G, a partir do vértice 1 e
seguindo a ordem numérica sempre que possível,
gera uma árvore binária com raiz no vértice 1
E
a busca em profundidade em G, a partir do vér-
tice 1 e seguindo a ordem numérica sempre que
possível, gera uma árvore binária com raiz no
vértice 1
Teste 34 Considere as seguintes afirmações:
I Um dígrafo (grafo dirigido ou orientado) admite ordenação topológica se e somente se for acíclico.
II É possível definir uma ordenação topológica em um grafo não dirigido.
III O algoritmo de ordenação topológica tem como cerne o BFS (Busca em Largura).
Assinale a alternativa correta em relação à veracidade das afirmações:
A
Somente I é verdadeira.
B
Somente III é verdadeira.
C
Somente I e II são verdadeiras.
D
Nenhuma das outras alternativas é correta.
E
Todas afirmações são verdadeiras.
Solução
Teste 35 Uma pequena fábrica tem cinco máquinas � 1, 2, 3, 4, 5 � e seis operários � A, B, C, D, E, F. A
tabela a seguir especifica as máquinas que cada operário sabe operar. A relação entre operários e máquinas pode ser
representada por um grafo bipartido G. Considere as seguintes afirmações acerca de G:
1. G é um grafo regular.
2. D é um vértice isolado.
3. O grau do vértice 3 é 3.
4. G é um grafo completo K6,5, com |G.V| = 6+5
5. A ordem de G é 11.
6. G é um grafo conexo.
operários máquina
A 2, 3
B 1, 2, 3, 4, 5
C 3
D
E 2, 4, 5
F 2, 5
Assinale a alternativa correta em relação à veracidade das afirmações:
A
Somente 4 e 6 são falsas.
B
Somente 1, 2 e 3 são verdadeiras.
C
Somente 2, 3 e 5 são verdadeiras.
D
Todas afirmações são verdadeiras.
E
Nenhuma das outras alternativas é correta.
Teste 36 Aplicando-se o algoritmo de Dijkstra no Dígrafo D, a partir do vértice a, obtém-se para os vértices
a,b,c,d,e,f,g, respectivamente:
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)
A
custos dos caminhos mínimos: 0,1,2,7,7,5,2 / predecessores: NIL,a,g,c,a,a,b
B
custos dos caminhos mínimos: 0,1,2,7,7,5,2 / predecessores: NIL,a,b,a,a,g,b
C
custos dos caminhos mínimos: 0,1,3,8,7,6,2 / predecessores: NIL,a,b,a,a,g,b
D
nenhuma das outras alternativas
E
custos dos caminhos mínimos: 0,1,3,8,7,6,2/ predecessores: NIL,a,g,c,a,a,b

Outros materiais