Praticas de Programação

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 FACULDADE COTEMIG ANÁLISE E DESENVOLVIMENTO DE SISTEMAS SISTEMAS DE INFORMAÇÃO Disciplina ALGORITMOS E ESTRUTURAS DE DADOS Professor Virgílio Borges de Oliveira Trabalho Prático Pilhas Estáticas Escreva um programa que simule o funcionamento de uma calculadora científica com memória de pilha Qualquer número inteiro digitado pelo usuário deverá ser empilhado Se o usuário digitar um dos quatro operadores matemáticos o programa deverá realizar a operação desejada desempilhando os dois últimos valores O resultado da operação deverá ser empilhado e impresso na tela Observação Exibir mensagem de erro em caso de pilha cheiavazia O tamanho máximo da pilha deverá ser de 100 valores Exemplo de entrada de dados 4enter estado da pilha 4 6enter estado da pilha 6 4 2enter estado da pilha 2 6 4 enter estado da pilha 8 4 enter estado da pilha 32 Teste 5 2 4 60 4 8 3 5 8 5 RESPOSTA 18 FACULDADE COTEMIG ANÁLISE E DESENVOLVIMENTO DE SISTEMAS SISTEMAS DE INFORMAÇÃO Disciplina ALGORITMOS E ESTRUTURAS DE DADOS Professor Virgílio Borges de Oliveira Trabalho Prático Lista Encadeada Crie o projeto Pratica3 e importe os arquivos Lista e TestaLista localizados na pasta da disciplina em Java e C Execute o programa TestaLista e entenda seu funcionamento Faça as seguintes modificações 1 Crie um menu para o programa com as opções 1 Inserir 2 Pesquisar 3 Imprimir Lista 4 Sair 2 Na opção 1 altere a rotina para que não permita a inserção de chaves duplicadas Antes de inserir verifique se a chave já se encontra na lista e caso positivo informe o erro ao usuário 3 Na classe NoLista adicione o atributo String nome e faça as devidas adaptações na classe Lista Na opção 1 além de informar uma chave o usuário deverá informar também um nome 4 Na pesquisa se a chave procurada for encontrada o programa deverá imprimir o nome correspondente Dê ao usuário a opção de remover o nó da lista FACULDADE COTEMIG ANÁLISE E DESENVOLVIMENTO DE SISTEMAS SISTEMAS DE INFORMAÇÃO ALGORITMOS E ESTRUTURAS DE DADOS Professor Virgílio Borges de Oliveira Trabalho Prático MaxMin 1 Crie o projeto Pratica4 e importe a classe MaxMin disponível junto a este enunciado Faça alterações nos três métodos inserindo contadores para contabilizar as comparações 2 Crie uma nova classe denominada Pratica4 contendo o método main 3 Você deverá chamar cada método da classe MaxMin três vezes com vetores de 1000 elementos inteiros preenchidos respectivamente em ordem crescente decrescente e aleatória Apresente no console os valores dos contadores para cada execução serão 9 execuções no total FACULDADE COTEMIG ANÁLISE E DESENVOLVIMENTO DE SISTEMAS BACHARELADO EM SISTEMAS DE INFORMAÇÃO Disciplina ALGORITMOS E ESTRUTURAS DE DADOS Professor Virgílio Borges de Oliveira Trabalho Prático Filas Estáticas O restaurante Dona Tita possui um sistema de atendimento que funciona assim existem três filas consecutivas pelas quais o cliente passa A primeira é a fila na qual o cliente faz seu pedido saindo desta fila ele entra em uma segunda fila na qual faz o pagamento de seu pedido saindo desta segunda ele entra em uma terceira fila na qual lhe é entregue a sua encomenda Escreva um programa em linguagem JavaC que simule o funcionamento deste sistema Deverá ser exibido um menu com as seguintes opções 1 Inserção de cliente na fila de pedidos 2 Remoção de cliente da fila de pedidos 3 Remoção de cliente da fila de pagamentos 4 Remoção de cliente da fila de encomendas 5 Sair Cada cliente novo que entra na fila de pedidos recebe um código que vai aumentando sequencialmente Sempre que um cliente entrar em uma fila deverá ser impressa uma mensagem como no seguinte exemplo Cliente 9999 entrou na fila de pedidos Sempre que um cliente for removido de um fila deverá ser impressa uma mensagem como no seguinte exemplo Cliente 9999 foi removido da fila de pagamentos Prática 5 Métodos de Ordenação Análise e Desenvolvimento de Sistemas Bacharelado em Sistemas de Informação Disciplina Algoritmos e Estruturas de Dados Período 2º Professora Virgílio Borges de Oliveira OBJETIVO Desenvolver um programa que forneça ao usuário animações gráficas e estatísticas dos principais métodos de ordenação em memória primária INSTRUÇÕES I Copie o projeto fornecido junto ao enunciado II Observe atentamente a distribuição das classes dentro do projeto III Execute o programa observando o funcionamento dos itens do menu IV Coloque seus dados pessoais no menu Sobre TAREFAS PARTE I Menu Animações 1 Adicionar um novo item de menu para cada método de ordenação estudado Bolha já incluído Seleção Inserção Shellsort Heapsort Quicksort Mergesort Cada item deverá acionar o respectivo método mostrado a animação durante a execução 2 Permitir que o usuário escolha o estado inicial do vetor preenchimento em ordem crescente ordem decrescente ou valores aleatórios PARTE II Menu Estatísticas 1 Adicionar um novo item de menu para cada método de ordenação estudado Bolha já incluído Seleção Inserção Shellsort Heapsort Quicksort Mergesort 2 Permitir que o usuário escolha o tamanho e o estado inicial de preenchimento do vetor a O tamanho do vetor 10000 50000 100000 e 500000 b Estado inicial do vetor ordem crescente ordem decrescente ou valores aleatórios 3 O programa deverá executar o método com as configurações escolhidas exibindo ao final as seguintes estatísticas obtidas durante a execução a Número de trocas b Número de comparações testes c Tempo decorrido em segundos formatado com 4 casas decimais APRESENTAÇÃO E ENTREGA O trabalho é individual Durante a avaliação o professor poderá fazer perguntas sobre os códigos apresentados A nota será penalizada caso a explicação não seja satisfatória ou deixe dúvidas quanto a autoria Todos os códigos críticos deverão conter comentários explicativos que serão avaliados Trabalhos entregues após a data de entrega serão desconsiderados Copias totais ou parciais serão penalizadas com nota zero