ALGORITMOS E COMPLEXIDADE

Prévia do material em texto

ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS 
 
 
 1. Ref.: 4053480 Pontos: 1,00 / 1,00 
 
Acerca dos algoritmos de ordenação, assinale a afirmativa correta: 
 
 
O algoritmo insertion sort é mais eficiente do que o quick sort para grandes 
entradas de dados. 
 
O shell sort é um algoritmo de ordenação estável e instável. 
 
A complexidade do algoritmo bubble sort é de ordem logarítmica. 
 
O algoritmo de ordenação heap sort utiliza uma árvore ternária de busca. 
 O algoritmo merge sort é implementado por meio de divisão e conquista. 
 
 
 2. Ref.: 4059319 Pontos: 1,00 / 1,00 
 
O algoritmo bubble sort é popular, mesmo que ineficiente. Usando esse algoritmo 
para ordenar um vetor em ordem crescente, contendo os números [ 5, 4, 1, 3, 2 ], 
serão feitas: 
 
 
10 comparações e 9 trocas. 
 10 comparações e 8 trocas. 
 
10 comparações e 10 trocas. 
 
6 comparações e 10 trocas. 
 
16 comparações e 9 trocas. 
 
 
 
 
ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL 
 
 
 3. Ref.: 3990638 Pontos: 1,00 / 1,00 
 
Árvore AVL é uma árvore de busca autobalanceada. Isso significa que: 
 
 
as alturas das duas subárvores a partir de cada nó são exatamente iguais. 
 
cada nó da árvore possui até três descendentes. 
 as alturas das duas subárvores a partir de cada nó diferem no máximo em 
uma unidade. 
 
pode possuir até duas raízes. 
 
as alturas das duas subárvores a partir de cada nó diferem no máximo em 
duas unidades. 
 
 
 4. Ref.: 3990635 Pontos: 1,00 / 1,00 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204053480.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204059319.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990638.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990635.');
Á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. 
 
 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. 
 
As operações de inserir, retirar e pesquisar são definidas. 
 
Utilização de algoritmos de ordenação eficientes. 
 
Não é necessário indexar os registros. 
 
Utilização de estruturas de dados como lista, pilha e fila. 
 
 
 
 
ENSINEME: ALGORITMOS EM GRAFOS 
 
 
 5. Ref.: 3992628 Pontos: 1,00 / 1,00 
 
(CESGRANRIO - Transpetro - Analista de Sistemas Júnior - Processos de Negócio 
- 2018) 
Uma das medidas de qualidade do código de um software é a Complexidade, que pode 
ser medida por meio da complexidade ciclomática. 
Considere um grafo de fluxo que possui 5 nós e 12 arcos. Qual a complexidade 
ciclomática desse grafo? 
 
 
11 
 9 
 
17 
 
19 
 
15 
 
 
 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%20da%20quest%C3%A3o:%203992628.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992631.');
 
A quantidade de grau total do grafo na figura é: 
 
 
15 
 14 
 
17 
 
16 
 
13 
 
 
 
 
ENSINEME: ANÁLISE DE ALGORITMO 
 
 
 7. Ref.: 7625308 Pontos: 0,00 / 1,00 
 
Analise o custo computacional dos algoritmos a seguir, que calculam o valor 
de polinômio 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 an�� que é diferente de zero. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207625308.');
 
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 complexidade 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 verdadeira e a segunda uma 
proposição falsa. 
 
tanto a primeira quanto a segunda asserção são proposições falsas. 
 
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. 
 a primeira asserção é uma proposição falsa e a segunda uma proposição 
verdadeira. 
 
 
 8. Ref.: 3990624 Pontos: 1,00 / 1,00 
 
Classifique cada uma das seguintes afirmações em "V" (se verdadeira) ou "F" (se 
falsa) e escolha a alternativa que corresponde à sequência correta de indicações. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990624.');
I- Um registro reúne uma coleção de informações, facilitando a sua organização e o 
seu uso. 
II- Cada informação distinta de um registro é considerada um atributo ou campo. 
III- O atributo pode ser definido como qualquer tipo de dado que a linguagem utiliza 
ou como outra estrutura de dados: vetor, matriz ou mesmo outro registro. 
 
 
V, F, F 
 V, V, V 
 
F, F, V 
 
V, F, V 
 
F, V, F 
 
 
 
 
ENSINEME: RECURSIVIDADE 
 
 
 9. Ref.: 3992614 Pontos: 1,00 / 1,00 
 
Considere a função recursiva `func¿ definida por 
func(1) = 1 
func(n) = (n - 1) * func(n - 1) 
Quais são os valores de func(4) e func(5), respectivamente? 
 
 
12 e 24 
 
24 e 120 
 6 e 24 
 
2 e 6 
 
1 e 2 
 
 
 10. Ref.: 3992612 Pontos: 1,00 / 1,00 
 
Ano: 2010 Banca: FCC Órgão: TRT - 20ª REGIÃO (SE) Prova: FCC - 2010 - TRT - 20ª 
REGIÃO (SE) - Técnico Judiciário - Tecnologia da Informação 
Objeto que se constitui parcialmente ou é definido em termos de si próprio. Nesse 
contexto, um tipo especial de procedimento (algoritmo) será utilizado, algumas vezes, 
para a solução de alguns problemas. Esse procedimento é denominado: 
 
 Recursividade 
 
Interligação 
 
Rotatividade 
 
Repetição 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992614.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992612.');
 
Condicionalidade