Prova 1 - 2013-2

Prévia do material em texto

Algoritmos e Estruturas de Dados II
Prova 1 (35 + 3 pontos)
Questão 1 (7 pontos): Implemente uma função recursiva para determinar o índice do maior 
elemento de um dado vetor de inteiros. 
Formulário:
Método master:
T(n) = aT(n/b) + f(n), a≥1, b>1
Se f(n) = O(nlgb a - ε) para alguma constante ε então T(n) = Θ(nlgb a).
Se f(n) = Θ(nlgb a) então T(n) = Θ(nlgb a lg n)
Se f(n) = Ω(nlgb a + ε) para alguma constante ε e af(n/b) ≤ cf(n) para alguma constante c<1 e para n 
suficientemente grande, então T(n) =Θ(f(n)).
Questão 2 (7 pontos): Considere o seguinte algoritmo (busca binária) que procura um inteiro em 
um vetor de inteiros ordenado.
bool pbin_aux(int a[], int ini, int fim, int x) {
 if (ini == fim) {
 return (a[ini]==x);
 } else {
 int med = (ini + fim)/2;
 if (a[med]>=x) {
 return (pbin_aux(a,ini,med,x));
 } else {
 return (pbin_aux(a,med+1,fim,x));
 } 
 }
}
bool pbin(int a[], int n, int x) {
 return(pbin_aux(a,0,n-1,x));
}
a) Calcule a complexidade da busca binária.
b) Tendo que fazer uma busca em um vetor não ordenado. Vale a pena ordenar o vetor com algum 
dos algoritmos vistos em aula para depois aplicar busca binária?
c) Tendo que fazer Θ(n) buscas em um vetor não ordenado. Vale a pena ordenar o vetor com algum 
dos algoritmos vistos em aula para depois aplicar busca binária Θ(n) vezes?
Questão 3 (8 pontos): Considere a seguinte algoritmo de ordenação:
void swap (elem &x, elem &y) {
elem aux;
aux = x;
x = y;
y = aux;
}
void iSort(elem a[], int n ) {
int j,pos;
for (int i= 1;i<n;i++) {
elem x;
j=0;
while (a[j].chave < a[i].chave) {
j++;
}
pos=j;
x = a[j];
j++; 
while (j<=i) {
swap(a[j],x); 
j++;
}
a[pos] = x;
}
}
a) O que pode ser dito acerca do estado do vetor após a iteração p do ciclo for?
b) Qual é a complexidade do algoritmo?
c) Como se compara essa complexidade com a do Insertion Sort e a do Merge Sort? 
Questão 4 (8 pontos): O tempo de execução de um algoritmo A está dado pela fórmula de 
recorrência T(n) = 7T(n/2) + n2. O tempo de execução de um algoritmo A' está dado pela fórmula 
de recorrência T'(n) = aT'(n/4) + n2. Qual é o maior valor inteiro de a para o qual o algoritmo A' 
tem menor complexidade que o algoritmo A? Dica: Use o método master para calcular a 
complexidade dos dois algoritmos.
Questão 5 (8 pontos): Implemente o TAD palavra para manipular palavras de até 15 caracteres. Um 
dos campos privados deve ser um vetor de char de 15 posições. Forneça um construtor que crie uma 
palavra nula (de tamanho 0), um destrutor que não faça nada, um observador para conhecer o 
caractere em qualquer posição válida da palavra, outro observador para conhecer o tamanho da 
palavra e um operador para colocar um dado caractere no final da palavra (o tamanho da palavra 
deve aumentar em uma unidade). Depois, implemente um procedimento fora da classe que receba 
uma palavra por parâmetro e a imprima na tela.
	Algoritmos e Estruturas de Dados II
	Prova 1 (35 + 3 pontos)