3º proa

Prévia do material em texto

Centro Universitário do Leste de Minas Gerais
Curso de Computação – Sistemas de Informação
Algoritmos e Estruturas de Dados III
Prova 3 – 30/11/2009 – Valor: 25 pontos
Nome: _______________________________________________________
1	Usando as propriedades básicas da notação O, simplifique as funções abaixo. (6 pontos).
a) 
b)
c)
2	Faça o rastreio do algoritmo da partição listado para o vetor mostrado abaixo. (7 pontos)
int particao(int v[], int esq, int dir) {
	int i, j, pivo, aux;
	pivo = v[dir];
	i = -1; j = dir;
	while(true) {
		while(v[++i]<pivo) ;
		while(j>esq && v[--j]>pivo) ;
		if(i >= j) break;
		aux = v[i]; v[i] = v[j]; v[j] = aux;
	}
	v[dir] = v[i];
	v[i] = pivo;
	return i;
}
Vetor:
	12
	54
	60
	47
	33
	10
	42
	102
	70
	56
	0
	1
	2
	3
	4
	5
	6
	7
	8
	9
3	A afirmação abaixo é verdadeira ou falsa? Justifique sua resposta. (4 pontos)
“Se dois algoritmos A e B têm custo O(n), então o desempenho dos dois é exatamente igual.”
4	Faça a análise do melhor caso das operações de movimentação do algoritmo de ordenação pelo método da inserção listado abaixo. Explique textualmente os passos que você utilizar. (4 pontos)
void insercao(int v[], int n) {
	int i, j, aux;
	
	for(i=1; i<n; i++) {
		aux = v[i];
		j = i;
		while(j>0 && v[j-1] > aux) {
			v[j]=v[j-1];
			j--;
		}
		v[j] = aux;		
	}
}
5	Um algoritmos O(1) sempre terá melhor desempenho que um algoritmo O(n3)? Justifique sua resposta. (4 pontos)
_49775776.unknown
_49824416.unknown
_49829568.unknown