Tipos e Estruturas de Dados Lista de Exercícios - 1 1) Conceitue: a) algoritmo b) tipo de dados c) tipo abstrato de dados 2) Suponha dois algoritmos A e B com funcoes de complexidade de tempo dadas por a(n) = n^2 - n + 549 e b(n) = 49n + 49 respectivamente. Determine quais valores de n no conjunto dos numeros naturais para os quais A leva menos tempo para executar que B. 3) Dois programas A e B foram analisados e os respectivos limites de pior caso foram determinados como sendo 150n*log(n) e n^2. Se possivel, responda `as seguintes perguntas: a) Qual dos programas tem melhor garantia de desempenho para valores grandes de n (n>10000)? b) Qual dos programas tem melhor garantia de desempenho para valores pequenos de n (n<100)? c) Qual programa executara' mais rapido na media para n=1000? d) E' possivel ao programa B executar mais rapido que A para todas as entradas possiveis? 4) Liste as principais vantagens e desvantagens de cada um dos métodos vistos até o momento: inserção, seleção, bolha, shellsort, quicksort, heapsort e mergesort. 5) Que algoritmo de ordenação você usaria para cada um dos seguintes casos: a: A ordenação original de elementos com chave idêntica precisa ser mantida. b: O tempo de execução não deve apresentar grandes variações para nenhum caso. c: A lista a ser ordenada já está sempre bem próxima da ordem final d: Os elementos a serem ordenados são muito grandes se comparados ao tamanho das chaves. e: A lista a ser ordenada não cabe na memória principal. 6) Ordene as letras da palavra Exemplar utilizando cada um dos métodos estudados. Para fins de ordenação, letras maiúsculas e minúsculas devem ser consideradas equivalentes, isto é, ``E'' e ``e'' devem ser consideradas iguais durante comparações. Para verificar o correto andamento de cada algoritmo, escreva o conteúdo do vetor a cada passo intermediário, conforme as exigências abaixo. A cada caso, um exemplo com a sequência ``UMDOIS'' é mostrado. a: SELEÇÃO: Liste o vetor a cada elemento que atinja sua posição definitiva: UMDOIS Início DMUOIS D selecionado DIUOMS I selecionado DIMOUS M selecionado DIMOUS O selecionado DIMOSU S selecionado b: INSERÇÃO: Liste o vetor a cada elemento que é incluido na ordenação parcial até o momento. UMDOIS Início, ordem parcial contém apenas U MUDOIS Ordem parcial é MU DMUOIS Ordem é DMU DMOUIS DMOU DIMOUS DIMOU DIMOSU c: QUICKSORT: Use o elemento à esquerda da partição como pivot. Liste o vetor a cada nova partição (c/ dois ou mais elementos) completada. UMDOIS Início, pivot = U SMDOIU Partição SMDOI, pivot = S IMDOSU Partição IMDO, pivot = I DMIOSU Partição MIO, pivot = M DIMOSU Partição MO, pivot = M DIMOSU d: QUICKSORT: Use o elemento no centro da partição como pivot ((esq+dir)/2). Liste o vetor a cada nova partição (c/ dois ou mais elementos) completada. UMDOIS Início, pivot na pos.3 ((1+7)/2) = D DMUOIS Partição MUOIS, pivot = O DMIOUS Partição MI, pivot = M DIMOUS Partição US, pivot = U DIMOSU e: HEAPSORT: Liste o vetor a cada elemento que é inserido no heap na fase de construção e a cada elemento que é removido, antes e depois do heap ser refeito. UMDOIS Início, head 4-6 OK UMSOID D adicionado ao heap UOSMID M adicionado UOSMID U adicionado, heap completo DOSMIU U removido e trocado com D SODMIU heap refeito IODMSU S removido, trocado com I OMDISU heap refeito IMDOSU O removido, trocado com I MIDOSU heap refeito DIMOSU O removido, trocado com D IDMOSU heap refeito DIMOSU I removido, trocado com I 7) O papel do for interno na função insercao é encontrar o ponto onde v[j] deve ser inserido em v[0..j-1]. Considere fazer isso com uma busca binária. Analise o resultado. 8) Escreva uma função que coloque em ordem lexicográfica um vetor de strings. Use o algoritmo de inserção. A ordem lexicográfica entre strings é análoga à ordem das palavras em um dicionário. Ela se baseia na ordenação dos caracteres estabelecida na tabela ISO8859-1, da mesma forma que a ordem das palavras em um dicionário se baseia na ordenação das letras no alfabeto. Para comparar duas strings s e t, procura-se a primeira posição, digamos k, em que as duas strings diferem. Se s[k] vem antes de t[k] na tabela ISO então s é lexicograficamente menor que t. 9) Existe um ordenador chamado count sort que construirá uma nova lista ordenada em um vetor, a partir de uma lista L existente, dado que L não possua elementos repetidos, ou seja, todas as chaves são diferentes. Para cada chave (l->dados[i].ch) o algoritmo percorre a lista e conta quantas chaves são menores que a referida chave. Se este valor é “c”, então a posição dessa chave no novo vetor é c+1. Escreva o algoritmo. 10) Considere o seguinte vetor: [25, 57, 48, 37, 12, 92, 86, 33]. Mostre passo a passo como se ordena este vetor com o ShellSort usando k = 5, 3, 1. Diz-se que o ShellSort se assemelha ao método da Inserção. Mostre em que situação essa semelhança é mais evidente e diga qual a vantagem do ShellSort em relação ao método de Inserção 11) Implemente os algoritmos de ordenacao por selecao, insercao, quicksort e shellsort. Utilize as rotinas disponiveis no link "Exemplo pratico de busca sequencial" para contar o tempo de execucao. COmo entrada, voce pode criar um vetor de inteiros aleatorio de dimensao bem grande.