Av1 Algoritmo e complexidade

Prévia do material em texto

1. Ref.: 7642260 
 
 
A notação Big O é uma ferramenta importantíssima para os cientistas da computação 
analisarem o custo de um algoritmo. 
Tecnocamente falando, a notação Big O é uma notação matemática que descreve o 
comportamento limitante de uma função quando o argumento tende a um valor específico ou 
ao infinito. Ela pertence a uma família de notações inventadas por Paul Bachmann, Edmund 
Landau e outros, coletivamente chamadas de notação Bachmann¿Landau ou de notação 
assintótica. Ou seja, a notação Big O descreve a complexidade do seu código usando termos 
algébricos. 
Diante do contexdo apresentado, podemos afirmar: 
I ) Quando tentamos descobrir a Big O para uma função g(n) específica, nos preocupamos 
apenas com o termo dominante da função. O termo dominante é o termo que cresce mais 
rápido. 
II ) Na notação Big O, podemos dizer que um algoritmo tem a menor complexidade quando 
seu custo for O(1). 
III) De uma forma geral, a complexidade de um algoritmo tem relação principalmente com 
seu tempo de execução e espaço de memória ocupado para execução; 
IV ) Na notação Big O, podemos dizer que um algoritmo que tem a complexidade O(log(n)) é 
mais complexo do que que custa O(n⁴); 
Assinale a alternativa correta: 
 
 
 
apenas as afirmações I e IV são verdadeiras; 
 
apenas as afirmações I, II e IV são verdadeiras; 
 
apenas as afirmações II, III e IV são verdadeiras; 
 apenas as afirmações I, II e III são verdadeiras; 
 
todas as afirmações são verdadeiras; 
Respondido em 06/10/2022 19:54:28 
 
 
 2. Ref.: 7703471 
 
 
Seja n o tamanho da entrada de um algoritmo para um problema P. 
Cada alternativa, que corresponde a um algoritmo distinto, apresenta o número de operações 
necessárias para resolver P. 
Considerando-se a análise assintótica (Big O notation), qual algoritmo possui menor 
complexidade? 
 
 
15n + 256 
 2n 
 
5 n2 + n 
 
 
500 + 100 n3 
 100 + 10 log n 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207642260.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207703471.');
Respondido em 06/10/2022 19:38:16 
 
 
 3. Ref.: 4059324 
 
 
Em relação aos algoritmos de ordenação, avalie se as afirmativas a 
seguir são verdadeiras (V) ou falsas (F): 
 
I. O algoritmo quick sort é muito eficiente quando há uma quantidade 
pequena de elementos a ordenar. 
II. O algoritmo shell sort utiliza intensamente a inserção direta. 
III. No algoritmo bubble sort, o número de variáveis envolvidas é pequeno. 
 
As afirmativas I, II e III são, respectivamente: 
 
 
V, F e F 
 
V, F e V 
 
F, F e V 
 F, V e V 
 
V, V e V 
Respondido em 06/10/2022 19:42:24 
 
 
 4. Ref.: 4053476 
 
 
Considere que os percentuais foram inseridos no vetor vet de 5 posições, a 
partir da posição 1, na seguinte sequência: 25.33, 27.72, 27.10, 26.90 e 
27.31, ou seja, com os dados de 2008 até 2012. Um técnico 
em processamento de dados do TCE-RS utilizou um método para ordenar os 
dados de vet. O método realizou os seguintes passos no processo de 
ordenação: 
 
• Passo 1 - 25.33 27.72 27.10 26.90 27.31; 
• Passo 2 - 25.33 27.10 27.72 26.90 27.31; 
• Passo 3 - 25.33 26.90 27.10 27.72 27.31; 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204059324.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204053476.');
• Passo 4 - 25.33 26.90 27.10 27.31 27.72. 
 
Trata-se do método de ordenação: 
 
 Insertion sort 
 
Fast sort 
 
Bubble sort 
 
Quick sort 
 
Selection sort 
Respondido em 06/10/2022 19:38:35 
 
 
 5. Ref.: 4059323 
 
 
O algoritmo de ordenação mais eficiente para um conjunto grande de 
elementos randomicamente inseridos é: 
 
 
Selection sort 
 
Shell sort 
 
Bubble sort 
 
Insert sort 
 Quick sort 
Respondido em 06/10/2022 19:40:52 
 
 
 6. Ref.: 4053481 
 
 
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 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204059323.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204053481.');
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, II, III, IV, V 
 V, II, III, IV, I 
 
V, IV, II, III, I 
 
I, III, II, IV, V 
 
I, IV, V, III, II 
Respondido em 06/10/2022 19:43:16 
 
 
 7. Ref.: 3990624 
 
 
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. 
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 
 
F, F, V 
 V, V, V 
 
F, V, F 
 
V, F, V 
Respondido em 06/10/2022 19:40:36 
 
 
 8. Ref.: 4053479 
 
 
Analise as seguintes afirmativas sobre os métodos de ordenação: 
 
I. Quick sort divide um conjunto de itens em conjuntos menores, que são 
ordenados de forma independente, e, depois, os resultados são combinados 
para produzir a solução de ordenação do conjunto maior. 
 
II. Seleção é um método que consiste em selecionar o menor item de um 
vetor e substituí-lo pelo item que estiver na primeira posição. Essas duas 
operações são repetidas com os itens restantes até o último elemento. 
 
III. Shell sort é uma extensão do algoritmo de ordenação por inserção, 
contornando o problema que ocorre quando o menor item de um vetor está 
na posição mais à direita. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990624.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204053479.');
 
Assinale a alternativa correta: 
 
 As afirmativas I, II e III estão certas. 
 
As afirmativas I, II e III estão erradas. 
 
A afirmativa II está errada, e as afirmativas I e III estão certas. 
 
A afirmativa I está errada, e as afirmativas II e III estão certas. 
 
A afirmativa III está errada, e as afirmativas I e II estão certas. 
Respondido em 06/10/2022 19:43:49 
 
 
 9. Ref.: 3992613 
 
 
Sobre o conceito de Algoritmos Recursivos, analise as afirmações abaixo e, a seguir, assinale a 
alternativa correta. 
I. Um programa tem um número limitado de procedimentos recursivos. 
II. Recursividade é utilizada exclusivamente quando não se sabe solucionarum problema de 
maneira imediata, então é realizada a divisão em problemas menores para alcançar o 
resultado desejado. 
III. Todos os problemas computacionais resolvidos de maneira iterativa gastam mais memória 
que se resolvidos de forma recursiva. 
 
 
As afirmações I e II estão corretas 
 
Somente a afirmação III está correta 
 
Somente a afirmação II está correta 
 
Somente a afirmação I está correta 
 Nenhuma das afirmações está correta 
Respondido em 06/10/2022 19:44:30 
 
 
 10. Ref.: 3992612 
 
 
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 
 
Condicionalidade 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992613.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992612.');
 
Rotatividade 
 
Interligação 
 
Repetição 
Respondido em 06/10/2022 19:40:55