Algoritmos e Estrutura de Dados I - AE22CP - 2012/2
Bruno César Ribas

Exercícios

  1. O que é Algoritmo?

Inserção

  1. Implemente o Algoritmo de Ordenação por Inserção

  2. Escreva uma versão recursiva do algoritmo de ordenação por inserção.

  3. Na função insercao, troque a comparação "v[i] > x" por "v[i] >= x". A nova função continua produzindo uma ordenação crescente de v[0..n-1]?

  4. Que acontece se trocarmos "for (j = 1" por "for (j = 0" no código da função insercao?

  5. Que acontece se trocarmos "v[i+1] = x" por "v[i] = x" no código da função insercao?

  6. O papel do for interno na função insercao é encontrar o ponto onde v[j] deve ser inserido em v[0..j-1]. Considere fazer isso com uma busca binária. Analise o resultado.

  7. Escreva uma função que permute os elementos de um vetor inteiro v[0..n-1] de modo que eles fiquem em ordem decrescente.

  8. Escreva uma função que coloque em ordem lexicográfica um vetor de strings. Use o algoritmo de inserção.

Merge

  1. Implemente o algoritmo da Intercalação (merge)

  2. Resolva a questão 3 da Prova Substitutiva da Segunda prova de 2012-1

  3. Escreva uma função que receba vetores disjuntos x[0..m-1] e y[0..n-1], ambos em ordem crescente, e produza um vetor z[0..m+n-1] que contenha o resultado da intercalação dos dois vetores dados. (É claro que z estará em ordem crescente). Escreva duas versões da função: uma iterativa e uma recursiva.

  4. Um algoritmo de intercalação é estável se não altera a posição relativa de elementos iguais. A função intercala1 discutida acima é estável? E se a comparação "v[i] <= v[j]" for trocada por "v[i] < v[j]"?

  5. Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas): 
         i = p; j = q; k = 0;
     while (i < q && j < r) {
        if (v[i] <= v[j])  w[k++] = v[i++];
        if (v[i] > v[j]) w[k++] = v[j++];
     }
     while (i < q)  w[k++] = v[i++];
     while (j < r)  w[k++] = v[j++];
     for (i = p; i < r; ++i)  v[i] = w[i-p];

  6. Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas): 
         i = p; j = q; k = 0;
     while (i < q && j < r) {
        if (v[i] <= v[j])  w[k++] = v[i++];
        else  w[k++] = v[j++];
     }
     while (i < q)  w[k++] = v[i++];
     for (i = p; i < j; ++i)  v[i] = w[i-p];

  7. Analise e discuta a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas): 
         i = p; j = q;
     for (k = 0; k < r-p; ++k) {
        if (j >= r || (i < q && v[i] <= v[j])) 
           w[k] = v[i++];
        else 
           w[k] = v[j++]; 
     }
     for (i = p; i < r; ++i)  v[i] = w[i-p];

  8. Critique a seguinte alternativa para a função intercala1 (a alocação e liberação de memória foram omitidas): 
         i = p; j = q; k = 0;
     while (k < r-p) {
        while (i < q && v[i] <= v[j]) 
           w[k++] = v[i++];
        while (j < r && v[j] <= v[i]) 
           w[k++] = v[j++];
     }
     for (i = p; i < r; ++i)  v[i] = w[i-p];