ESTRUTURA DE DADOS ATIVIDADE 2

Prévia do material em texto

1. 
Um algoritmo é uma sequência de passos que resolve algum problema ou alcança algum objetivo. 
E uma estrutura de dados definem como as informações serão organizadas na memória. Existem 
métodos ordenação que reduz o uso de memória e outros que aumentam o volume de memória 
utilizado. Sendo assim, analise a alternativa do método que possui como desvantagem um gasto 
extra de espaço de memória. 
RESPOSTA: 
. Merge Sort. 
 
2. 
Algoritmos de ordenação são exemplos de algoritmos desenvolvido para solucionar de forma 
mais rápida e eficiente alguns problemas com o auxílio de um computador. Existem diversos 
métodos que podem ser utilizados, cada método tem procedimentos distintos para resolver uma 
determinada tarefa. Assinale a alternativa a seguir que pode ser considerados métodos de 
ordenação? 
RESPOSTA: 
. bubble sort, selection sort, merge sort, quick sort. 
 
3. 
O algoritmo Merge-Sort, faz o uso da estratégia dividir para conquistar. Assim, sua ideia é dividir 
o conjunto de dados em subconjuntos, reorganiza cada subconjunto e depois intercala os 
resultados. De acordo com o método descrito, assinale a alternativa que descreva a complexidade 
do algoritmo no melhor caso e no pior caso. 
RESPOSTA: 
Melhor caso: O (n log n) Pior caso: O (n log n). 
 
4. 
O método de ordenação Insertion Sort, também conhecido como método de inserção, é 
classificado como um método simples. O funcionamento do método é percorrer os elementos e 
à medida que avança vai ordenando. Utilize esse algoritmo para organizar em ordem crescente 
um array unidimensional, contendo os números [5,3,8,2,6]. 
Assinale a alternativa a seguir que apresente a quantidade de trocas que serão realizados para 
ordenar o array utilizando o algoritmo Insertion Sort. 
RESPOSTA: 
.5 trocas. 
 
5. 
O método de ordenação Bubble Sort, também conhecido como método bolha, é classificado 
como um método simples e também um dos métodos mais utilizados. Utilize esse algoritmo para 
ordenar um array unidimensional, contendo os números [6,5,0,3,2] em ordem crescente. 
Assinale a alternativa a seguir que apresente a quantidade de comparações e trocas que serão 
realizados para ordenar o array utilizando o algoritmo Bubble Sort. 
RESPOSTA: 
.10 comparações e 8 trocas. 
 
6. 
A complexidade de um algoritmo se dá por meio das funções que são implementadas no código. 
Cada laço de repetição aumenta o tempo de execução da aplicação. Assinale a complexidade do 
melhor caso do algoritmo de ordenação Bubble Sort. 
RESPOSTA: 
. O(n). 
 
7. 
As estruturas de dados são aplicadas aos algoritmos para melhorar o tempo de execução nas 
aplicações. Cada método de ordenação possui um conceito e uma forma de manipular os dados. 
O método utilizado no algoritmo abaixo é eficiente para resolver problemas com poucos dados e 
a sua complexidade é O (n) no melhor caso e O (n 2) no pior caso. Analise o código abaixo sobre 
o método de ordenação citado acima. 
 
Qual a alternativa que corresponde aos conceitos de ordenação descritos acima e ao código na 
imagem representam o algoritmo de ordenação: 
RESPOSTA: 
. Insertion Sort. 
 
8. 
A tarefa de obter uma expressão matemática para avaliar o tempo de execução de um algoritmo 
não é simples, mesmo considerando-se uma expressão aproximada (SZWARCFITER, Jayme Luiz; 
MARKENZON, Lilian. Estruturas de Dados e seus Algoritmos. 3. ed. Rio de Janeiro: Ltc, 2010). As 
expressões são representadas por meio de funções, no qual podemos descobrir a complexidade 
do algoritmo. Desta forma, analise as afirmativas abaixo. 
 
I. O algoritmo Bubble Sort não é um algoritmo estável. 
II. O algoritmo Bublle Sort, possui complexidade O (n) para o melhor caso e O (n2) para o pior caso. 
III. O algoritmo Quick Sort possui complexidade O (n log (n)) para o melhor caso. 
IV. O algoritmo Quick Sort é um algoritmo estável. 
Julgue e assinale se as afirmativas acima são verdadeiras (V) ou falsas (F). 
RESPOSTA: 
F, V, V, F. 
 
9. 
O método de ordenação Quick Sort, é classificado como um método complexo e não estável. 
Nesse algoritmo se faz necessária a escolha de um elemento como pivô. Utilize esse algoritmo 
para ordenar um array unidimensional, contendo os números [5,2,9,6,3] em ordem crescente. 
Considere o número 9 e, na sequência, o número 3 como pivô. 
Assinale a alternativa a seguir que apresente a quantidade de trocas que serão realizados para 
ordenar o array utilizando o algoritmo Quick Sort. 
RESPOSTA: 
. 3 trocas. 
 
10. 
A complexidade de um algoritmo é calculada por meio da complexidade temporal e espacial, 
sendo na primeira o cálculo do tempo que as instruções levam para serem executadas em uma 
aplicação (utilizando as funções), e na sequência, o espaço na memória que o algoritmo utiliza 
enquanto é executado. Existem algoritmos que necessitam de muito mais espaço, como o 
Algoritmo _____________. Assinale a alternativa que complete o nome de algoritmo que exige 
mais espaço na memória. 
RESPOSTA: 
. Merge Sort.