Algoritmos de Ordenação Eficiente

Exercício 1

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

  • <50, 25, 30, 27, 24, 21, 28>
  • <50, 30, 25, 27, 24, 28, 21>
  • <60, 50, 9, 40, 41, 10, 8>
  • <40, 15, 18, 13, 11, 14, 16>
  • <60, 30, 80, 10, 35, 70, 40>

Exercício 2

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>.

  • Indique o conteúdo do vector após o passo de transformação num amontoado.
  • Indique 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).

Exercício 3

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?

Exercício 4

  • (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?

Exercício 5

  • (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?

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.

Ponteiros e Alocação Dinâmica de Memória

Exercício 6

Implemente um programa em C que leia uma palavra do standard input e que imprima todos os sufixos dessa palavra. O programa deverá imprimir um sufixo por linha começando do mais comprido para o menos comprido.

Por exemplo, para o input abc o output deve ser:

abc
bc
c

Poderá supor que a palavra nunca terá mais de 1000 caracteres.

Dica: Sugere-se utilização de aritmética de ponteiros, para poder avançar com um ponteiro p representando os diferentes sufixos e passar esse ponteiro p como parâmetro para a função printf.

Exercício 7

Implemente um programa em C que leia uma sequência de palavras do standard input e imprima as mesmas na ordem inversa. O programa deverá imprimir uma palavra por linha começando pela última palavra.

Por exemplo, para o input abcd foo bar o output deve ser:

bar
foo
abcd

Poderá supor que a palavra nunca terá mais de 1000 caracteres, que não aparacem mais que 10000 palavras e que cada palavra pode ser lida com scanf("%s", s).

Dica: Guarde as palavras como um vector de strings. Primeiro leia a palavra dentro de uma string com um tamanho fixo e só depois aloca a string com o tamanho adequado.

Dica: A chamada scanf("%s", buffer) devolve 1 se e só se a palavra foi lida com sucesso, i.e. a leitura pode terminar se o valor devolvido não estiver 1.