Complexidade e Algoritmos

Prévia do material em texto

Questão 1/10 - Estrutura de Dados
“A complexidade de um algoritmo reflete o esforço computacional requerido para executá-lo. Esse esforço computacional mede a quantidade de trabalho, em termos de tempo de execução ou da quantidade de memória requerida. As principais medidas de complexidade são tempo e espaço, relacionadas a` velocidade e a` quantidade de memória, respectivamente, para a execuçãoo de um algoritmo.”
Toscani, Laira, V. e Paulo A. S. Veloso. Complexidade de Algoritmos - V13 - UFRGS. Disponível em: Minha Biblioteca, Grupo A, 2012.pag 29
Levando em consideração o texto base e o conteúdo visto em aula, temos portanto, dois tipos de complexidade de algoritmos:
	
	A
	Complexidade de execução e  complexidade de memória
	
	B
	Complexidade de tempo e  complexidade de espaço
Você assinalou essa alternativa (B)
	
	C
	Complexidade de tempo e  complexidade de desempenho
	
	D
	Complexidade de esforço e complexidade de espaço
	
	E
	Complexidade de tempo e  complexidade de velocidade 
Questão 2/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:
	
	A
	No algoritmo de busca sequencial, o valor 24 seria localizado na 6ª tentativa, se fizermos uma varredura da esquerda para a direita.
	
	B
	No algoritmo de busca binária, o valor 24 seria localizado na 3ª tentativa.
	
	C
	No algoritmo de busca sequencial, o valor 77 seria localizado mais rapidamente que se comparado com a busca binária.
	
	D
	No algoritmo de busca sequencial, da esquerda para a direta, o valor 07 seria localizado com o mesmo número de tentativas se comparado com a busca binária.
Você assinalou essa alternativa (D)
	
	E
	Em nenhum cenário de busca o algoritmo sequencial irá localizar o valor antes da busca binária.
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á:
	
	A
	25
	
	B
	11,34,23,14,25
	
	C
	11,23,14,25
	
	D
	14,25
Você assinalou essa alternativa (D)
	
	E
	11,14
Questão 4/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:
	
	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)
Questão 5/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:
	
	A
	II
	
	B
	I e III
	
	C
	I e IV
	
	D
	II e III
	
	E
	II e IV
Você assinalou essa alternativa (E)
Questão 6/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:
	
	A
	Busca (ou Pesquisa) sequencial
	
	B
	Busca (ou Pesquisa)  Linear
	
	C
	Busca (ou Pesquisa) Binaria
Você assinalou essa alternativa (C)
	
	D
	Ordenação por troca
	
	E
	Ordenação por seleção
Questão 7/10 - Estrutura de Dados
Considere o algoritmo abaixo:
def bubble_com_flag(dados):
    tam = len(dados 
    for v in range(0, tam, 1): 
        flag = 0
        for i in range(0, tam - 1, 1):
              if dados[i] > dados[i + 1]:
                 aux = dados[i]
                 dados[i] = dados[i + 1]
                 dados[i + 1] = aux
                 flag = 1
        if flag == 0:
            return dados
 
Considere o seguinte conjunto de dados:
dados = [9,5,7,3,1]
Quando v for igual a 1 e após executado o terceiro passo do laço for interno, os elementos em dados terão a seguinte ordem: 
	
	A
	5,7,3,1,9
	
	B
	5,3,1,7,9
Você assinalou essa alternativa (B)
	
	C
	3,1,5,7,9
	
	D
	5,1,3,7,9
	
	E
	5,3,7,1,9
Questão 8/10 - Estrutura de Dados
Considere o algoritmo abaixo:
def algoritmo(dados):
    tam = len(dados)
    for v in range(0, tam, 1): 
        flag = 0
        for i in range(0, tam - 1, 1):
              if dados[i] < dados[i + 1]:
                 aux = dados[i]
                 dados[i] = dados[i + 1]
                 dados[i + 1] = aux
                 flag = 1
        if flag == 0:
            return dados
Após análise do algoritmo acima, assinale a alternativa correta:
	
	A
	O código é um  algoritmo de seleção e ordena em ordem crescente.
	
	B
	O código em questão é de um algoritmo de pesquisa e busca o menor número. 
	
	C
	O código em questão  é de um algoritmo de pesquisa e busca o maior número.
	
	D
	O código em questão é de um algoritmo de ordenação e ordena em ordem crescente.
	
	E
	O código em questão é de um algoritmo de ordenação e ordena em ordem decrescente.
Você assinalou essa alternativa (E)
Questão 9/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 comportamentodo algoritmo que flutua para o topo o maior elemento, pode se afirmar que se trata de qual algoritmo de ordenação?
	
	A
	Heapsort
	
	B
	Mergesort
	
	C
	Quicksort
	
	D
	Bubble sort
Você assinalou essa alternativa (D)
	
	E
	Insertion sort
Questão 10/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:
	
	A
	I somente.
	
	B
	I e II somente.
	
	C
	I e III somente.
Você assinalou essa alternativa (C)
	
	D
	II e III somente
	
	E
	I, II e III.