COMPLEXIDADE DE ALGORITMOS ESTACIO EAD

Prévia do material em texto

1a Questão (Ref.: 202013530075) 
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(N22) 
 O(N) 
 O(log N) 
 O(1) 
 O(Nlog N) 
 
 
 
 2a Questão (Ref.: 202013530073) 
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. 
 
 F, V, F 
 V, V, V 
 V, F, F 
 V, F, V 
 F, F, V 
 
 
 
 3a Questão (Ref.: 202013532036) 
Ano: 2017 Banca: CONSULPLAN Órgão: TRE-RJ Prova: CONSULPLAN - 2017 - TRE-RJ - 
Técnico Judiciário - Programação de Sistemas 
Analise as afirmativas a seguir a respeito de algoritmos recursivos. 
I. Diz-se que uma rotina é recursiva se a sua definiçã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. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990626/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990624/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992587/n/nStatus da quest%C3%A3o: Liberada para Uso.');
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 afirmação INCORRETA. 
 
 
I e V 
 
III e IV 
 
II e III 
 
I e II 
 
I e IV 
 
 
 4a Questão (Ref.: 202013532067) 
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); 
} 
} 
 
 
Recursiva da série de Fibonacci 
 
Iterativa da série de Fibonacci 
 
Recursiva do fatorial 
 
Iterativa da exponenciação 
 
Recursiva da exponenciação 
 
 
 5a Questão (Ref.: 202013598772) 
O algoritmo de ordenação mais eficiente para um conjunto grande de 
elementos randomicamente inseridos é: 
 
 Shell sort 
 Quick sort 
 Bubble sort 
 Insert sort 
 Selection sort 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992618/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4059323/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 6a Questão (Ref.: 202013592929) 
Acerca dos algoritmos de ordenação, assinale a afirmativa correta: 
 
 O shell sort é um algoritmo de ordenação estável e instável. 
 O algoritmo insertion sort é mais eficiente do que o quick sort para 
grandes entradas de dados. 
 O algoritmo merge sort é implementado por meio de divisão e conquista. 
 O algoritmo de ordenação heap sort utiliza uma árvore ternária de 
busca. 
 A complexidade do algoritmo bubble sort é de ordem logarítmica. 
 
 
 
 7a Questão (Ref.: 202013530088) 
Após a inserção de um nó, é necessário verificar 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 afirmações acima, conclui-se que: 
 
 as duas afirmações são verdadeiras, e a segunda justifica a primeira. 
 a primeira afirmação é falsa, e a segunda é verdadeira. 
 a primeira afirmação é verdadeira, e a segunda é falsa. 
 as duas afirmações são falsas. 
 as duas afirmações são verdadeiras, e a segunda não justifica a 
primeira. 
 
 
 
 8a Questão (Ref.: 202013530084) 
Á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. 
 Utilização de estruturas de dados como lista, pilha e fila. 
 Utilização de algoritmos de ordenação eficientes. 
 As operações de inserir, retirar e pesquisar são definidas. 
 Não é necessário indexar os registros. 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053480/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990639/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990635/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 9a Questão (Ref.: 202013532077) 
(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 
 
17 
 
15 
 
19 
 
9 
 
 
 10a Questão (Ref.: 202013532078) 
(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,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-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. 
 {1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6. 
 {1} {2} {4} {6}, caminho mais curto 1-2-4-6. 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992628/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992629/n/nStatus da quest%C3%A3o: Liberada para Uso.');