COMPLEXIDADE DE ALGORITMOS - AV 3-2021 EAD

Prévia do material em texto

ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS 
 
 1. Ref.: 4053481 Pontos: 1,00 / 1,00
Correlacione os algoritmos internos de ordenação de listas com sua descrição: 
 
I. Bubble sort 
II. Ordenação por seleção 
III. Ordenação por inserção 
IV. Shell sort 
V. Quick sort 
 
( ) Escolhe-se um pivô e particiona-se a lista em duas sublistas - uma com os elementos
menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivô,
geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha
uma complexidade de pior caso de O(n2 ), no caso médio, é de O(n log n). 
 
( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do vetor.
Repetem-se essas duas operações com os n − 1 itens restantes; depois, com os n − 2
itens; até que reste apenas um elemento. 
 
( ) Método preferido dos jogadores de cartas. A cada momento, existem duas partes na
lista ¿ uma ordenada (destino) e outra não ordenada (fonte). Inicialmente, a lista destino tem
apenas o primeiro elemento, e a fonte, os demais elementos. Em cada passo, a partir de i=2,
seleciona-se o i-ésimo item da lista fonte. Deve-se colocá-lo no lugar apropriado na lista
destino, de acordo com o critério de ordenação. 
 
( ) É uma extensão de outro algoritmo de ordenação conhecido e permite trocas de elementos
distantes um do outro, não necessariamente adjacentes. Os itens separados de h posições são
rearranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é dita estar h-ordenada. 
 
( ) Varre-se a lista, trocando de posição os elementos adjacentes fora de ordem. Varre-se a
lista até que não haja mais trocas. Neste caso, a lista está ordenada. 
 
A sequência correta, de cima para baixo, é: 
I, III, II, IV, V 
V, IV, II, III, I 
I, II, III, IV, V 
 V, II, III, IV, I 
I, IV, V, III, II 
 2. Ref.: 4059327 Pontos: 1,00 / 1,00
Se f é uma função de complexidade para um algoritmo F, então, O(f) é considerada a
complexidade assintótica ou o comportamento assintótico do algoritmo F. Assinale
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053481.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059327.');
a alternativa que apresenta somente algoritmos com complexidade assintótica, quando f(n)
= O(n log n): 
Merge sort e bubble sort. 
 Quick sort e merge sort. 
Bubble sort. 
Insertion sort. 
Quick sort e insertion sort. 
 
ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL 
 
 3. Ref.: 3990635 Pontos: 1,00 / 1,00
Árvore de pesquisa é uma estrutura de dados eficiente para armazenar informação, sendo
particularmente adequada quando existe a necessidade de considerar todos ou alguma
combinação de registros. Assinale uma combinação correta desses registros. 
Utilização de algoritmos de ordenação eficientes. 
Não é necessário indexar os registros. 
As operações de inserir, retirar e pesquisar são definidas. 
Utilização de estruturas de dados como lista, pilha e fila. 
 Acesso direto e sequencial eficientes, facilidade de inserção e retirada de registro, boa
taxa de utilização de memória, utilização de memória primária e secundária. 
 4. Ref.: 3990634 Pontos: 1,00 / 1,00
Imagine que temos números de 1 a 100 em uma árvore de pesquisa binária (ABP). Agora
queremos procurar o número 50. Assinale a alternativa que apresenta a possível sequência de
elementos da árvore consultada. 
40 - 10 - 45 - 30 - 50. 
42 - 60 - 20 - 48 - 50. 
 40 - 60 - 45 - 48 - 50. 
42 - 60 - 20 - 30 - 50. 
40 - 15 - 45 - 30 - 50. 
 
ENSINEME: ALGORITMOS EM GRAFOS 
 
 5. Ref.: 3992632 Pontos: 0,00 / 1,00
(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014)
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990635.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990634.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992632.');
O grafo anterior pode ser representado pela seguinte matriz:
 
 
 6. Ref.: 3992631 Pontos: 1,00 / 1,00
(CESPE/CEBRASPE - TRT - 8ª Região (PA e AP) - Analista Judiciário - Tecnologia da Informação - 2016)
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992631.');
A quantidade de grau total do grafo na figura é:
17
 14
13
15
16
 
ENSINEME: ANÁLISE DE ALGORITMO 
 
 7. Ref.: 3990626 Pontos: 1,00 / 1,00
Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a
cada POP, o elemento retirado é inserido em um vetor de elementos. Após a completa inserção
de todos os elementos neste vetor, são feitas buscas de números na mesma. O tempo médio
de busca de um número neste elemento é: 
O(log N)
O(Nlog N)
O(1)
 O(N)
O(N )
 8. Ref.: 3990628 Pontos: 1,00 / 1,00
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de polinomio de
grau n da forma onde os coeficientes são números de
ponto flutuante armazenados no vetor [a..n], e o valor de n é maior que zero. Todos os
coeficientes podem assumir qualquer valor, exceto o coeficiente que é diferente de zero. 
2
an
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990626.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990628.');
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre
elas. 
1. Os algoritmos possuem a mesma complexida assintótica 
 PORQUE
1. Para o melhor caso, ambos possuem a complexidade O(n) 
 
A respeito dessas asserções, assinale a opção correta: 
 a primeira asserção é uma proposição falsa e a segunda uma proposição verdadeira. 
tanto a primeira quanto a segunda asserções são proposições falsas. 
a primeira asserção é uma proposição verdadeira e a segunda uma proposição falsa. 
as duas asserções são proposições verdadeiras e a segunda não é a justificativa correta
da primeira. 
as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa
correta da primeira. 
 
ENSINEME: RECURSIVIDADE 
 
 9. Ref.: 3992618 Pontos: 1,00 / 1,00
O código abaixo é uma implementação:
 
public class Misterio {
public static long Misterio(long x) {
if (x == 1)
return 1;
else
return x * Misterio(x-1);
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992618.');
}
}
Iterativa da série de Fibonacci
Iterativa da exponenciação
Recursiva da série de Fibonacci
 Recursiva do fatorial
Recursiva da exponenciação
 10. Ref.: 3992616 Pontos: 1,00 / 1,00
Analise o seguinte código:
 
public static double recursive (double d) {
if (d <= 1) {
return 1;
} else {
return d * recursive(d - 1);
}
}
 
Assinale o conteúdo que será exibido na saída do programa quando a função for chamada com o parâmetro 6:
240
 720
120
360
1440
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992616.');