Buscar

Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P3 2014

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
 
 
 
Professores: 
 Anna Helena Reali Costa (Turma 1) 
Fabio Levy Siqueira (Turma 2) 
Romero Tori (Turma 3) 
 
3
a
. Prova 
 
25 de Novembro de 2014 
 
 
Nome: GABARITO NUSP: _______________Turma: _____ 
 
 
 
INSTRUÇÕES 
 
 
1) Esta prova contém 2 (duas) questões dissertativas e 8 (oito) testes. Verifique atentamente se todas 
elas estão presentes. Em caso de dúvida, chame o professor. 
2) Preencha IMEDIATAMENTE o seu nome e o seu número USP na capa da prova e no espaço 
reservado para as respostas aos testes. Provas não identificadas não serão corrigidas. 
3) Resolva as questões dissertativas apenas nas folhas de questão. 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 ou qualquer dispositivo eletrônico. 
6) É proibido retirar o grampo da prova. 
7) A interpretação das questões 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 e PODE SER FEITA COM LÁPIS (DESDE QUE LEGÍVEL). 
9) A Folha óptica deve ser preenchida com caneta preta ou azul, enchendo totalmente cada espaço e 
sem vazá-lo. 
Boa prova! 
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
GABARITO 
Questão 1 (2,6 pontos) Utilize o grafo dirigido ponderado P e o Algoritmo de Dijkstra para responder ao 
ítens desta questão que deles necessitarem. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Dijkstra(G, origem) 
1 for each u  G.V // Inicializa caminho 
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 = Extrair-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) (0,5 ponto) Aplique o Algoritmo de Dijkstra no Grafo G, tendo como origem o vértice a. 
Apresente o resultado final na tabela abaixo. Sempre que possível, use a ordem lexicográfica. 
 
vértices a b c d e f g 
Caminho 
 
0 7 6 5 3 1 2 
Predecessor 
 
NIL e a a g a f 
 
 
b) (0,5 ponto) Informe o caminho e o custo indicado pelo Algoritmo de Dijkstra para se ir de: 
 
a a b: caminho: a f g e b custo: 7 
 
a a e: caminho: a f g e custo: 3 
 
Grafo P 
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
c) (0,3 ponto) O que poderia ocorrer de errado se, contrariando o requisito do algoritmo de 
Dijkstra, o grafo G tivesse uma ou mais arestas com peso negativo ? Justifique, considerando 
que o algoritmo é guloso. 
Pode ocorrer que um caminho mais custoso, mas que atinja a aresta com peso negativo, seja 
compensatório, mas como o Algoritmo de Dijkstra não usa programação dinâmica, não teria 
como prever isso. Outro problema seriam ciclos com caminhos de peso negativo. Se o 
resultado do percurso do ciclo der negativo, quanto mais vezes se passar por esse ciclo menor 
será o custo. 
 
d) (0,3 ponto) Se todas as arestas do grafo G possuíssem pesos iguais indique um algoritmo de 
árvore geradora que poderia ser utilizado para obtenção de caminhos mínimos, e de que forma. 
Justifique. 
Busca em largura, Prim ou Kruskal resolveriam. Busca em profundidade não funcionaria. 
 
e) (1,0 ponto) O algoritmo “Imprime-Caminho(G, origem)” abaixo recebe como parâmetro um 
grafo G, executa o algoritmo de Dijkstra sobre G para a origem, também passada como 
parâmetro, e em seguida imprime a sequência de vértices e o respectivo custo dos caminhos 
mínimos do vértice origem para cada um dos demais vértices. 
Exemplo do formato de saída 
(para um suposto grafo G de vértices A,B,C e D, com origem em A ): 
Caminho: A C D B Custo: 15 
Caminho: A C Custo: 10 
Caminho: A C D Custo: 13 
 
Imprime-Caminho(G, origem) 
1 Dijkstra(G, origem) 
2 seja S uma nova pilha vazia 
3 for each u  G.V –{origem] 
4 proximo = u 
5 while proximo  origem 
6 Push(S, proximo) 
7 proximo = proximo.antecessor 
8 Imprime “Caminho: “ + origem + “ “ 
9 while NOT Stack-Empty(S) 
10 Imprime Pop (S)+ “ “ 
11 Imprime “Custo: ” + u.caminho + \n 
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
Questão 2 (2,6 pontos) Considere uma determinada árvore binária de busca A. Esta árvore foi 
percorrida em pré-ordem e resultou a seguinte sequência de impressão de chaves: 50, 30, 20, 15, 25, 
40, 70, 60, 80; e, no percurso em pós-ordem, gerou a seguinte sequência de impressão de chaves: 15, 
25, 20, 40, 30, 60, 80, 70, 50. 
a) (0,5 pontos) Desenhe a árvore binária de busca A. 
 
 
 
 
b) (0,4 pontos) A inserção de um nó em uma árvore binária de busca (ABB) resulta em 
uma árvore que deve continuar sendo uma ABB. Considere a ABB abaixo. Complete-a 
(mantendo todos nós já existentes, em suas respectivas posições) para apresentar o 
resultado da inserção dos seguintes dados, nesta ordem: 6, 3, 9, 2, 4, 7. Deixe bem claro 
quem é filho da esquerda e quem é filho da direita. 
 
c) (0,5 pontos) Complete o algoritmo recursivo de inserção de novos nós em uma ABB: 
algoritmo abb-insere (raiz, dado). Lembre que, a cada dado inserido, a árvore 
continua sendo uma ABB. Este algoritmo retorna a raiz da ABB. 
 
 abb-insere (raiz, dado) 
01. if raiz == NIL 
02. Seja new um novo nó //cada nó tem 3 atributos: dado, filho-esquerda e filho-direita. 
03. new.chave = dado 
04. new.filho-esquerda = NIL 
05. new.filho-direita = NIL 
06. return new 
07. if dado < raiz.chave 
08. raiz.filho-esquerda = abb-insere(raiz.filho-esquerda, dado) 
09. elseif dado > raiz.chave 
10. raiz.filho-direita = abb-insere(raiz.filho-direita, dado) 
11. return raiz 
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
 
d) (0,7 pontos) Complete o algoritmo recursivo de remoção de nós de uma ABB, algoritmo 
abb-remove(raiz,dado), mantendo a árvore como uma ABB. O algoritmo considera 
três casos de remoção de um nó de uma ABB: (1) O nó é folha; neste caso, o nó pode ser 
retirado sem problema; (2) O nó possui uma única sub-árvore (esq./dir.); neste caso, o nó-
raiz da sub-árvore (esq./dir.) pode substituir o nó eliminado; (3) O nó possui duas sub-
árvores; neste caso, o nó cuja chave seja a menor da sub-árvore direita pode substituir o nó 
eliminado (ou, alternativamente, o de maior valor da sub-árvore esquerda pode substituí-lo). 
 
 abb-remove(raiz,dado) 
01. if raiz == NIL 
02. return NIL 
03. if dado == raiz.chave // deve remover a raiz 
04. if raiz.filho-esquerda == NIL and raiz.filho-direita == NIL 
05. raiz = NIL 
06. elseif raiz.filho-esquerda == NIL 
07. raiz = raiz.filho-direita 
08. elseif raiz.filho-direita == NIL 
09. raiz = raiz.filho-esquerda 
10. else //possui dois filhos 
11. f = raiz.filho-direita 
12. while f.filho-esquerda  NIL 
13. f = f.filho-esquerda 
14. raiz.chave = f.chave 
15. f.chave = dado 
16. raiz.filho-direita = abb-remove(raiz.filho-direita, dado) 
17. elseif dado < raiz.chave 
18. raiz.filho-esquerda = abb-remove(raiz.filho-esquerda, dado) 
19. else 
20. raiz.filho-direita = abb-remove(raiz.filho-direita, dado) 
21. return raize) (0,5 pontos) Desenhe como ficaria a ABB original dada no item (b) após a remoção do nó de chave 
10 usando o algoritmo abb-remove. 
 
 
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
Testes (valor: 4,8 pontos) 
 
T1. Considere o problema da devolução de troco utilizando-se uma quantidade mínima de moedas. 
Podemos ter duas abordagens para este problema de otimização: escolha gulosa e programação 
dinâmica (PD). Considere ainda que a escolha gulosa utilize a seguinte estratégia: devolver o máximo 
de moedas de mais alto valor. Assim, se possuirmos o seguinte conjunto de moedas (quantas forem 
necessário, de cada valor): 1, 10, 25 e 50 centavos, qual seria a solução dada por cada abordagem para 
fornecer um troco de 30 centavos? 
a) Escolha gulosa: 25, 1, 1, 1, 1, 1. PD: 10, 10, 10. 
b) Escolha gulosa: 10, 10, 10. PD: 10, 10, 10. 
c) Escolha gulosa: 1, 1, ..., 1 (30 moedas de 1 centavo). PD: 25, 1, 1, 1, 1, 1. 
d) Escolha gulosa: 25, 1, 1, 1, 1, 1. PD: 25, 1, 1, 1, 1, 1. 
e) Escolha gulosa: 1, 1, ..., 1 (30 moedas de 1 centavo). PD: 1, 1, ..., 1 (30 moedas de 1 centavo). 
Alternativa a. 
T2. Considere o grafo bipartido completo K3,2, com V={{a,b,c}, {d,e}}, e os percursos em busca em 
largura (BFS) e em busca em profundidade (DFS) para encontrar uma árvore geradora. Assinale a 
alternativa correta sobre afirmações após os percursos, considerando a ordem lexicográfica sempre que 
possível. 
a) A árvore resultante em BFS possui altura = 2 e E={(a,b), (b,c), (a,d), (d,e)}, na ordem de inserção na 
árvore. A árvore resultante em DFS possui altura = 4 e E={(a,b), (b,c), (c,d), (d,e)}, na ordem de 
inserção na árvore. 
b) A árvore resultante em BFS possui altura = 3 e E={(a,d), (a,e), (d,b), (d,c)}, na ordem de inserção na 
árvore. A árvore resultante em DFS possui altura = 5 e E={(a,d), (d,b), (b,e), (e,c)}, na ordem de 
inserção na árvore. 
c) A árvore resultante em BFS possui altura = 3 e E={(a,b), (b,c), (a,d), (d,e)}, na ordem de inserção na 
árvore. A árvore resultante em DFS possui altura = 5 e E={(a,b), (b,c), (c,d), (d,e)}, na ordem de 
inserção na árvore. 
d) A árvore resultante em BFS possui altura = 2 e E={(a,d), (a,e), (d,b), (d,c)}, na ordem de inserção na 
árvore. A árvore resultante em DFS possui altura = 4 e E={(a,d), (d,b), (b,e), (e,c)}, na ordem de 
inserção na árvore. 
e) Não existem árvores geradoras neste grafo. 
Alternativa d. 
T3. Considere as letras e suas respectivas frequências de ocorrência em textos, com <letra, 
frequência>: <A,28>, <B,8>, <C,22>, <D,12>, <E,30> e construa a respectiva árvore do código 
de Huffman, cujo pseudo-código encontra-se a seguir. Assinale a alternativa correta sobre a altura da 
árvore gerada e o correspondente código para DECADA. 
Huffman(C) 
1. n = |C| // Número de caracteres 
2. Seja Q uma nova Fila de Prioridades 
3. Q = C 
4. for i = 1 to n – 1 // cada iteração tira 1 elemento 
5. Seja z um novo Nó 
6. x = Extrair-Menor(Q) 
7. y = Extrair-Menor(Q) 
8. z.filho-esquerda = x 
9. z.filho-direita = y 
10. z.frequencia = x.frequencia + y.frequencia 
11. Insert(Q, z) 
12.return Extrair-Menor(Q) 
a) Altura = 4, código: 1101011110110110 
b) Altura = 3, código: 00111011000110 
c) Altura = 4, código: 00111011000110 
d) Altura = 3, código: 1101011110110110 
e) Nenhuma das outras alternativas está correta. 
Alternativa b 
 
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
T4. Assinale a alternativa que indica como devem ser as condições nas linhas 4 e 7 para que o 
algoritmo É-Ciclo-Hamilton verifique se o caminho C no grafo G é um ciclo de Hamilton, ou seja, 
é um ciclo que contém cada vértice em G exatamente uma vez, exceto o vértice de início e fim. 
É-Ciclo-Hamilton(G, C) 
1 Seja Vertices um novo Conjunto 
2 Vertices = G.V 
3 for i = 1 to C.tamanho – 1 
4 if __________________________ 
5 Remover(Vertices, C[i + 1]) // Remove C[i + 1] do conjunto Vértices 
6 else return false 
7 if ____________________________ 
8 return false 
9 return true 
 
a) Linha 4: Possui-Aresta(G, C[i], C[i + 1]) and C[i + 1]  Vertices 
Linha 7: not Está-Vazio(Vertices) or C[1] != C[C.tamanho] 
b) Linha 4: Possui-Aresta(G, C[i], C[i + 1]) and C[i + 1]  Vertices 
Linha 7: not Está-Vazio(Vertices) or C[1] != C[C.tamanho] 
c) Linha 4: Possui-Aresta(G, C[i], C[i + 1]) and C[i + 1]  Vertices 
Linha 7: Está-Vazio(Vertices) or C[1] != C[C.tamanho] 
d) Linha 4: Possui-Aresta(G, C[i], C[i + 1]) and C[i + 1]  Vertices 
Linha 7: Está-Vazio(Vertices) or C[1] != C[C.tamanho] 
e) Linha 4: Possui-Aresta(G, C[i], C[i + 1]) and C[i + 1]  Vertices 
Linha 7: Está-Vazio(Vertices) or C[1] == C[C.tamanho] 
Alternativa b 
T5. A respeito da representação de grafos, quais alternativas são corretas? 
 
I) A matriz de adjacência requer Θ(|V|2) de memória, enquanto que a lista de adjacência requer Θ(|V| + |E|) 
de memória. Verdadeira. 
II) É importante a ordem em que os vértices estão na lista ligada de um determinado vértice na lista de 
adjacência. Falsa. A ordem não é relevante. 
III) Grafos bipartidos completos não podem ser representados por matrizes de adjacências. Falsa. O grafo 
pode ser representado. 
IV) A matriz de adjacência M corresponde ao grafo G. Verdadeira. 
M = a b c d 
G = 
 a 
 
0 1 1 1 
 
 
 b 1 1 0 1 
 c 1 0 0 0 
 d 1 1 0 0 
a) I e II b) II e III c) III e IV d) I e IV e) II e IV Alternativa d. 
T6. Seja um grafo dirigido de ordem 5 com o seguinte conjunto de arestas E = {(1,2), (1,3), (1,4), 
(2,3), (2,4), (4,3), (5,1), (5,2), (5,4)}. Assinale a alternativa que indique uma ordenação topológica 
correta para este grafo. 
a) <1, 2, 3, 4, 5> 
b) <1, 2, 3, 5, 4> 
c) <5, 1, 2, 4, 3> 
d) <5, 1, 2, 3, 4> 
e) Nenhuma das outras alternativas está correta. 
Alternativa c. 
a b
c d
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
T7. O algoritmo abaixo implementa o algoritmo de Prim para encontrar uma árvore geradora 
mínima de um grafo simples conexo G, ponderado (pesos positivos), a partir da matriz de adjacências 
M que o representa (mij = mji = peso da aresta ij, se essa existe, ou mij = mji = ∞ , se não existe aresta 
ij; mii = 0). Assinale a alternativa cprreta. 
Prim-MA (M, v) // M: Matriz de Adjacências; v: número de vértices 
1 Seja V um Conjunto de inteiros (representando vértices); V = {1} 
2 Seja A um Conjunto de pares ordenados (representando arestas); A = { } 
3 while V ≠ {} // enquanto houver vértices a analisar 
4 menorPG = ∞ 
5 for each u  V 
6 menorPL = ∞ 
7 for j = 1 to v //obtém o menor peso na linha u 
8 if u ≠ j AND M[u][j] < menorPL 
9 V1 = u 
10 V2 = j 
11 menorPL = M[u][j] 
12 if menorPL == ∞ //essa linha não precisa mais ser analisada 
 
13 V = V - {u} 
14 else if menorPL < menorPG 
15 menorPG = menorPL 
16 menorV1 = V1 
17 menorV2 = V2 
18 if menorPG ≠ ∞ 
19 A = A  {(menorV1, menorV2) } 
 
20 V = V  {menorV2} 
21 M[menorV1][menorV2] = ∞ //marca aresta (menorV1,menorV2) como visitada 
22 M[menorV2][menorV1] = ∞ 
23 return A 
a) Linha 13: V = V - {j} Linha 20: V = V  {menorV1} 
b) Linha 13: V = V - {u} Linha 20: V = V  {menorV1} 
c) Linha 13: V = V - {j} Linha 20: V = V  {menorV2} 
d) Linha 13: V = V - {u} Linha 20: V = V  {menorV1, menorV2} 
e) Nenhuma das demais alternativas é correta 
Alternativa e. (foi aceita tambem a alternativa d, porque também funcionaria, apesar de não ser 
necessário incluir o vértice V1 na linha 20, nem fazer sentido para a lógica do programa, porV1 já 
fazer parte da lista. 
T8. Com relação à Teoria de Grafos, quais alternativas são corretas? 
 
I) As matrizes de adjacências M1 e M2 representam grafos conexos com ciclos. 
II) No grafo representado pela matriz de adjacências M1 tem-se que (a,c,b,a) não é um caminho simples, 
mas é um ciclo simples. 
III) Os grafos representados pelas matrizes de adjacências M1 e M2 são isomorfos. 
 
 
 
 
 
 
a) I, II e III são corretas 
b) somente I é correta 
c) somente III é incorreta 
M1= a b c d M2= a b c d 
 a 
 
0 1 1 0 
 
 a 
 
1 1 1 1 
 
 b 1 1 1 1 b 1 0 0 0 
 c 1 1 1 0 c 1 0 0 1 
 d 0 1 0 0 d 1 0 1 1 
PCS 3110 Algoritmos e Estrutura de Dados para a Engenharia Elétrica 
d) somente II é incorreta 
e) I, II e III são incorretas Alternativa a

Outros materiais