PROVA NOTA 10 - COMPLEXIDADE DE ALGORITMOS

Prévia do material em texto

PROVA AV NOTA 10 
COMPLEXIDADE DE ALGORITMOS
1 ponto 
1. 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, V, F 
F, F, V 
V, F, V 
V, V, V 
1 ponto 
2. 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: 
I, III, IV, V. 
I, II, IV, V. 
NOTA 10
II, III, V. 
II, III, IV, V. 
II, III, IV. 
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: 
Condicionalidade 
Interligação 
Repetição 
Recursividade 
Rotatividade 
1 ponto 
4. Considere a função recursiva `func¿ definida por 
func(1) = 1 
func(n) = (n - 1) * func(n - 1) 
Quais são os valores de func(4) e func(5), respectivamente? 
12 e 24 
1 e 2 
2 e 6 
6 e 24 
24 e 120 
1 ponto 
5. Analise as seguintes afirmativas sobre os métodos de ordenação: 
NOTA 10
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.
Assinale a alternativa correta: 
A afirmativa II está errada, e as afirmativas I e III estão certas. 
As afirmativas I, II e III estão certas. 
A afirmativa III está errada, e as afirmativas I e II estão certas. 
A afirmativa I está errada, e as afirmativas II e III estão certas. 
As afirmativas I, II e III estão erradas. 
1 ponto 
6. 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. 
A complexidade do algoritmo bubble sort é de ordem logarítmica. 
O algoritmo de ordenação heap sort utiliza uma árvore ternária de 
busca. 
O algoritmo merge sort é implementado por meio de divisão e 
conquista. 
NOTA 10
PROVA AV NOTA 10 
COMPLEXIDADE DE ALGORITMOS
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: 
as duas afirmações são falsas. 
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 verdadeiras, e a segunda justifica a 
primeira. 
a primeira afirmação é verdadeira, e a segunda é falsa. 
1 ponto 
8. Observe a árvore binária a seguir: 
O caminhamento central (infixado) sobre essa árvore produz a 
NOTA 10
sequência de visitação: 
A - B - C - D - E - F - G - H - I - J - K 
A - B - D - E - H - I - J - K - C - F - G 
J - K - I - H - E - D - B - F - G - C - A 
D - H - J - K - I - E - B - F - G - C - A 
D - B - H - E - J - I - K - A - F - C - G 
1 ponto 
9. (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: 
 
Grafo 
Colunar 
Chave-valor 
Documento 
Tabular 
1 ponto 
10. (FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte - Tecnologia de 
Informação - 2017) 
NOTA 10
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: 
{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} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 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.NOTA 10