Métodos de Ordenação e Algoritmos

Prévia do material em texto

Questão 1/10 - Estrutura de Dados 
Os métodos de ordenação são algoritmos muito utilizados quando é necessário que os dados de uma lista de 
valores, originalmente desordenada, sejam recuperados de maneira ágil e facilitada. Entre os métodos de 
ordenação eficientes, alguns dos mais conhecidos são aqueles que utilizam a estratégia da divisão e 
conquista, na qual um problema deve ser dividido em vários problemas menores, que serão solucionados até 
que o problema maior possa ser completamente resolvido. 
Vetorazzo, Adriana de, S. et al. Estrutura de dados. Disponível em: Minha Biblioteca, Grupo A, 2018.pag43 
(modificado) 
Considerando o texto base e o conteúdo aprendido em aula são feitas as seguintes afirmações: 
I. São exemplos de algoritmos de divisão e conquista o Merge sort e o Quicksort. 
II. O Bubble sort é também conhecido como algoritmo de ordenação por intercalação. 
III. O Quick sort define um elemento chamado pivô para se iniciar as comparações. 
 
 
 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. 
 
Questão 2/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 3/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 4/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, o valor 07 seria localizado mais rapidamente que 
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 5/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 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 maiorelemento, 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 
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 10/10 - Estrutura de Dados 
O algoritmo de ordenação pelo método da bolha (bubble sort ) foi utilizado para ordenar a sequência 43, 6, 
32, 15, 21 de forma crescente. 
Quantas trocas foram realizadas? 
 
A 2 
 
B 3 
 
C 4 
 
D 5 
 
E 6 
Você assinalou essa alternativa (E)