Prova AV - COMPLEXIDADE DE ALGORITMOS

Prévia do material em texto

Disciplina: COMPLEXIDADE DE ALGORITMOS AV 
Aluno: 
Professor: 
 
Turma: 
 
 
 
Avaliação: 
7,0 
Nota Partic.: Nota SIA: 
9,0 pts 
 
 
 
 
 
 
 
 1. Pontos: 1,00 / 1,00 
 
Analise as seguintes afirmativas sobre os métodos de ordenação: 
 
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: 
 
 As afirmativas I, II e III estão erradas. 
 As afirmativas I, II e III estão certas. 
 A afirmativa I está errada, e as afirmativas II e III estão certas. 
 A afirmativa II está errada, e as afirmativas I e III estão certas. 
 A afirmativa III está errada, e as afirmativas I e II estão certas. 
 
 
 2. Pontos: 1,00 / 1,00 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204053479.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204059327.');
Se f é uma função de complexidade para um algoritmo F, então, O(f) é 
considerada a complexidade assintótica ou o comportamento assintótico do 
algoritmo F. Assinale a alternativa que apresenta somente 
algoritmos com complexidade assintótica, quando f(n) = O(n log n): 
 
 Quick sort e merge sort. 
 Quick sort e insertion sort. 
 Bubble sort. 
 Insertion sort. 
 Merge sort e bubble sort. 
 
 
 
 
 3. 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. 
 
 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. 
 Utilização de estruturas de dados como lista, pilha e fila. 
 Não é necessário indexar os registros. 
 
 
 4. Pontos: 1,00 / 1,00 
 
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 - 30 - 50. 
 40 - 60 - 45 - 48 - 50. 
 40 - 15 - 45 - 30 - 50. 
 40 - 10 - 45 - 30 - 50. 
 42 - 60 - 20 - 48 - 50. 
 
 
 
 5. Pontos: 1,00 / 1,00 
 
(CESPE/CEBRASPE - TRT - 8ª Região (PA e AP) - Analista Judiciário - Tecnologia da Informação 
- 2016) 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990635.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990634.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992631.');
 
A quantidade de grau total do grafo na figura é: 
 
 
16 
 
15 
 
17 
 14 
 
13 
 
 
 6. Pontos: 0,00 / 1,00 
 
(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%20da%20quest%C3%A3o:%203992632.');
 
 
 
 
 
 
 
 
 7. Pontos: 0,00 / 1,00 
 
No algoritmo abaixo, os parâmetros da função valor são recebidos e são 
impressos na própria função. Assim sendo, o valor da variável u exibido na 
última linha da função é: 
Algoritmo questao_prova; 
var 
x,y: inteiro; 
inicio 
x<- 4; 
y<- 2; 
valor(x,y); 
fim. 
 
sub-rotina valor(inteiro: u, v) 
inicio 
u <- u * 2; 
v <- v + u; 
u <- u - 1; 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990621.');
escreva(u); 
fim sub-rotina; 
 
Marque a opção que mostra o valor correto exibido da variável u. 
 
 4 
 5 
 10 
 8 
 7 
 
 
 8. Pontos: 0,00 / 1,00 
 
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 complexida assintótica 
 PORQUE 
1. Para o melhor caso, ambos possuem a complexidade O(n) 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990628.');
A respeito dessas asserções, assinale a opção correta: 
 
 a primeira asserção é uma proposição verdadeira e a segunda uma 
proposição falsa. 
 a primeira asserção é uma proposição falsa e a segunda uma proposição 
verdadeira. 
 tanto a primeira quanto a segunda asserções são proposições falsas. 
 as duas asserções são proposições verdadeiras e a segunda não é a 
justificativa correta da primeira. 
 as duas asserções são proposições verdadeiras, mas a segunda é uma 
justificativa correta da primeira. 
 
 
 9. Pontos: 1,00 / 1,00 
 
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 
 
24 e 120 
 6 e 24 
 
 
 10. Pontos: 1,00 / 1,00 
 
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 simples 
 
Lista circular 
 Recursividade indireta 
 
Recursividade direta 
 
Lista linear simples 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992614.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992581.');