COMPLEXIDADE DE ALGORITMOS - Prova

Prévia do material em texto

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 é: 
 (Ref.: 202207613898) 
 
 
O(Nlog N) 
 
 
O(log N) 
 
 
O(N) 
 
 O(N22) 
 
 
O(1) 
 
 
 
 
1 ponto 
 
2. 
 
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 anan que é diferente de zero. 
 
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: 
 (Ref.: 202211248580) 
 
 
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. 
 
 
as duas asserções são proposições verdadeiras e a segunda não é a 
justificativa correta da primeira. 
 
 
tanto a primeira quanto a segunda asserção são proposições falsas. 
 
 
a primeira asserção é uma proposição verdadeira e a segunda uma 
proposição falsa. 
 
 
 
 
1 ponto 
 
3. 
 
 
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: 
 (Ref.: 202207615884) 
 
 
Condicionalidade 
 
 
Rotatividade 
 
 
Recursividade 
 
 
Interligação 
 
 
Repetição 
 
 
 
 
1 ponto 
 
4. 
 
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: 
 (Ref.: 202207615888) 
 
 
720 
 
 
240 
 
 
360 
 
 
120 
 
 
1440 
 
 
 
 
1 ponto 
 
5. 
 
 
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: 
 (Ref.: 202207682591) 
 
 
6 comparações e 10 trocas. 
 
 
16 comparações e 9 trocas. 
 
 
10 comparações e 8 trocas. 
 
 
10 comparações e 10 trocas. 
 
 
10 comparações e 9 trocas. 
 
 
 
 
1 ponto 
 
6. 
 
 
O algoritmo de ordenação mais eficiente para um conjunto grande de 
elementos randomicamente inseridos é: 
 (Ref.: 202207682595) 
 
 
Bubble sort 
 
 
Shell sort 
 
 
Quick sort 
 
 
Insert sort 
 
 
Selection sort 
 
 
 
 
1 ponto 
 
7. 
 
 
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: 
 (Ref.: 202207613911) 
 
 
as duas afirmações são verdadeiras, e a segunda não justifica a 
primeira. 
 
 
a primeira afirmação é falsa, e a segunda é verdadeira. 
 
 
as duas afirmações são falsas. 
 
 
a primeira afirmação é verdadeira, e a segunda é falsa. 
 
 
as duas afirmações são verdadeiras, e a segunda justifica a 
primeira. 
 
 
 
 
1 ponto 
 
8. 
 
 
 
Considerando a figura acima, que ilustra uma árvore de busca binária, 
assinale a opção correta. 
 (Ref.: 202207613908) 
 
 
O percurso a percorrer nessa árvore na pré-ordem é 4 10 15 12 8. 
 
 
Se a árvore em tela for balanceada, depois da inserção de um nó 9, 
o nó 12 assume a raiz da árvore. 
 
 
Se a árvore em questão não for balanceada, então, com a remoção 
do nó 8, o nó 12 deve assumir a raiz da árvore. 
 
 
Transformando essa árvore em uma nova árvore de ordem 2, as 
folhas teriam de estar no nível 2. 
 
 
Se a referida árvore for balanceada, a inserção de um nó 5 fará que 
ele tome o lugar do nó 4, passando a ser o nó 5 a raiz 
da subárvore. 
 
 
 
 
1 ponto 
 
9. 
 
 
(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? 
 (Ref.: 202207615900) 
 
 
11 
 
 
15 
 
 
9 
 
 
19 
 
 
17 
 
 
 
 
1 ponto 
 
10. 
 
(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: 
 
 (Ref.: 202207615901) 
 
 
{1} {2} {4} {6}, caminho mais curto 1-2-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. 
 
 
{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} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-
3-4-6.