Atividade Teórica de Algoritmo e Estrutura de Dados

Segunda Lista de Exercícios Análise e Desenvolvimento de Sistemas Bacharelado em Sistemas de Informação Bacharelado em Ciência da Computação Disciplina Algoritmos e Estruturas de Dados Entrega Prova Final Professor Virgílio Borges de Oliveira 1 Fale sobre as classes de comportamento assintótico e dê exemplos de problemas que pertencem a cada classe 2 Escreva sobre o método de ordenação apresentado pelo seu grupo abordando os seguintes aspectos estratégia utilizada análise da complexidade para o melhor e o pior caso como eles ocorrem vantagens desvantagens se é eficiente e estável 3 Observe o estado inicial do vetor e o primeiro passo de sua ordenação ESTADO INICIAL 23 31 11 13 27 16 19 i 0 11 23 31 13 16 27 19 i 1 a Qual o nome do método de ordenação usado e a que classe de comportamento assintótico ele pertence b Considerando apenas as comparações existe diferença entre o melhor e o pior caso Se sim como se caracterizam c Termine a execução do algoritmo mostrando os passos restantes até a conclusão 4 Marque V para as alternativas verdadeiras e F para as falsas Faça a correção das alternativas falsas use o espaço abaixo da alternativa a Os algoritmos de ordenação eficientes pertencem a classe de comportamento Olog n b O problema de encontrar valores repetidos em um vetor pertence a classe de comportamento On c O método mais adequado para ordenar uma lista encadeada é o Inserção d O problema de pesquisar por um valor em um conjunto desordenado pertence a classe de comportamento O2N e O vetor a seguir constitui um maxHeap 40202518162324 f Para um vetor de 500 elementos o primeiro salto utilizado pelo método ShellSort será de 364 g O pior caso do método QuickSort ocorre quando sistematicamente o pivô é escolhido como sendo um dos extremos de um vetor desordenado Neste caso é da ordem de On2 comparações h O método Inserção é o mais lento para qualquer tamanho se os elementos estão em ordem descendente 5 Dado o vetor abaixo com as chaves inicialmente dispostas desta forma faça o que se pede a Mostre os passos para a construção do heap b Mostre os passos seguintes da ordenação HeapSort até a sua conclusão 6 Dado o vetor abaixo faça sua ordenação através do método ShellSort Dê os valores das variáveis h e i a cada passo use como referência o algoritmo do arquivo Ordenacaocs 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 H F A C U L D A D E C O T E M I G 13 7 Observe o seguinte método public void ordenaint vet int esq int dir int i j x temp x vetesq dir 2 i esq j dir imprimavet esq dir x do whilex veti i whilex vetj j ifi j temp veti veti vetj vetj temp i j whilei j ifesq j ordenavet esq j ifi dir ordenavet i dir a Qual o nome do método b Explique a sua estratégia c Sublinhe as linhas do código onde ocorrem as trocas relevantes para a ordenação d Considere um programa que faça a seguinte chamada ao método ordena int vet 3 1 5 7 9 vetor aleatoriamente preenchido ordenavet 0 4 chamada inicial Mostre o que será impresso o console durante a execução do método até a conclusão da ordenação e Quantas trocas foram realizadas ao todo 8 Faça uma análise comparativa entre as seguintes estruturas de dados vetores ordenados listas encadeadas árvores binárias de pesquisa e tabela hash no que diz respeito a inserção remoção e pesquisa de chaves Fale sobre as vantagens e desvantagens de cada um e como ocorrem 6 4 2 7 9 5 1 9 A árvore binária abaixo representa uma expressão matemática Faça o que se pede a Represente os níveis na figura e dê a sua altura b Mostre a sequência de chaves impressa pelo passeio Em Ordem RESPOSTA c Mostre a sequência de chaves impressa pelo passeio PréOrdem RESPOSTA d Mostre a sequência de chaves impressa pelo passeio PósOrdem RESPOSTA 10 Observe a árvore binária de pesquisa a seguir a Considerando o método abaixo mostre o que será impresso na tela após a execução da seguinte linha de comando apasseio araiz public void passeio NoArvore no if no null ConsoleWriteLine ENTROU NO NÓ nochave passeio nodir ConsoleWriteLine DIREITA FEITA nochave passeio noesq ConsoleWriteLine ESQUERDA FEITA nochave else ConsoleWriteLine NULO b Remova as seguintes chaves na sequência R M D V B faça um desenho para cada remoção 11 Sobre árvores binárias responda a Em uma árvore binária cheia quantos nós possui o nível 11 b Em uma árvore binária de altura h qual o nº mínimo de nós c Em uma árvore binária de altura h qual o nº máximo de nós d Em uma árvore binária com 4657 nós qual sua altura mínima e Desenhe uma árvore binária de grau 1 f Desenhe 5 árvores binárias diferentes com exatamente 3 nós sem variar as chaves g Defina árvore binária de pesquisa 12 Dada a função de transformação hashchave chave m sendo m13 faça o que se pede a Calcule o hash das seguintes chaves 50 25 67 68 19 1 28 63 45 80 b Distribua as chaves acima em uma tabela Hash de endereçamento aberto Qual será o pior caso de pesquisa entre as chaves inseridas e quantos testes serão necessários para encontrála c Distribua as chaves acima em uma tabela Hash de endereçamento fechado Quantos testes serão realizados na busca pela chave 89 13 A figura abaixo representa o estado de uma tabela Hash após a inserção de várias chaves compostas de caracteres Sabese que função de hash usada foi somatório dos caracteres m e o valor de cada caractere é A0 B1 C2 e assim sucessivamente 0 1 2 3 4 5 6 EAC ADF DDA FF DB EAA FAB a Qual o valor de m b Quantas colisões ocorreram nessa tabela Justifique mostrando os cálculos necessários c O pior caso na pesquisa ocorrerá quando pesquisarmos por qual chave Quantos testes serão necessários para encontrála d Quantos testes seriam necessários na busca pela chave BBA Justifique mostrando os cálculos necessários 14 Faça um novo método na classe Arvore que visite os nós em ordem decrescente de chave calcule e imprima o valor da chave seguido do grau do nó Outros métodos e variáveis auxiliares podem ser usados livremente 15 Suponha que se queira pesquisar a chave 287 em uma árvore binária de pesquisa com chaves entre 1 e 1000 Durante uma pesquisa como essa uma sequência de chaves é examinada Cada sequência abaixo é uma suposta sequência de chaves examinadas em uma busca da chave 287 I 7 342 199 201 310 258 287 II 110 132 133 156 289 288 287 III 252 266 271 294 295 289 287 IV 715 112 530 249 406 234 287 É válido apenas o que se apresenta em a I e II b II e IV c I d III e III e IV 16 ENADE 2005 Julgue os itens a seguir acerca de algoritmos para ordenação I O algoritmo de ordenação por inserção tem complexidade On log n II Um algoritmo de ordenação é dito estável caso ele não altere a posição relativa de elementos de mesmo valor III No algoritmo quicksort a escolha do elemento pivô influencia o desempenho do algoritmo IV O bubblesort e o algoritmo de ordenação por inserção fazem em média o mesmo número de comparações Estão certos apenas os itens a I e II b I e III c II e IV d I III e IV e II III e IV 17 As filas de prioridades heaps são estruturas de dados importantes no projeto de algoritmos Em especial heaps podem ser utilizados na recuperação de informação em grandes bases de dados constituídos por textos Basicamente para se exibir o resultado de uma consulta os documentos recuperados são ordenados de acordo com a relevância presumida para o usuário Uma consulta pode recuperar milhões de documentos que certamente não serão todos examinados Na verdade o usuário examina os primeiros m documentos dos n recuperados em que m é da ordem de algumas dezenas Considerando as características dos heaps e sua aplicação no problema descrito acima avalie as seguintes afirmações I Uma vez que o heap é implementado como uma árvore binária de pesquisa essencialmente completa o custo computacional para sua construção é On log n II A implementação de heaps utilizandose vetores é eficiente em tempo de execução e em espaço de armazenamento pois o pai de um elemento armazenado na posição i se encontra armazenado na posição 2i1 III O custo computacional para se recuperar de forma ordenada os m documentos mais relevantes armazenados em um heap de tamanho n é Om log n IV Determinar o documento com maior valor de relevância armazenado em um heap tem custo computacional O1 Está correto apenas o que se afirma em a I e II b II e III c III e IV d I II e IV e I III e IV 18 ENADE 2005 Considere o algoritmo que implementa o seguinte processo uma coleção desordenada de elementos é dividida em duas metades e cada metade é utilizada como argumento para a reaplicação recursiva do procedimento Os resultados das duas reaplicações são então combinados pela intercalação dos elementos de ambas resultando em uma coleção ordenada Qual é a complexidade desse algoritmo a On2 b On2n c O2n d Olog n log n e On log n Prova de Análise e Desenvolvimento de Sistemas 1 Fale sobre as classes de comportamento assintótico e dê exemplos de problemas que pertencem a cada classe Classe Definição Exemplo Constante Tempo de execução não muda com tamanho da entrada Acesso a elemento de vetor de dados Linear Tempo de execução cresce linearmente com o tamanho da entrada Percorrer elementos de lista Logaritmica Tempo de execução cresce mm ordem logaritmica com o tamanho da entrada Busca Binária Linear Logaritmica Tempo de execução Cresce em fator nlog com tamanho de entrada Merge SortQuick Sort Quadrática Tempo de execução cresce quadraticamente com o tamanho a entrada Algoritmo de ordenação ingênuas como bubble sort e Insertion sort Exponencial Tempo de execução cresce exponencialmente com o tamanho a entrada Problema de decisão baseado em algoritmos de força bruta em geral Fatorial Tempo de execução cresce fatorialmente com o tamanho a entrada Problemas de permutação como o caixeiro viajante 2 Escreva sobre o método de ordenação apresentado pelo seu grupo abordando os seguintes aspectos estratégia utilizada análise da complexidade para o melhor e o pior caso como eles ocorrem vantagens desvantagens se é eficiente e estável Método de ordenação escolhido Merge Sort Merge Sort é um algoritmo de ordenação que utiliza a estratégia Divide and Conquer Dividir para Conquistar A ideia principal é dividir o problema em subproblemas menores resolver esses subproblemas recursivamente e em seguida combinar ou mesclar as soluções dos subproblemas para formar a solução do problema original A estratégia pode ser descrita em três etapas principais dividis a lista a ser ordenada em duas metades aproximadamente iguais ordenar recursivamente cada metade e combinar mesclar as duas metades ordenadas para produzir a lista final ordenada Sobre a análise de complexidade no Merge Sort o melhor caso On log n ocorre quando a lista já está ordenada Devido à natureza do algoritmo que sempre divide a lista ao meio e realiza a fusão o tempo de execução é o mesmo independentemente da ordem inicial dos elementos Por isso para o pior caso para o Merge Sort é também On log n Sobre as vantagens do Merge Sort temos a complexidade Consistente Merge Sort tem uma complexidade de tempo On log n em todos os casos melhor pior e médio Estabilidade pois é um algoritmo de ordenação estável o que significa que ele mantém a ordem relativa dos elementos iguais Eficiência em Listas Grandes É eficiente para ordenar listas grandes especialmente quando implementado de forma paralela Desempenho Garantido Oferece um desempenho garantido de On log n ao contrário do Quick Sort que pode ter desempenho On² no pior caso Sobre as desvantagens do Merge Sort podemos atribuir o uso de Espaço Adicional Ele requere espaço adicional proporcional ao tamanho da lista que está sendo ordenada On pois utiliza listas auxiliares para a fusão Além de ser mais complexo de implementar em comparação com outros algoritmos de ordenação como Insertion Sort ou Bubble Sort 3 Observe o estado inicial do vetor e o primeiro passo de sua ordenação a Qual o nome do método de ordenação usado e a que classe de comportamento assintótico ele pertence Insertion Sort On no melhor caso e On² no caso médio ou pior caso b Considerando apenas as comparações existe diferença entre o melhor e o pior caso Se sim como se caracterizam Melhor caso lista já ordenada Pior caso list ana ordem inversa c Termine a execução do algoritmo mostrando os passos restantes até a conclusão 23 31 11 13 27 16 19 11 23 31 13 27 16 19 11 13 23 31 27 16 19 11 13 23 27 31 16 19 11 13 16 23 27 31 19 11 13 16 19 23 27 31 4 Marque V para as alternativas verdadeiras e F para as falsas Faça a correção das alternativas falsas use o espaço abaixo da alternativa a F Os algoritmos de ordenação eficientes pertencem a classe de comportamento Olog n Correção Onlogn b V O problema de encontrar valores repetidos em um vetor pertence a classe de comportamento On c V O método mais adequado para ordenar uma lista encadeada é o Inserção d F O problema de pesquisar por um valor em um conjunto desordenado pertence a classe de comportamento O2N Correção On² e V O vetor a seguir constitui um maxHeap 40202518162324 f V Para um vetor de 500 elementos o primeiro salto utilizado pelo método ShellSort será de 364 g V O pior caso do método QuickSort ocorre quando sistematicamente o pivô é escolhido como sendo um dos extremos de um vetor desordenado Neste caso é da ordem de On2 comparações h O método Inserção é o mais lento para qualquer tamanho se os elementos estão em ordem descendente 5 Dado o vetor abaixo com as chaves inicialmente dispostas desta forma faça o que se pede a Mostre os passos para a construção do heap 6 Nó pai de 4 e 2 vai até os filhos para indexer dois filhos em cada 4 Nó pai de 7 e 9 2 Nó pai de 5 e 1 b Mostre os passos seguintes da ordenação HeapSort até a sua conclusão Percorre a árvore Verifica se os filhos de 6 são maiores que o pai e percebe que não Próximo passo Verifica os filhos de 4 Troca o maior deles por 4 troca 9 por 4 depois volta pro nó central 6 Passo 3 Desce os nós de novo e verifica 9 6 9 sobe até o nó central Passo 4 Troca o 6 com 7 o 7 passa a ser o pai de 6 e 4 Passo 5 Sobe até o Nó 2 e verifica seus filhos o 5 é maior que o 2 então sobre no lugar dele 6 Dado o vetor abaixo faça sua ordenação através do método ShellSort Dê os valores das variáveis h e i a cada passo use como referência o algoritmo do arquivo Ordenacaocs def shellSortarr n lenarr gap n 2 Inicializa o valor de gap h while gap 0 for i in rangegap n temp arri j i Ordena os subvetores com a inserção direta while j gap and arrj gap temp arrj arrj gap j gap arrj temp Reduz o gap h gap 2 return arr Vetor fornecido arr F A C U L D A D E C O T E M I G Ordena o vetor sortedarr shellSortarr Imprime o vetor ordenado printVetor ordenado sortedarr 7 Observe o seguinte método a Qual o nome do método Quicksort b Explique a sua estratégia Escolhe um elemento como pivô neste caso o pivô é o elemento no meio do array Particiona o array de forma que todos os elementos menores que o pivô fiquem à esquerda e todos os elementos maiores que o pivô fiquem à direita Recursivamente aplica a mesma lógica às sublistas à esquerda e à direita do pivô até que toda a lista esteja ordenada c Sublinhe as linhas do código onde ocorrem as trocas relevantes para a ordenação d Considere um programa que faça a seguinte chamada ao método ordena int vet 3 1 5 7 9 vetor aleatoriamente preenchido ordenavet 0 4 chamada inicial Mostre o que será impresso o console durante a execução do método até a conclusão da ordenação 3 1 5 7 9 esq0 dir4 x5 3 1 5 esq0 dir2 pivô1 3 5 esq1 dir2 pivô3 7 9 esq3 dir4 pivô7 e Quantas trocas foram realizadas ao todo Uma troca entre os elementos 3 e 1 8 Faça uma análise comparativa entre as seguintes estruturas de dados vetores ordenados listas encadeadas árvores binárias de pesquisa e tabela hash no que diz respeito a inserção remoção e pesquisa de chaves Fale sobre as vantagens e desvantagens de cada um e como ocorrem Vetores Ordenados têm inserção e remoção custosas On pois podem exigir o deslocamento de muitos elementos A pesquisa é eficiente Olog n devido à ordenação mas manter essa ordem é caro em termos de inserção e remoção Listas Encadeadas permitem inserção e remoção rápidas O1 para início ou fim mas a pesquisa é lenta On porque é necessário percorrer a lista Elas são simples de implementar mas não eficientes para pesquisa em listas grandes Árvores Binárias de Pesquisa BST oferecem operações de inserção remoção e pesquisa eficientes Olog n em média desde que a árvore esteja balanceada No entanto se a árvore ficar desbalanceada o desempenho pode se degradar para On Tabelas Hash são extremamente rápidas para inserção remoção e pesquisa O1 em média No entanto colisões podem ocorrer necessitando de técnicas de resolução o que pode complicar a implementação Em resumo vetores ordenados são ideais para pesquisas rápidas listas encadeadas são úteis para inserções e remoções rápidas BSTs são boas para operações balanceadas e tabelas hash são preferidas para velocidade extrema desde que as colisões sejam gerenciadas eficientemente A escolha da estrutura de dados depende das necessidades específicas de desempenho para as operações predominantes no aplicativo a b altura 4 c 8 3 4 2 7 d 4 8 3 2 7 2 e 8 3 2 7 4 2 a ENTROU NO NÓ M ENTROU NO NÓ R ENTROU NO NÓ V ENTROU NO NÓ Z NULO DIREITA FEITA Z NULO ESQUERDA FEITA Z DIREITA FEITA V NULO ESQUERDA FEITA V DIREITA FEITA R NULO ESQUERDA FEITA R DIREITA FEITA M ENTROU NO NÓ G ENTROU NO NÓ K ENTROU NO NÓ O ENTROU NO NÓ U NULO DIREITA FEITA U NULO ESQUERDA FEITA U DIREITA FEITA O ENTROU NO NÓ P NULO DIREITA FEITA P NULO ESQUERDA FEITA P ESQUERDA FEITA O DIREITA FEITA K ENTROU NO NÓ N NULO DIREITA FEITA N NULO ESQUERDA FEITA N ESQUERDA FEITA K DIREITA FEITA G ENTROU NO NÓ B ENTROU NO NÓ D NULO DIREITA FEITA D ENTROU NO NÓ E NULO DIREITA FEITA E NULO ESQUERDA FEITA E ESQUERDA FEITA D DIREITA FEITA B NULO ESQUERDA FEITA B ESQUERDA FEITA G ESQUERDA FEITA M b Remoção de R M G S B K V D N O Z E P U Remoção de M N G S B K V D P O Z E U Remoção de D N G S B K V E P O Z U Remoção de V N G S B K Z E P O U Remoção de B N G S E K Z P O U a 211 2048 nós b h1 nós c 2h1 1 nós d 2h1 1 4657 2h1 4658 h1 log24658 h 1119 numero mais proximo h12 e A B C D f A B C A B C A B C B C A C A B a 50 13 11 25 13 12 67 13 2 68 13 3 19 13 6 1 13 1 28 13 2 63 13 11 45 13 6 80 13 2 b Índice Chave 0 63 1 1 2 67 3 68 4 28 5 80 6 19 7 45 8 9 10 11 50 12 25 c Índice Chave 0 1 1 2 672880 3 68 4 5 6 1945 7 8 9 10 11 12 a 7 b 3 EAC Valores E 4 A 0 C 2 Soma 40264 0 2 64026 Posição 6766 7 6676 ADF Valores A 0 D 3 F 5 Soma 03580 3 5 80358 Posição 8718 7 1871 DDA Valores D 3 D 3 A 0 Soma 33063 3 0 63306 Posição 6766 7 6676 Colisão com EAC já na posição 6 FF Valores F 5 F 5 Soma 55105 5 105510 Posição 107310 7 31073 DB Valores D 3 B 1 Soma 3143 1 4314 Posição 4744 7 4474 EAA Valores E 4 A 0 A 0 Soma 40044 0 0 44004 Posição 4744 7 4474 Colisão com DB já na posição 4 FAB Valores F 5 A 0 B 1 Soma 50165 0 1 65016 Posição 6766 7 6676 Colisão com EAC e DDA já na posição 6 c Qualquer uma das chaves EAC DDA FAB Serão necessários 3 testes d Valores B 1 B 1 A 0 Soma 11021 1 0 21102 Posição 2722 7 2272 A posição 2 contém a chave DDA Como não há outras chaves nesta posição apenas 1 teste será necessário class NoArvore int chave NoArvore esq dir public NoArvoreint item chave item esq dir null class Arvore NoArvore raiz Arvore raiz null Método principal que será chamado para iniciar a travessia public void visitaNosDecrescente visitaNosDecrescenteraiz Método auxiliar para visitar os nós em ordem decrescente private void visitaNosDecrescenteNoArvore no if no null Visitar o subárvore direita visitaNosDecrescentenodir Calcular e imprimir o valor da chave seguido do grau do nó int grau calculaGrauno SystemoutprintlnChave nochave Grau grau Visitar o subárvore esquerda visitaNosDecrescentenoesq Método para calcular o grau do nó private int calculaGrauNoArvore no int grau 0 if noesq null grau if nodir null grau return grau Métodos auxiliares para adicionar nós à árvore public void adicionarint chave raiz adicionarRecursivoraiz chave private NoArvore adicionarRecursivoNoArvore no int chave if no null return new NoArvorechave if chave nochave noesq adicionarRecursivonoesq chave else if chave nochave nodir adicionarRecursivonodir chave return no Exemplo de uso public class Main public static void mainString args Arvore arvore new Arvore arvoreadicionar50 arvoreadicionar30 arvoreadicionar70 arvoreadicionar20 arvoreadicionar40 arvoreadicionar60 arvoreadicionar80 arvorevisitaNosDecrescente 15 Suponha que se queira pesquisar a chave 287 em uma árvore binária de pesquisa com chaves entre 1 e 1000 Durante uma pesquisa como essa uma sequência de chaves é examinada Cada sequência abaixo é uma suposta sequência de chaves examinadas em uma busca da chave 287 I 7 342 199 201 310 258 287 II 110 132 133 156 289 288 287 III 252 266 271 294 295 289 287 IV 715 112 530 249 406 234 287 É válido apenas o que se apresenta em a I e II CORRETA b II e IV c I d III e III e IV 16 ENADE 2005 Julgue os itens a seguir acerca de algoritmos para ordenação I O algoritmo de ordenação por inserção tem complexidade On log n II Um algoritmo de ordenação é dito estável caso ele não altere a posição relativa de elementos de mesmo valor III No algoritmo quicksort a escolha do elemento pivô influencia o desempenho do algoritmo IV O bubblesort e o algoritmo de ordenação por inserção fazem em média o mesmo número de comparações Estão certos apenas os itens a I e II b I e III c II e IV d I III e IV e II III e IV CORRETA 17 As filas de prioridades heaps são estruturas de dados importantes no projeto de algoritmos Em especial heaps podem ser utilizados na recuperação de informação em grandes bases de dados constituídos por textos Basicamente para se exibir o resultado de uma consulta os documentos recuperados são ordenados de acordo com a relevância presumida para o usuário Uma consulta pode recuperar milhões de documentos que certamente não serão todos examinados Na verdade o usuário examina os primeiros m documentos dos n recuperados em que m é da ordem de algumas dezena Considerando as características dos heaps e sua aplicação no problema descrito acima avalie as seguintes afirmações I Uma vez que o heap é implementado como uma árvore binária de pesquisa essencialmente completa o custo computacional para sua construção é On log n II A implementação de heaps utilizandose vetores é eficiente em tempo de execução e em espaço de armazenamento pois o pai de um elemento armazenado na posição i se encontra armazenado na posição 2i1 III O custo computacional para se recuperar de forma ordenada os m documentos mais relevantes armazenados em um heap de tamanho n é Om log n IV Determinar o documento com maior valor de relevância armazenado em um heap tem custo computacional O1 Está correto apenas o que se afirma em a I e II b II e III c III e IV CORRETA d I II e IV e I III e IV 18 ENADE 2005 Considere o algoritmo que implementa o seguinte processo uma coleção desordenada de elementos é dividida em duas metades e cada metade é utilizada como argumento para a reaplicação recursiva do procedimento Os resultados das duas reaplicações são então combinados pela intercalação dos elementos de ambas resultando em uma coleção ordenada Qual é a complexidade desse algoritmo a On2 b On2n c O2n d Olog n log n e On log n CORRETA