Apol Objetiva 1

Prévia do material em texto

Questão 1/10 - Estrutura de Dados 
Assuma uma lista com 10 dados numéricos e inteiros colocados na seguinte ordem: 
[ 05 , 07 ,08 , 14 , 24 , 29 , 56, 77 , 78 , 88 ] 
Suponha que você deseja implementar um algoritmo de busca para localizar algum dado neste vetor já ordenado de maneira crescente. Você 
resolve testar a busca sequencial e a busca binária. (Adaptada) 
Acerca destes algoritmos e analisando o vetor acima, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A No algoritmo de busca sequencial, o valor 24 seria localizado na 6ª tentativa, se fizermos uma varredura da esquerda para a direita. 
Na 5ª tentativa. 
 
B No algoritmo de busca binária, o valor 24 seria localizado na 3ª tentativa. 
Na 1ª tentativa. 
 
C No algoritmo de busca sequencial, o valor 77 seria localizado mais rapidamente que se comparado com a busca binária. 
Binária se sairia mais rápida. 
 
D No algoritmo de busca sequencial, o valor 07 seria localizado mais rapidamente que se comparado com a busca binária. 
Você assinalou essa alternativa (D) 
Você acertou! 
Levará menos iterações. 
 
Aula1 tema1 
 
E Em nenhum cenário de busca o algoritmo sequencial irá localizar o valor antes da busca binária. 
É possível que sim, a sequencial ache antes. Dependerá o valor buscado e onde ele se localizado no vetor. 
 
Questão 2/10 - Estrutura de Dados 
Considere o Tipo Abstrato de Dados (TAD) da Pilha. Nessa TAD estão implementadas as seguintes operações: 
push(x): inserção do elemento x em uma pilha. 
pop(): remoção do elemento de uma pilha, retornando esse elemento. 
Considere a pilha abaixo, na qual existem quatro valores armazenados. O topo é indicado pelo ponteiro Topo. 
 
 
No estado da pilha acima, foi executada a sequência de instruções abaixo: 
y = 0 
x = pop() 
y = y + x 
x = 6 
push(x) 
x = 8 
push(x) 
x = pop() 
x = pop() 
y = y + x 
Ao final da execução o valor de y será: 
Nota: 10.0 
 
A 8 
 
B 10 
Você assinalou essa alternativa (B) 
Você acertou! 
Aula 3 – tema 3 
 
C 12 
 
D 19 
 
E 15 
 
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 
 
C 11,23,14,25 
Você assinalou essa alternativa (C) 
 
D 14,25 
Aula 3 – tema 4 
 
E 11,14 
 
Questão 4/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 5/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 
Você assinalou essa alternativa (A) 
 
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 
 
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 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 
Considere um vetor ordenado: 
O vetor é dividido ao meio. 
O número do meio é comparado com o número procurado. Se forem iguais a busca termina, senão se o número procurado é menor que o do meio, a busca 
é realizada no subvetor a esquerda, seé maior no subvetor a direita. O procedimento é repetido até que o vetor fique com um elemento ou se encontre o 
desejado. 
 As instruções acima se referem a: 
Nota: 10.0 
 
A Busca (ou Pesquisa) sequencial 
 
B Busca (ou Pesquisa) Linear 
 
C Busca (ou Pesquisa) Binaria 
Você assinalou essa alternativa (C) 
Você acertou! 
Aula 1 - Tema 1 
 
D Ordenação por troca 
 
E Ordenação por seleção 
 
Questão 8/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 enfileirar um 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: 0.0Você não pontuou essa questão 
 
A II 
Você assinalou essa alternativa (A) 
 
B I e III 
 
C I e IV 
 
D II e III 
 
E II e IV 
Aula 3 - tema4 
 
Questão 9/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 10/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: 0.0Você não pontuou essa questão 
 
A Insertion sort e Bublesort 
Você assinalou essa alternativa (A) 
 
B Mergesort e Quicksort 
 Aula 2 – temas1,2 e 4 
 
C Bubblesort e Quicksort 
 
D Selection sort e Bubblesort 
 
E Bubblesort e Mergesort