Questão EPO - Heap sort

Árvore-Heap a partir do Arquivo
Arquivo Original por Níveis

Como ficaria a arvore heap resultante??

a) 48,5,15,1,19,11,59,77,26
b) 61,1,15,48,19,11,59,77,26
c) 77,61,59,48,26,19,11,15,1,5
d) 77,61,59,48,26,19,15,11,1,5
e) NDA

Fonte:
http://www.inf.ufsc.br/~ine5384-hp/Estruturas.Quick.html

Questão EPO - Bubble sort

O algoritmo Bubble Sort é um dos algoritmos mais simples e efetua a ordenação de n elementos. O algoritmo consiste na passagem por um conjunto de tamanho n, n vezes e a cada passagem, fazemos a verificação de todos os seus itens em pares. Se o valor de numero[i] for maior do que numero[i + 1], efetuamos a troca dos valores. No final o vetor esta ordenado.

Exercio utilizando o vetor [4, 9, 5, 0, 2] de entrada:
Para cada elemento à direita do maior, vamos invertendo suas posições para que assim o  maior chegue ao final
Inicio :4 9 5 0 2
Final  :_ _ _ _ _
Como ficaria os elementos no final do bubble sort?

a) 0 2 9 5 4
b) 0 9 5 4 2
c) 0 2 4 9 5
d) 0 2 4 5 9
e) NDA

Fonte:
http://kleberandrade.wordpress.com/2010/01/19/c-algoritmo-de-ordenacao-bolha-bubble-sort/

Questão EPO - Hash Table

Chave de Busca pertence a qual estrutura de dados??

a) Quick sort
b) Merge sort
c) Heap sort
d) Hash table
e) NDA

Questão EPO - Linked List

Dado a Lista encadeada:
Struct  no {
    Int cod;
    Struct    no    *prox;
};
Struct no *Lista = NULL, // 1)________________________
    *Fim = NULL,  // 2)________________________
    *exc = NULL,  // 3)________________________
    *ant = NULL,  // 4)________________________
    *p = NULL,    //  5)________________________
Int   tam  = 0 , x;

Qual alternativa preenche os comentarios corretamente:

a)
    1. Aponta para o inicio da lista
    2. Aponta para o fim da lista
    3. Aponta para o no a ser excluído
    4. Aponta para o no anterior
    5. Aponta para o no criado

b)
    1. Aponta para o fim da lista
    2. Aponta para o inicio da lista
    3. Aponta para o no a ser excluído
    4. Aponta para o no anterior
    5. Aponta para o no criado

c)
    1. Aponta para o no a ser excluido
    2. Aponta para o começo da lista
    3. Aponta para o fim da lista
    4. Aponta para o no anterior
    5. Aponta para o no criado

d)
      
    1. Aponta para o no a ser excluido
    2. Aponta para o começo da lista
    3. Aponta para o no criado
    4. Aponta para o no anterior
    5. Aponta para o fim da lista

e)
    NDA

Fonte:
http://www.brasilacademico.com/apostilas/ED_07_Lista_Simples_Fechada_ex.pdf

Questão EPO - Merge sort

MergeSort(i,f)

    Dado um vetor A[i..f] de inteiros
    Devolve A com os elementos em ordem crescente.

{
 1    se (i-f > 0) então {
 2        m <- (i+f) div 2;
 3        MergeSort(i,m);
 4        MergeSort(m,f);
 5        para k de 1 até m-i+1 faça
 6            b[k] <- A[i+k-1];
 7        para l de m+1 até f faça
 8            c[l-m] <- A[l];
 9        k <- 1;
10        l <- 1;
11        b[m+1] <-  ∞;
12        c[f-m+1] <- ∞;
13        para r de i até f faça
14            se ( b[k] < c[l] ) { A[r] <- b[k]; k <- k+1;}
15            senão {A[r] <- c[l]; l <- l+1;}
    }
}

O número de comparações entre elementos do vetor A feitas por uma chamada de MergeSort(1,n),n>1 , é o número de comparações feitas recursivamente nas chamadas das linhas 3 e 4 mais o número de compações feitas na linha 14 ( pois o resultado de cada comparação determina um elemento de A), logo
Complete o tracejado:

a) 1 , 2
b) 3 , 4
c) 3 , 5
d) 5 , 7
e) NDA

Fonte:
http://anotacoesdeaula.wordpress.com/2011/02/10/bc1435-mergesort-solucao-exata-da-recorrencia/

Questão EPO - Quicksort

Quais dos seguintes algoritmos de ordenação são instáveis?

I. BubbleSort (ordenação por bolha);
II. InsertionSort (ordenção por inserção);
III. Merge sort;
IV. Quick sort;

a) Somente II.
b) Somente I e II.
c) Somente I, II e III.
d) Somente IV
e) NDA

Fonte:
http://www.allgoritmos.com/2009/08/poscomp-2005-q33-algoritmos-de.html