Prova 2 do Primeiro Semestre de 2013

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 2 – Valor 25 Pontos
Nome:________________________________________________
1 Com a inserção dos valores listados a seguir monte: (6 pontos)
a) uma árvore AVL
b) uma árvore Red-Black
2 Faça o rastreio da função particao tendo como entrada o vetor apresentado e os limites 
esquerdo igual a 0 e direito igual a 7. (4 pontos)
Vetor:
11 31 16 17 12 14 18 15
0 1 2 3 4 5 6 7
int particao(int v[], int esq, int dir)
{
 int i, j, pivo, aux;
 pivo = v[dir];
 i = esq-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;
}
3 São apresentadas a seguir 4 seqüências de ordenação. Analise-as e determine qual algoritmo 
foi usado em cada uma. Os algoritmos possíveis são: seleção, inserção, bolha e mergesort. (5 
pontos)
5 1 6 2 3 4
1 5 6 2 3 4
1 5 6 2 3 4
1 2 5 6 3 4
1 2 3 5 6 4
1 2 3 4 5 6
5 1 6 2 3 4
1 5 6 2 3 4
1 5 6 2 3 4
1 5 6 2 3 4
1 5 6 2 3 4
1 2 3 4 5 6
5 1 6 2 3 4
1 5 6 2 3 4
1 2 6 5 3 4
1 2 3 5 6 4
1 2 3 4 6 5
1 2 3 4 5 6
5 1 6 2 3 4
1 5 2 3 4 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
R:_____________ R:_____________ R:_____________ R:_____________
4 Mostre a sequência de ordenação para o vetor apresentado na questão 1 usando os métodos 
dos algoritmos: (6 pontos)
a) Bolha
b) Mergesort
c) Seleção
5 O gráfico abaixo apresenta o desempenho (tempo de execução) para três algoritmos para 
ordenar vetores aleatórios de tamanho variando de 1000 a 10000 elementos. Identifique-os. (4 
pontos)
a) bolha seleção inserção
b) seleção bolha inserção
c) inserção bolha seleção
d) seleção inserção bolha
e) bolha inserção seleção
1000 2000 3000 4000 5000 6000 7000 8000 900010000
Desempenho dos algoritmos de ordenação
tamanho do v etor
te
m
po