Exercícios

1) Considere o seguinte vector v = <6, 3, 4, 2, 5, 1>. Indique o conteúdo de v no final de cada passo dos algoritmos insertion sort e selection sort.


2) Considere o seguinte vector v = <12, 2, 18, 15, 16, -1, 35, 30, 15>. Indique as razões porque é que o vector <-1, 2, 12, 15, 18, 15, 16, 30, 35> não pode corresponder ao conteúdo de v num passo intermédio da aplicação dos algoritmos insertion sort, selection sort ou merge sort?


3) Considere a aplicação do algoritmo bubblesort ao vector <20, 11, 16, 9, 12, 14, 17, 19, 13, 15>. Supondo que o algoritmo percorre o vector da esquerda para a direita em cada iteração, qual o conteúdo do vector após as duas primeiras iterações do algoritmo bubblesort ?


4) Diga quais dos seguintes vectores corresponde a um amontoado (heap)? 

a. <50, 25, 30, 27, 24, 21, 28> 
b. <50, 30, 25, 27, 24, 28, 21> 
c. <60, 50, 9, 40, 41, 10, 8> 
d. <40, 15, 18, 13, 11, 14, 16> 
e.  <60, 30, 80, 10, 35, 70, 40>


5) A primeira operação do algoritmo heapsort é transformar o vector num amontoado. Considere que o vector de entrada do algoritmo é <20, 11, 16, 9, 12, 14, 17, 19, 13, 15>.
      5.1.Indique o conteúdo do vector após o passo de transformação num amontoado.
      5.2. Indique ainda o conteúdo do vector após os dois maiores elementos terem sido ordenados (colocados na sua posição final), durante a operação de ordenação (heapsort).


6) Qual o conteúdo do seguinte vector <25, 19, 23, 15, 18, 16, 21, 12> depois de os dois primeiros elementos (i.e. os dois maiores) terem sido ordenados, utilizando o algoritmo de ordenação heapsort?


7) Considere a implementação clássica da função int partition (Item v[], int l, int r) usada no algoritmo quicksort tal como apresentada nas aulas teóricas. Esta função recebe o vector v e as posições l e r que definem, respectivamente, os índices limite esquerdo e direito do vector a considerar na função. Suponha que o procedimento partition é invocado com os seguintes argumentos: v = <13, 6, 5, 14, 12, 4, 16, 18, 7, 9, 10>, l = 0, r = 10.  Considerando a posição a[r] como pivot, indique qual o conteúdo do vector v após a execução da função partition.


8) Considere o exercício anterior, mas onde os argumentos da função partition são os seguintes: v =<20, 11, 16, 9, 12, 14, 17, 19, 13, 15> , l = 0 , r = 9. Qual o conteúdo do vector v após a execução do procedimento partition?


9) (Radix LSD) Considere a aplicação do algoritmo radix sort LSD, em que cada passo os elementos são ordenados considerando um dígito, ao seguinte vector:

<48372, 62309, 83861, 91874, 18913, 33829, 47812, 95954, 52377, 22394, 56108, 60991>

Qual é o terceiro número da sequência, após o algoritmo ter considerado três digitos?


10) (Radix MSD) Considere o seguinte vector de números inteiros sem sinal de 6 bits:

<32, 2, 34, 9, 6, 1, 20, 18, 10>. Qual o conteúdo do vector após os primeiros dois passos do algoritmo de

ordenação radix sort MSD, em que em cada passo os elementos são ordenados considerando 2 bits (ou seja, byte = 2 bits) ?

Nota: considere que o algoritmo é baseado numa versão estável do algoritmo counting sort. O algoritmo deve apenas processar os 6 bits menos significativos de cada número, independentemente dos números poderem ser guardados em palavras com maior número de bits.

Sugestão de resolução

1) R: Ver aulas teóricas.

2) 

3) R: 11, 9, 12, 14, 16, 17, 13, 15, 19, 20

4) R: Ver aulas teóricas.

5) 

5.1. : <20, 19, 17, 13, 15, 14, 16, 9, 11, 12> 

5.2. : <17, 15, 16, 13, 12, 14, 11, 9, 19, 20> 

6) R: <21, 19, 16, 15, 18, 12, 23, 25>

7) R: <9, 6, 5, 7, 4, 10, 16, 18, 14, 13, 12>

8)  R: <13, 11, 14, 9, 12, 15, 17, 19, 20, 16> 

9) R: ver exercícios das aulas teóricas

10) R: ver "Binary MSD" discutido na aula teórica. Adapte o exemplo dado para 2 bits.