Lista de exercícios – Classificação e Pesquisa

Lista de exercícios – Classificação e Pesquisa

1- Faça uma tabela de comparação entre todos os métodos de ordenação estudados em aula com relação a estabilidade, ordem de complexidade levando em consideração comparações e movimentações.

2- Seja a sequencia de caracteres “ E S T U P R O ”. Calcule o número de comparações para que

a chave “S” seja localizada (caso necessário, ordene a sequência), utilizando-se:

a) Pesquisa sequencial;

b) Pesquisa Binária.

3- Seja a sequencia de caracteres “ E S T U P R O ”. Calcule o número de comparações para quea chave “B” seja localizada ( ou não) (caso necessário, ordene a sequência), utilizando-se:

a) Pesquisa sequencial;

b) Pesquisa Binária.

4- Realize as etapas necessárias para a ordenação ( crescente), da sequencia de caracteres da palavra “ E S T U P R O “ para cada um dos métodos pedidos abaixo:

a) Seleção e Troca;

b) Inserção ;

c) ShelSort;

d) QuickSort.

5- Quais das seguintes figuras representam árvores binárias de altura balanceada ou do tipo AVL ( justifique sua resposta):

6- Deseja-se efetuar uma busca para localizar uma certa chave fixa x, em uma tabela contendo n elementos. A busca considerada pode ser a linear ou binária. No primeiro caso pode-se considerar que a tabela esteja ordenada ou não. No segundo caso a tabela está, de forma óbvia, ordenada. Verifique a validade ( ou não) das afirmações abaixo, justificando sua resposta:

I- Uma busca binária sempre localiza x, efetuando menos comparações que a busca linear.

II- Uma busca linear ordenada sempre localiza x, efetuando menos comparações que a não ordenada.

III- Uma busca linear não ordenada sempre localiza x, com menos comparações que a ordenada.

IV- Uma busca linear ordenada nunca requer mais do que n/2 comparações para localizar x.

7- Qual a sequência de caracteres obtida percorrendo a árvore binária abaixo, nas seguintes formas:

a) Em pré-ordem;

b) Em pós-ordem;

c) Em-ordem;

d) Em-nível

8- Podemos utilizar uma lista estática (vetor) para armazenar os elementos de uma árvore binária. Represente desta forma a árvore binária da questão anterior.

9- - Dada a estrutura abaixo, escreva as seguintes funções em “C”:

#define MaxLista 100

struct Estrutura_Lista{

int Dados[MaxLista];

int ultimo; };

a)Uma função que preencha uma Lista baseada nessa estrutura com valores “aleatórios” entre 1 a 10000;

b)Uma função utilizando