exec04-algoritmos-busca

Prévia do material em texto

ANÁLISE DE ALGORITMOS 
Bacharelado em Ciências da Computação 
 
 
 
Lista de Exercícios 04 
Algoritmos de Busca 
 
 
1. Explique por que a busca binária: 
a. É mais eficiente do que a busca sequencial. 
b. Só pode ser efetuada em um array. 
 
 
2. Considere a lista linear sequencial de inteiros no vetor, a seguir. 
 
2 4 6 8 10 12 14 16 
 
a. Considerando o método da busca binária: 
1. Quantas comparações (e com quais chaves) são necessárias na busca pelo valor 15? 
2. Idem para o inteiro 6. 
b. Considerando a Busca Sequencial: 
1. Quantas comparações (e com quais chaves) são necessárias pelo valor 15? 
2. Idem para o inteiro 6. 
c. Generalize o número máximo de comparações na Busca Binária e na Busca Sequencial, 
considerando o tamanho do vetor igual a n. 
 
3. Qual é o pior tempo para inserir n elementos em uma tabela hashing inicialmente vazia, 
com colisões sendo resolvidas por listas encadeadas? Qual seria o melhor caso? 
 
4. Considerando que as chaves inseridas em um Hashing não provocaram colisão, 
independente do algoritmo, podemos dizer que a pesquisa por uma chave na tabela será 
de ordem de complexidade constante, ou seja, T(n) = 1? Podemos dizer que este algoritmo 
é ótimo? Justifique. 
 
5. No processo de pesquisa binária em um vetor ordenado, os números máximos de 
comparações necessárias para se determinar se um elemento faz parte de vetores com 
tamanhos 50, 1.000 e 300 são, respectivamente 
a. 5, 100 e 30 
b. 6, 10 e 9 
ANÁLISE DE ALGORITMOS 
Bacharelado em Ciências da Computação 
 
 
c. 8, 31 e 18 
d. 10, 100 e 30 
e. 25, 500 e 150 
 
 
6. Um programador propôs um algoritmo não-recursivo para o percurso em pré-ordem de 
uma árvore binária com as seguintes características. 
• Cada nó da árvore binária é representado por um registro com três campos: chave, que 
armazena seu identificador; esq e dir, ponteiros para os filhos esquerdo e direito, 
respectivamente. 
• O algoritmo deve ser invocado inicialmente tomando o ponteiro para o nó raiz da árvore 
binária como argumento. 
• O algoritmo utiliza push() e pop() como funções auxiliares de empilhamento e 
desempilhamento de ponteiros para nós de árvore binária, respectivamente. 
A seguir, está apresentado o algoritmo proposto, em que λ representa o ponteiro nulo. 
 
 
Com base nessas informações e supondo que a raiz de uma árvore binária com n nós seja passada 
ao procedimento pré-ordem(), julgue os itens seguintes. 
I. O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso. 
II. O algoritmo só funcionará corretamente se o procedimento pop() for projetado de forma a 
retornar λ caso a pilha esteja vazia. 
III. Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser 
implementadas com custo constante. 
IV. A complexidade do pior caso para o procedimento pré-ordem() é O(n). 
ANÁLISE DE ALGORITMOS 
Bacharelado em Ciências da Computação 
 
 
Indique a opção correta. 
a. Apenas um item está certo. 
b. Apenas os itens I e IV estão certos. 
c. Apenas os itens I, II e III estão certos. 
d. Apenas os itens II, III e IV estão certos. 
e. Todos os itens estão certos. 
 
7. Em relação à pesquisa sequencial e binária, assinale a alternativa correta. 
a. A pesquisa binária percorre no pior caso lgn elementos 
b. A pesquisa binária pode ser feita sobre qualquer distribuição dos elementos 
c. A pesquisa sequencial exige que os elementos estejam completamente ordenados 
d. A pesquisa sequencial percorre todos os elementos para encontrar a chave 
 
 
8. Considere as seguintes afirmativas sobre o algoritmo de pesquisa binária: 
I. a entrada deve estar ordenada 
II. uma pesquisa com sucesso é feita em tempo logarítmico na média 
III. uma pesquisa sem sucesso é feita em tempo logarítmico na média 
IV. o pior caso de qualquer busca é logarítmico 
As afirmativas corretas são: 
a. Somente I e II 
b. Somente I, II e III 
c. Somente II e III 
d. Somente III e IV 
e. Todas as afirmativas estão corretas