Estruturas de Dados

1.

Usando uma pseudo-linguagem em português, descreva detalhadamente o algoritmo de busca linear.

2.

Idem para busca binária.

3.

Implemente em C uma função que ordene por inserção os elementos de um setor de N posições a ser fornecido pela função main( ).

4.

Implemente em C um programa que ordene por Bubble sort os elementos de um vetor usando uma função de ordenação fora do programa principal.

5.

Determine o número máximo de passos (situação de pior caso) necessários para ordenar N elementos de um vetor quando são usados os algoritmos de ordenação por inserção e tipo bolha e compare os resultados. Existe alguma situação em que um se torna mais vantajoso que o outro.

6.

Descreva em detalhes e de forma textual o algoritmo de ordenação tipo HEAP.

7.

Determine a complexidade dos algoritmos de ordenação por inserção, de bolha e de heap, comparando e discutindo os resultados.

8.

Implemente em C a função de divisão do quicksort e teste-a com a função quicksort ( ) apresentada em sala de aula.

9.

Na sua forma mais simples o Quicksort exige um espaço adicional da ordem de O(n) para ir compilando vetor com os elementos reposicionados. Procure uma forma de implementar o quicksort que não exija espaço de memória extra para guardar todos os elementos do vetor.

10.

determine a complexidade temporal de quicksort quando:

- os dados do vetor estão desordenados;

- os dados do vetor estão ordenados.

11.

compare quicksort e heap sort, mostrando as vantagens de um sobre o outro.

12.

Explique como funciona o algoritmo radix sort e compare-o com o quicksort.

13.

Considerando a estrutura em C chamada Node apresentada na seção 2.6.4, mostre como seriam as estruturas de listas circulares com encadeamento simples e duplo.

14.

Considerando a estrutura em C chamada Node apresentada na seção 2.6.4, explique como se faz para inserir um novo dado em listas simplesmente e duplamente encadeadas não ordenadas.

15.

Repita o exercício anterior para listas ordenadas.

16.

Considerando a estrutura em C chamada Node apresentada na seção 2.6.4, mostre como deve ser feita a remoção de um dado elemento de uma lista simplesmente encadeada.

17.

Repita o exercício anterior para listas duplamente encadeadas.

18.

Crie uma árvore binária arbitrária, não-balanceada, contendo pelo menos 14 nós, e determine a seqüência de nós da mesma para cada uma das três possíveis estratégias de varredura.

19.

(enunciado corrigido) Proponha uma função hash para organizar uma certa quantidade M de elementos numéricos inteiros não repetidos (com valores de 0 a N-1, N>M). Podem haver colisões em sua função? De que maneira(s) tais colisões podem ser minimizadas?

20.

Determine a complexidade da busca de elementos, usando a função de hash proposta no exercício anterior.

Usando uma pseudo-linguagem em português, descreva detalhadamente o algoritmo de busca linear.

Idem para busca binária.

Implemente em C uma função que ordene por inserção os elementos de um setor de N posições a ser fornecido pela função main( ).

Implemente em C um programa que ordene por Bubble sort os elementos de um vetor usando uma função de ordenação fora do programa principal.

Determine o número máximo de passos (situação de pior caso) necessários para ordenar N elementos de um vetor quando são usados os algoritmos de ordenação por inserção e tipo bolha e compare os resultados. Existe alguma situação em que um se torna mais vantajoso que o outro.

Descreva em detalhes e de forma textual o algoritmo de ordenação tipo HEAP.

Determine a complexidade dos algoritmos de ordenação por inserção, de bolha e de heap, comparando e discutindo os resultados.

Implemente em C a função de divisão do quicksort e teste-a com a função quicksort ( ) apresentada em sala de aula.

Na sua forma mais simples o Quicksort exige um espaço adicional da ordem de O(n) para ir compilando vetor com os elementos reposicionados. Procure uma forma de implementar o quicksort que não exija espaço de memória extra para guardar todos os elementos do vetor.

determine a complexidade temporal de quicksort quando:

- os dados do vetor estão desordenados;

- os dados do vetor estão ordenados.

compare quicksort e heap sort, mostrando as vantagens de um sobre o outro.

Explique como funciona o algoritmo radix sort e compare-o com o quicksort.

Considerando a estrutura em C chamada Node apresentada na seção 2.6.4, mostre como seriam as estruturas de listas circulares com encadeamento simples e duplo.

Considerando a estrutura em C chamada Node apresentada na seção 2.6.4, explique como se faz para inserir um novo dado em listas simplesmente e duplamente encadeadas não ordenadas.

Repita o exercício anterior para listas ordenadas.

Considerando a estrutura em C chamada Node apresentada na seção 2.6.4, mostre como deve ser feita a remoção de um dado elemento de uma lista simplesmente encadeada.

Repita o exercício anterior para listas duplamente encadeadas.

Crie uma árvore binária arbitrária, não-balanceada, contendo pelo menos 14 nós, e determine a seqüência de nós da mesma para cada uma das três possíveis estratégias de varredura.

(enunciado corrigido) Proponha uma função hash para organizar uma certa quantidade M de elementos numéricos inteiros não repetidos (com valores de 0 a N-1, N>M). Podem haver colisões em sua função? De que maneira(s) tais colisões podem ser minimizadas?

Determine a complexidade da busca de elementos, usando a função de hash proposta no exercício anterior.