ALGORITMOS E COMPLEXIDADE

Prévia do material em texto

Disciplina: ALGORITMOS E COMPLEXIDADE  AV
Aluno: BRUNO MARQUES DA SILVA FILHO 202202308511
Turma: 9001
DGT1348_AV_202202308511 (AG)   14/03/2023 19:37:40 (F) 
Avaliação: 9,00 pts Nota SIA: 10,00 pts
 
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, IV, V, III, II 
I, II, III, IV, V 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053481.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053481.');
Bruno Marques
Destacar
Bruno Marques
Destacar
Bruno Marques
Destacar
Bruno Marques
Destacar
Bruno Marques
Destacar
Bruno Marques
Destacar
Bruno Marques
Destacar
Bruno Marques
Destacar
Bruno Marques
Retângulo
V, IV, II, III, I 
 V, II, III, IV, I 
I, III, II, IV, V 
 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 a alternativa que apresenta somente
algoritmos com complexidade assintótica, quando f(n) = O(n log n): 
Quick sort e insertion sort. 
Merge sort e bubble sort. 
 Quick sort e merge sort. 
Insertion sort. 
Bubble sort. 
 
ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL  
 
 3. Ref.: 3990639 Pontos: 1,00  / 1,00
Após a inserção de um nó, é necessário veri�car cada um dos nós ancestrais desse nó inserido, relativamente
à consistência com as regras estruturais de uma árvore AVL. 
                                                  PORQUE 
O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por {−2, −1,
0, +1, +2}. 
 
Analisando-se as a�rmações acima, conclui-se que: 
 a primeira a�rmação é verdadeira, e a segunda é falsa.  
a primeira a�rmação é falsa, e a segunda é verdadeira.  
as duas a�rmações são verdadeiras, e a segunda não justi�ca a primeira.  
as duas a�rmações são verdadeiras, e a segunda justi�ca a primeira.  
as duas a�rmações são falsas. 
 4. Ref.: 3990635 Pontos: 1,00  / 1,00
Árvore de pesquisa é uma estrutura de dados e�ciente 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 estruturas de dados como lista, pilha e �la. 
As operações de inserir, retirar e pesquisar são de�nidas. 
 Acesso direto e sequencial e�cientes, 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.  
Não é necessário indexar os registros. 
Utilização de algoritmos de ordenação e�cientes.  
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059327.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059327.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990639.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990639.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990635.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990635.');
 
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 �uxo que possui 5 nós e 12 arcos. Qual a complexidade ciclomática desse grafo?
11
15
17
19
 9
 6. Ref.: 3992629 Pontos: 1,00  / 1,00
(FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte - Tecnologia de Informação - 2017)
Considere a estrutura abaixo que representa um problema de rotas em pequena escala:
Considere, por hipótese, que se solicitou a um Agente de Fiscalização à Regulação de Transporte da ARTESP utilizar
alguma estratégia lógica para, partindo do ponto 1, chegar ao ponto 6 usando a menor rota. De um mesmo ponto
pode haver mais de uma rota, com distâncias diferentes. A lógica correta utilizada pelo Agente, em função dos
pontos a serem percorridos, foi:
{6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-3-4-6.
{1} {2} {4} {6}, caminho mais curto 1-2-4-6.
{1} {2,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-6.
 {1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6.
{6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, que é igual a 1-2-5-3-4-6.
 
ENSINEME: ANÁLISE DE ALGORITMO  
 
 7. Ref.: 3990621 Pontos: 1,00  / 1,00
No algoritmo abaixo, os parâmetros da função valor são recebidos e são impressos na própria função. Assim
sendo, o valor da variável u exibido na última linha da função é: 
Algoritmo questao_prova; 
var 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992628.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992628.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992629.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992629.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990621.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990621.');
x,y: inteiro; 
inicio 
x<- 4; 
y<- 2; 
valor(x,y); 
�m. 
 
sub-rotina valor(inteiro: u, v) 
inicio 
u <- u * 2; 
v <- v + u; 
u <- u - 1; 
escreva(u); 
�m sub-rotina; 
 
Marque a opção que mostra o valor correto exibido da variável u. 
10
5
8
 7
4
 8. Ref.: 3990624 Pontos: 0,00  / 1,00
Classi�que cada uma das seguintes a�rmaçõ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 de�nido como qualquer tipo de dado que a linguagem utiliza ou como outra
estrutura de dados: vetor, matriz ou mesmo outro registro. 
 V, V, V 
F, F, V 
 V, F, F 
F, V, F 
V, F, V 
 
ENSINEME: RECURSIVIDADE  
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990624.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990624.');
 9. Ref.: 3992587 Pontos: 1,00  / 1,00
Ano: 2017 Banca: CONSULPLAN Órgão: TRE-RJ Prova: CONSULPLAN - 2017 - TRE-RJ - Técnico Judiciário -
Programação de Sistemas
Analise as a�rmativas a seguir a respeito de algoritmos recursivos.
I. Diz-se que uma rotina é recursiva se a sua de�nição envolver uma chamada a ela mesma. Neste sentido, o termo
recursão é equivalente ao termo indução utilizado por matemáticos.II. Cada algoritmo recursivo possui um algoritmo iterativo equivalente e vice-versa, mas que pode ter mais ou menos
complexidade em sua construção.
III. Uma função recursiva possui duas partes: caso base e caso recursivo.
IV. Um algoritmo pode ser chamado de iterativo quando ele requer a repetição implícita de um processo até que
determinada condição seja satisfeita.
V. A recursividade possibilita a escrita de um código mais enxuto, com maior legibilidade e simplicidade.
Assinale a alternativa que possui alguma a�rmação INCORRETA.
I e II
 III e IV
II e III
I e V
I e IV
 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 é de�nido 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:
Condicionalidade
 Recursividade
Repetição
Rotatividade
Interligação
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992587.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992587.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992612.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992612.');