COMPLEXIDADE DE ALGORITMOS AV CORRIGIDA

Prévia do material em texto

Disciplina: COMPLEXIDADE DE ALGORITMOS AV 
Aluno: 8 
 
 
Turma: 9003 
 
 
 
Avaliação: 
9,0 
Nota Partic.: Nota SIA: 
10,0 pts 
 
 
 
 
 
ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS 
 
 
 1. Ref.: 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 10 trocas. 
 16 comparações e 9 trocas. 
 6 comparações e 10 trocas. 
 10 comparações e 8 trocas. 
 
 
 2. Ref.: Pontos: 1,00 / 1,00 
 
Acerca dos algoritmos de ordenação, assinale a afirmativa correta: 
 
 O algoritmo merge sort é implementado por meio de divisão e 
conquista. 
 O algoritmo insertion sort é mais eficiente do que o quick sort para 
grandes entradas de dados. 
 A complexidade do algoritmo bubble sort é de ordem logarítmica. 
 O shell sort é um algoritmo de ordenação estável e instável. 
 O algoritmo de ordenação heap sort utiliza uma árvore ternária de 
busca. 
 
 
 
 
ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL 
 
 
 3. R Pontos: 1,00 / 1,00 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204059319.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204053480.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990640.');
Observe a árvore binária a seguir: 
 
O caminhamento central (infixado) sobre essa árvore produz a sequência de 
visitação: 
 
 J - K - I - H - E - D - B - F - G - C - A 
 D - H - J - K - I - E - B - F - G - C - A 
 A - B - D - E - H - I - J - K - C - F - G 
 D - B - H - E - J - I - K - A - F - C - G 
 A - B - C - D - E - F - G - H - I - J - K 
 
 
 4. Ref.: 3990635 Pontos: 1,00 / 1,00 
 
Á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. 
 
 Utilização de estruturas de dados como lista, pilha e fila. 
 As operações de inserir, retirar e pesquisar são definidas. 
 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 algoritmos de ordenação eficientes. 
 Não é necessário indexar os registros. 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990635.');
 
 
ENSINEME: ALGORITMOS EM GRAFOS 
 
 
 5. 
 
Pontos: 1,00 / 1,00 
 
(IBGE - Analista Censitário - Análise de Sistemas - Desenvolvimento de Aplicações - Web 
Mobile - 2017) 
Observe a figura a seguir que ilustra relações entre colegas e seus interesses: 
 
O tipo de Banco de Dados NoSQL, não relacional, que armazena tais informações, utilizando 
estruturas de vértices e arestas, com propriedades associadas, é o: 
 
 
Colunar 
 
Documento 
 
Tabular 
 Grafo 
 
Chave-valor 
 
 
 6. 
 
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 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992630.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992629.');
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} {3,2} {4,5} {6}, caminho mais curto 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. 
 {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. 
 
Pontos: 0,00 / 1,00 
 
Marque a alternativa correta. Vetor é uma coleção de variáveis de: 
 
 registros alocadas em sequência na memória. 
 diferentes tipos de dados distribuídos pela memória. 
 diferentes tipos de dados em sequência na memória. 
 tipo de dado homogêneo em sequência na memória. 
 tipo de dado homogêneo distribuído pela memória. 
 
 
 8. Ref.: 3990625 Pontos: 1,00 / 1,00 
 
Leia as afirmativas a seguir considerando que f(n) e g(n) são funções 
positivas. 
I- Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo f(n) 
possui Ordem de complexidade g(n). 
II- Se g(n) é O(f(n)), f(n) é um limite superior para g(n). 
III- Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)). 
IV- Se g(n) = n2 e f(n) = (n+1)2 temos que g(n) é O(f(n)) e f(n) é 
O(g(n)). 
V- Se g(n) = 2n+1 e f(n) = 2n temos que g(n) = O(f(n)). 
Assinale a alternativa que apresenta somente as afirmativas: 
 
 II, III, V. 
 I, II, IV, V. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990622.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990625.');
 II, III, IV, V. 
 II, III, IV. 
 I, III, IV, V. 
 
 
 
 
ENSINEME: RECURSIVIDADE 
 
 
 9. 
 
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: 
 
 
Repetição 
 Recursividade 
 
Rotatividade 
 
Condicionalidade 
 
Interligação 
 
 
 10. 
 
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 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. 
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. 
 
 III e IV 
 
I e IV 
 
II e III 
 
I e II 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992612.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992587.');
 
I e V