AV1 Complexidade de Algoritimos 2022

Prévia do material em texto

Avaliação AV
 
avalie seus conhecimentos
RETORNAR À AVALIAÇÃO
Disciplina: EEX0030 - COMPLEXIDADE DE ALGORITMOS 
Data: 14/09/2022 16:58:23
Período: 2022.3 EAD (GT) / AV 
Turma: 9001
 ATENÇÃO
1. Veja abaixo, todas as suas respostas gravadas no nosso banco de dados.
2. Caso você queira voltar à prova clique no botão "Retornar à Avaliação".
1a Questão (Ref.: 202106386485)
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(log N)
O(N)
O(Nlog N)
O(1)
O(N\(^2\))
2a Questão (Ref.: 202110021167)
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 \
(a_n\) que é diferente de zero. 
javascript:voltar_avaliacoes()
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990626\n\nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7625308\n\nStatus da quest%C3%A3o: Liberada para Uso.');
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: 
as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa
correta da primeira. 
as duas asserções são proposições verdadeiras e a segunda não é a justificativa
correta da primeira. 
a primeira asserção é uma proposição verdadeira e a segunda uma
proposição falsa. 
tanto a primeira quanto a segunda asserção são proposições falsas. 
a primeira asserção é uma proposição falsa e a segunda uma proposição
verdadeira. 
3a Questão (Ref.: 202106388477)
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);
}
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992618\n\nStatus da quest%C3%A3o: Liberada para Uso.');
}
Recursiva do fatorial
Iterativa da série de Fibonacci
Recursiva da série de Fibonacci
Iterativa da exponenciação
Recursiva da exponenciação
4a Questão (Ref.: 202106388440)
Ano: 2019 Banca: Quadrix Órgão: Prefeitura de Jataí - GO Prova: Quadrix - 2019 - Prefeitura de Jataí - GO -
Analista de Tecnologia da Informação
A situação em que dois subprogramas fazem chamadas recíprocas, como, por exemplo, um subprograma P faz
uma chamada a um subprograma J, que, por sua vez, faz uma chamada a P, é caracterizada como uma
Recursividade indireta
Recursividade direta
Lista circular
Recursividade simples
Lista linear simples
5a Questão (Ref.: 202106449340)
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
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992581\n\nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 4053481\n\nStatus da quest%C3%A3o: Liberada para Uso.');
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, é: 
V, IV, II, III, I 
I, II, III, IV, V 
V, II, III, IV, I 
I, IV, V, III, II 
I, III, II, IV, V 
6a Questão (Ref.: 202106449339)
Acerca dos algoritmos de ordenação, assinale a afirmativa correta: 
O algoritmo de ordenação heap sort utiliza uma árvore ternária de busca. 
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 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. 
7a Questão (Ref.: 202106386494)
Á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 algoritmos de ordenação eficientes. 
Utilização de estruturas de dados como lista, pilha e fila. 
As operações de inserir, retirar e pesquisar são definidas. 
Não é necessário indexar os registros. 
8a Questão (Ref.: 202106386493)
Imagine que temos números de 1 a 100 em uma árvore de pesquisa binária (ABP).
Agora queremos procurar o número 50. Assinale a alternativa que apresenta a possível
sequência de elementos da árvore consultada. 
42 - 60 - 20 - 48 - 50. 
40 - 10 - 45 - 30 - 50. 
40 - 60 - 45 - 48 - 50. 
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: 3990635\n\nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3990634\n\nStatus da quest%C3%A3o: Liberada para Uso.');
40 - 15 - 45 - 30 - 50. 
42 - 60 - 20 - 30 - 50. 
9a Questão (Ref.: 202106388489)
(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:
Chave-valor
Documento
Colunar
Tabular
Grafo
10a Questão (Ref.: 202106388491)
(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014)
O grafo anterior pode ser representado pela seguinte matriz:
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992630\n\nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 3992632\n\nStatus da quest%C3%A3o: Liberada para Uso.');