AV2 ESTRUTURA DE DADOS

Prévia do material em texto

AV2 ESTRUTURA DE DADOS 
1.É correto afirmar que: 
A) O buble sort é um algoritmo recursivo. 
B) O Insert sort é um método de ordenação instável. 
C)O Selection Sort tem complexidade computacional O(n log n) 
D)O buble sort, o insert sort e o selection sort tem a mesma complexidade computacional, 
porém, isto não quer dizer que todos executem ao mesmo tempo para a mesma instância. 
E) O buble sort é um algoritmo de ordenação instável. 
2.Sobre o método da bolha é correto afirmar que: 
A) O algoritmo executa sempre no mesmo tempo para instâncias de mesmo tamanho n. 
B) O tempo de execução pode ser linear em relação ao tamanho da entrada se a instância 
apresentada estiver ordenada em ordem reversa a desejada. 
C)O tempo de execução é definido pela complexidade computacional sempre, 
independentemente da instância apresentada. 
D)A complexidade computacional deste algoritmo é O (n log n). 
E)O tempo de execução pode ser linear em relação ao tamanho da entrada se a instância 
apresentada já estiver ordenada. 
3.Avalie as afirmativas abaixo: 
1 - O merge sort executa em O (n log n). 
2 - O bucket sort executa em O(n). 
3 - Algoritmos que executam em uma complexidade abaixo de O (n log n) ordenam a 
sequência sem comparar os elementos desta sequência. 
A) Somente a 1 está correta. 
B) Somente a 1 e a 2 estão corretas. 
C)Somente a 2 e a 3 estão corretas. 
D)Somente a 3 está correta. 
E) Todas estão corretas. 
Resposta correta: E 
4.Comparando o Merge Sort com o Método da bolha podemos afirmar que: 
A)O merge sort sempre executará mais rápido que o buble sort uma vez que sua complexidade 
é O (n log n) e a do buble sort O(n2). 
B) Ambos têm complexidade comparável, assim, existem não é possível afirmar qual irá 
executar em melhor tempo. 
C)O merge sort tem complexidade computacional inferior ao buble sort, porém o 
merge sort sempre executa em um tempo proporcional a n log n, enquanto o buble sort, pode 
executar em tempo linear em algumas instâncias (melhores casos). 
D)O buble sort sempre irá executar mais rápido que o merge sort por ter complexidade 
computacional inferior ao merge sort. 
E) O merge sort, por ser instável, sempre executará em tempo superior ao buble sort. 
Resposta correta: C 
5.Todos os algoritmos de ordenação interna devem ter complexidade de espaço de: 
A) O(n2) 
B) O (n log n) 
C)O(n) 
D)O(n3) 
E) O (1) 
Resposta correta: C