Baixe o app para aproveitar ainda mais
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
Compartilhar