Apol objetiva 1

Prévia do material em texto

Questão 1/10 - Estrutura de Dados 
"A análise de um algoritmo geralmente conta com apenas algumas operações elementares e, em muitos casos, apenas uma operação elementar... Além 
disso, essa análise costuma ser feita tendo como base um modelo independente de máquina; isto é, a expressão de consumo de tempo é feita abstraindo 
particularidades como a linguagem de programação, os detalhes de implementação e o computador utilizado. Esse modelo de computação, conhecido como 
RAM (do inglês random access machine, ou máquina de acesso aleatório, em língua portuguesa), assume os seguintes custos associados às operações 
executadas por um computador (SKIENKA, 2008): 
Cada operação simples (operações aritméticas, comparações e invocações de métodos) custam exatamente um passo de tempo. 
Laços (loops) e sub-rotinas não são considerados operações simples. Ao contrário, eles são a composição de múltiplas operações de um passo de tempo. ... 
Assim, o tempo necessário para executar um laço ou um subprograma depende do número de iterações do laço ou da natureza específica do subprograma. 
Cada acesso à memória requer exatamente um passo de tempo." 
Serpa, Matheus da, S. et al. Análise de Algoritmos. Disponível em: Minha Biblioteca, Grupo A, 2021.pag 51-52 
Observe o algoritmo abaixo escrito em linguagem Pyhton: 
 1 def exercicios1(dados) 
 2 for i in range(0,len(dados),1): 
 3 if dados[i] > 0: 
 #... restante do código (não relevante para a questão)# 
 
Com base no texto e no código fornecido, considerando ainda que n é a quantidade de elementos em dados, é correto afirmar: 
I . A complexidade para a linha 2 é O(n). 
II. A complexidade na linha 2 é O(n/2). 
III. A complexidade da linha 3 é O(1). 
IV. A complexidade do algoritmo é O(n+1). 
 
Estão corretas as afirmativas: 
Nota: 10.0 
 
A I somente. 
 
B I e II somente. 
 
C I e III somente. 
Você assinalou essa alternativa (C) 
Você acertou! 
Aula 1 temas 2 e 3 
 
D II e III somente 
 
E I, II e III. 
 
Questão 2/10 - Estrutura de Dados 
Considere o trecho de código abaixo: 
a = 1 
b = a*10 
if a > b: 
 c = a 
else: 
 c = b 
 Acerca do código acima são feitas as seguintes afirmativas: 
 I. Cada operação (linha de código) tem complexidade assintótica O(1). 
II. Todas as operações são constantes, ou seja, executa da mesma forma para entradas grandes ou pequenas. 
III. A complexidade do código em questão é a soma de todas as complexidades, no caso: O(1) + O(1) + O(1)+ O(1)+ O(1)+ O(1)= O(6n). 
Estão corretas as afirmativas: 
Nota: 0.0Você não pontuou essa questão 
 
A 
I somente. 
 
B II somente. 
Você assinalou essa alternativa (B) 
 
C I e II somente. 
Aula 1 – tema 3 
 
D I e III somente. 
 
E II e III somente. 
 
Questão 3/10 - Estrutura de Dados 
Uma estrutura de dados operando como uma fila, opera com o princípio de o primeiro que entra é o primeiro que sai, ou em inglês, first in first out (fifo) . 
Implementar uma fila significa fazer uma inserção (queue) no final dela, e fazer a remoção (dequeue)no início dela. 
Após realizar a sequencia de operações 
QUEUE (11),QUEUE (34) ,DEQUEUE ( ), QUEUE (23) , DEQUEUE ( ) , QUEUE (14) , QUEUE (25) , DEQUEUE ( ) 
O conteúdo da fila será: 
Nota: 0.0Você não pontuou essa questão 
 
A 25 
 
B 11,34,23,14,25 
Você assinalou essa alternativa (B) 
 
C 11,23,14,25 
 
D 14,25 
Aula 3 – tema 4 
 
E 11,14 
 
Questão 4/10 - Estrutura de Dados 
Uma estrutura de dados é uma pilha quando só conseguimos manipular o que está em seu topo. Uma estrutura de pilha em programação opera como 
princípio chamado o primeiro que entra é o último que sai. A expressão correspondente em inglês é first in last out (filo) . Uma estrutura de dados operando 
como uma fila, opera com o princípio de o primeiro que entra é o primeiro que sai, ou em inglês, first in first out (fifo) . 
Inserindo a seguinte sequência em uma pilha: 
 
23, 44, 29, 12, 25, 60, 80, 29, 18 
Teríamos a pilha: 
I.(Topo) __________________________________________________ 
Retirando da pilha e inserindo na fila, teríamos a fila: 
 
II.(começo)_________________________________________________(fim) 
As estruturas pilha e fila terão, respectivamente, os valores: 
Nota: 0.0Você não pontuou essa questão 
 
A I.18,29,80,60,25,12,29,44,23 
II.23, 44, 29, 12, 25, 60, 80, 29,18 
 
B I.18,29,80,60,25,12,29,44,23 
II.18,29,80,60,25,12,29,44,23 
Aula 3 – temas 3 e 4 
 
C I.23, 44, 29, 12, 25, 60, 80, 29,18 
II.18,29,80,60,25,12,29,44,23 
Você assinalou essa alternativa (C) 
 
D I.23, 44, 29, 12, 25, 60, 80, 29,18 
II.23, 44, 29, 12, 25, 60, 80, 29,18 
 
E N.D.A (Nenhuma das alternativas) 
 
Questão 5/10 - Estrutura de Dados 
Observe o trecho do algoritmo abaixo e analise o seu comportamento 
 
X = [6, 5, 2, 3, 4, 1] 
n = 0 
troca = 1 
 
while n <= len(X) and troca == 1: 
 troca = 0 
 for i in range(0, len(X)-1, 1): 
 if X[i] > X[i+1]: 
 troca = 1 
 aux = X[i] 
 X[i] = X[i+1] 
 X[i+1] = aux 
 n = n + 1 
Analisando o comportamento do algoritmo que flutua para o topo o maior elemento, pode se afirmar que se trata de qual algoritmo de ordenação? 
Nota: 10.0 
 
A Heapsort 
 
B Mergesort 
 
C Quicksort 
 
D Bubble sort 
Você assinalou essa alternativa (D) 
Você acertou! 
Aula 2 tema1 
 
E Insertion sort 
 
Questão 6/10 - Estrutura de Dados 
Chamamos de análise assintótica de algoritmos quando encontramos a complexidade de um algoritmo de maneira aproximada através de uma curva de 
tendência. Este tipo de análise e é a mais adotada para compararmos desempenho de algoritmos. Para podermos comparar a complexidade dos algoritmos, 
podemos analisá-los matematicamente. A notação mais comum adotada na literatura para comparar algoritmos e dizer o quão rápido um algoritmo é, é a 
notação Big-O (ou “Grande-O”). (Adaptada) 
Acerca complexidade de um algoritmo, assinale a alternativa INCORRETA: 
Nota: 10.0 
 
A Um algoritmo com três laços de repetição não encadeados contém uma complexidade assintótica, para o pior caso, O(n). 
 
B Na análise assintótica, fazemos o conjunto de dados de entrada da função custo tender ao infinito, mantendo na equação somente o termo de maior grau, ou seja, aquele que mais cresce 
na equação. 
 
C Um algoritmo com três laços de repetição aninhados contém uma complexidade assintótica, para o pior caso, O(n³). 
 
D A complexidade assintótica para o pior caso, também conhecida como Big O, representa o pior cenário para um algoritmo, ou seja, quando mais instruções precisam ser executadas, 
levando mais tempo para finalizar a execução. 
 
E A complexidade assintótica para o pior caso de um algoritmo contendo dois laços de repetição aninhados, sendo que o segundo laço só será executado caso uma condicional simples seja 
verdadeira, será O(n). 
Você assinalou essa alternativa (E) 
Você acertou! 
AULA 1 –tema 2 e TEMA 3. O pior caso (BigO) nos diz que todas as linhas devem ser executadas, ou seja, a condicional será sempre verdadeira, e ambos laços de repetição serão sempre executados, 
sendo assim, complexidade O(n²). 
 
 
Questão 7/10 - Estrutura de Dados 
"Um exemplo de software que utiliza estrutura de dados conhecida é o jogo da cobrinha, tendo as seguintes regras: 
1.o corpo da cobrinha crescerá à medida que a cabeça tocar um quadrado com a cor diferente da cabeça, e o quadrado vai para o final do corpo da 
cobrinha. 
2.o corpo da cobrinha diminuirá à medida que a cabeça tocar um quadrado com a mesma cor da cabeça, e a cabeça será retirada da cobrinha e o próximo 
quadrado passa a ser a cabeça." 
Rodrigues, Thiago, N. et al. Estrutura de Dados em Java. Disponível em: Minha Biblioteca, Grupo A, 2021.Pag 65 
Acerca da estrutura de dados e das regras mencionadas acima são feitas as seguintes afirmativas: 
I.A regra 1 pode ser considerada uma ação de empilhar um elemento em uma pilha 
II.A regra 1 pode ser considerada uma ação de enfileirarum elemento em uma fila 
III.A regra 2 pode ser considerada ação de desempilhar um elemento de uma pilha 
IV.A regra 2 pode ser considerada ação de desenfileirar um elemento de uma fila 
Estão corretas apenas as afirmativas: 
Nota: 10.0 
 
A II 
 
B I e III 
 
C I e IV 
 
D II e III 
 
E II e IV 
Você assinalou essa alternativa (E) 
Você acertou! 
Aula 3 - tema4 
 
Questão 8/10 - Estrutura de Dados 
Considere o trecho de código abaixo: 
for i in range(0,n, 1): 
 for i in range(1,n-1, 1): 
 A[i] = B[j] 
Assinale a alternativa correta: 
Nota: 10.0 
 
A a complexidade assintótica (Big-O) é O(n). 
 
B a complexidade assintótica (Big-O) é O(n2). 
Você assinalou essa alternativa (B) 
Você acertou! 
aula 1 – tema5 
 
C a complexidade assintótica (Big-O) é O(2n). 
 
D a complexidade assintótica (Big-O) ) é O(2n + 1). 
a complexidade assintótica (Big-O) ) é O(n(2 + 1)). 
 
Questão 9/10 - Estrutura de Dados 
“Você deve pensar o algoritmo dividir-e-conquistar como tendo três partes: 
1. Dividir o problema em um número de subproblemas que sejam partes menores do mesmo problemas. 
2. Conquistar os subproblemas resolvendo-os recursivamente. Se eles forem pequenos o suficiente, resolva os subproblemas como problemas 
base. 
3. Combinar as soluções dos subproblemas em uma solução para o problema original.” 
 
https://pt.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms 
São exemplos de algoritmo de divisão e conquista: 
Nota: 10.0 
 
A Insertion sort e Bublesort 
 
B Mergesort e Quicksort 
Você assinalou essa alternativa (B) 
Você acertou! 
 Aula 2 – temas1,2 e 4 
 
C Bubblesort e Quicksort 
 
D Selection sort e Bubblesort 
 
E Bubblesort e Mergesort 
 
Questão 10/10 - Estrutura de Dados 
Observe a descrição abaixo: 
• Comparações são feitas entre elementos de um vetor 
• Cada elemento de uma posição i é comparado com o elemento da posição i + 1 
• Se a ordenação procurada é encontrada é feita uma troca de posições entre os elementos 
A descrição em questão se trata do algoritmo de ordenação: 
Nota: 10.0 
 
A 
Mergesort 
 
B Quicksort 
 
C Bubblesort 
Você assinalou essa alternativa (C) 
Você acertou! 
Aula 2 – tema 1 
 
D Hashsort 
 
E Insertion sort