Exercícios 1 Estrutura de Dados 100

Prévia do material em texto

Questão 1/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 2/10 - Estrutura de Dados
Observe o algoritmo abaixo:
def busca(x:list,alvo: int):
    n = len(x)
    for i in range(0, n, 1):
        if n[i] == alvo:
            return i
      #asserção: todos os elementos foram testados e alvo não foi encontrado.
    return -1
Koffman, Elliot, B. e Paul A. T. Wolfgang. Objetos, Abstração, Estrutura de Dados e Projeto Usando C++. Disponível em: Minha Biblioteca, Grupo GEN, 2008.Modificado
Quanto ao algoritmo acima é correto afirmar:
	
	A
	A complexidade assintótica é O(n).
Você assinalou essa alternativa (A)
	
	B
	A complexidade assintótica é O(i).
	
	C
	A complexidade assintótica é O(alvo).
	
	D
	A complexidade assintótica é O(n+1).
	
	E
	A complexidade assintótica é O(1).
Questão 3/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 4/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:
	
	A
	Insertion sort e Bublesort
	
	B
	Mergesort e Quicksort
Você assinalou essa alternativa (B)
	
	C
	Bubblesort e Quicksort
	
	D
	Selection sort e Bubblesort
	
	E
	Bubblesort e Mergesort
Questão 5/10 - Estrutura de Dados
Considere a estrutura de dados do tipo Pilha abaixo.  Nessa pilha  existem quatro valores armazenados. O topo é indicado pelo ponteiro Topo da pilha.
A inserção em uma pilha é chamada de empilhar, ou em inglês, push.
A remoção em uma pilha é desempilhar ou pop.
 
Após realizar as seguintes operações, de cima para baixo:
pop
pop
pop
push  4
push  5
push 3
pop
push 4
A pilha irá conter os valores, do topo para baixo:
	
	A
	2,4,5,4
	
	B
	3,5,4,2
	
	C
	2,4,3,5,4,5,4
	
	D
	4,5,4,2
Você assinalou essa alternativa (D)
	
	E
	4,3,5,4
Questão 6/10 - Estrutura de Dados
No terceiro assunto de nossa disciplina estudamos uma nova estrutura de dados denominada de LISTA ENCADEADA. (Adaptada)
Acerca de listas encadeadas, assinale a alternativa CORRETA:
	
	A
	Uma lista encadeada trabalha com alocação sequencial na memória. De maneira similar a uma estrutura de dados do tipo vetor.
	
	B
	Uma lista encadeada trabalha com o conceito de índice. Ou seja, podemos acessar qualquer posição da lista usando o seu índice como referência.
	
	C
	O acesso a qualquer dado em uma lista pode ser feito com a mesma eficiência em tempo de execução, caracterizando uma complexidade de acesso aos dados como O(1).
	
	D
	Cada elemento da lista encadeada armazena na memória não só seus dados, mas também o endereço de onde está localizado o próximo elemento na memória.  
Você assinalou essa alternativa (D)
	
	E
	Cada elemento de uma lista encadeada só poderá armazenar dados do tipo numérico. Não é permitido o uso de dados do tipo caractere ou lógico, por exemplo.
 
Questão 7/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 8/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?
	
	A
	Heapsort
	
	B
	Mergesort
	
	C
	Quicksort
	
	D
	Bubble sort
Você assinalou essa alternativa (D)
	
	E
	Insertion sort
Questão 9/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 filaIII.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 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:
	
	A
	Mergesort
	
	B
	Quicksort
	
	C
	Bubblesort
Você assinalou essa alternativa (C)
	
	D
	Hashsort
	
	E
	Insertion sort
image1.png