Questão EPO - Quicksort

O algoritmo de ordenação Quicksort é considerado um dos mais rápidos e eficientes. Sabendo que sua estratégia consiste em ordenar de forma que valores menores precedam maiores, indique qual nome dessa estratégia, complexidade de tempo no pior caso, caso médio e melhor caso respectivamente:

a) Divisão e Conquista;    O(n2) ;   O(nlogn) ;   O(nlogn)
b) Divisão e Conquista;   O(nlog) ;   O(nlogn) ;   O(n2)
c) Dividir, Comparar e Combinar;   O(nlog) ;   O(nlogn) ;   O(n2)
d) Dividir, Conquistar e Combinar;   O(n2) ;   O(nlogn) ;   O(nlogn)
e) N.D.A.

Referência: http://pt.wikipedia.org/wiki/Quicksort

Questão EPO - Hash Table

Um caso inevitável ocorre com Hash Tables, assumindo que as chaves no array não sejam fixas, é no jargão profissional ou termo técnico chamado de:

a) Impact;
b) Key impairing;
c) Collision;
d) Vector impairing
e) N.D.A.

Referência: http://pt.wikipedia.org/wiki/Tabela_de_dispers%C3%A3o

Questão EPO - Linked List

Assinale V(Verdadeiro) e F(Falso) sobre as afirmações abaixo de lista encadeada e marque uma alternativa correta :

(  ) Para cada novo elemento inserido na estrutura, alocamos um espaço na memória para armazená-lo .
(  ) O último elemento da lista aponta para NULL, sinalizando que não existe um próximo elemento.
(  ) O espaço total de memória gasto pela estrutura é proporcional ao número de elementos nela armazenado com acesso direto aos elementos da lista.
(  ) A inserção ou remoção de um elemento na lista não implica a mudança de lugar de outros elementos;
(  ) Uma lista encadeada simples é aquela que contém apenas dois  links por nodo. Estes links apontam para o próximo nodo da lista e primeiro nodo, ou para um valor nulo (vazio) quando se trata do nodo final.

a) V F V V V
b) V VV V F
c) V F V F F
d) V V F V F
e) N.D.A.

Referências:
Slide da apresentação do grupo do Gian;
http://pt.wikipedia.org/wiki/Lista_ligada;
http://pt.wikiversity.org/wiki/Estruturas_de_Dados_Intermedi%C3%A1rio/Lista_encadeada.

Questão EPO - Recursividade

Sabe-se que a sequência de Fibonacci é desenvolvida da seguinte forma: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... , ou seja, soma-se o número por seu antecessor (1+2)= 3, (2+3)= 5, (3+5)= 8 e assim por diante.
De acordo com as informações acima, analise o programa abaixo e indique o código recursivo que satisfaz a lógica de Fibonacci.

#include <stdio.h>
#include <conio.h>

main() {
    int n,i;
    printf("Digite a quantidade de termos da sequencia de Fibonacci: ");
    scanf("%d", &n);
    printf("\nA sequencia de Fibonacci e: \n");
    for(i=0; i<n; i++)
        printf("%d ", fibonacci(i+1)); //Aqui chama a função fibonacci
    getch();
}

int fibonacci(int num) {
    //Código Recursivo
}


a) if(num==1 || num==2)  {    return 1;  }
    else { return fibonacci(num-1) + fibonacci(num-2);}

b) if(num==1 || num==2){        return 1; }
    else{ return fibonacci(num) + fibonacci(num-1);}

c) if(num==1){    return 1; }
    else{ return fibonacci(num+ num-1);}

d) if(num==1){    return 1; }
    else{ return fibonacci(num-2 + num-1);}

e)  NDA.

Fonte:
Questão desenvolvida com meus conhecimentos e com o código desde link:
http://www.vivaolinux.com.br/dica/Serie-de-Fibonacci-usando-recursividade-em-linguagem-C

Questão EPO - Merge sort

Uma fábrica de software foi contratada para desenvolver um produto de análise de riscos. Em determinada funcionalidade desse software, é necessário realizar a ordenação de um conjunto formado por muitos números inteiros. Que algoritmo de ordenação oferece melhor complexidade de tempo (Big O notation) no pior caso?

a) Merge sort
b) Heap sort
c) Bubble sort
d) Quick sort
e) N.D.A.

Referência:
http://www.questoesdeconcursos.com/pesquisar/disciplina/algoritmos-e-estrutura-de-dados?di=98&page=55&pp=

Questão EPO - Heap sort

Das afirmações abaixo, assinale a alternativa correta sobre heapsort:

I. Todo nó filho é menor ou igual ao seu nó pai.
II. Sua  ideia é linearizar a árvore por níveis.
III. Não necessita de nenhuma memória adicional.
IV. É uma estrutura de dados baseada em árvores binárias.
V. Executa sempre em tempo proporcional a n log (n*2+1), onde o cálculo do pai é (i) = (i - 1)/2 e do filho da esquerda é (i) = i * 2 + 1.

a) Apenas as afirmações I, II e IV estão corretas.
b) Apenas as afirmações I e IV estão corretas.
c) Todas as alternativas estão corretas exceto a III.
d) Todas as alternativas estão corretas exceto a V.
e) N.D.A.

Fonte:
Esta questão foi desenvolvida de acordo com o slide de apresentação e com o slide:
http://homepages.dcc.ufmg.br/~rfortes/aeds/2/slides/heapsort.pdf

Questão EPO - Bubble sort

Analise as afirmações abaixo e assinale a alternativa correta sobre bubble sort comum:

I. Percorre o array em uma direção apenas.
II. A ideia é percorrer o vetor diversas vezes durante o processo de ordenação.
III. É melhor utilizado em vetores com poucos elementos, pois é lento quando utilizado com muitos valores.
IV. O procedimento termina quando, em uma dada varredura pelo vetor, apenas uma troca de chaves ocorre.

a) Todas estão corretas exceto a IV.
b) Todas estão corretas.
c) Apenas a I e a III estão corretas.
d) Apenas a II é incorreta.
e) N.D.A.

Questão EPO - Struct

Analise o código abaixo:

#include <stdio.h>
#include <conio.h>
 main ()
 {
 struct z
 {
 int a;
 int b;
 int x;
 };
 struct z x,y;
 x.a = 10;
 x.b = 20;
 x.x = 1;
 y = x;
 printf("%d , %d  , %d e %d", y.a, y.b, z.x, x.x);
 
 getch ();
 }

O código apresentado contém erros porque:

a) Ele não contém erros;
b) Porque z não é uma variável;
c) Porque x não possui valor para z, pois x é um atributo da Struct;
d) Porque x não aceita um atributo com o mesmo nome;
e) N.D.A

Questão EPO - Ponteiro

Qual será a saída do seguinte programa?

#include <stdio.h>

int main ()

{

    int i = 3;

    int *j;

    int **k;

    j = &i;

    k = &j;

    printf("%u %u %u",i,j,k);

    getch();

}

a)  3, endereço de j, endereço de j;
b)  3,3,3;
c)  Erro de compilação;
d)  3, endereço de j, endereço de k;
e)  N.D.A.

Referência:
http://translate.google.com.br/translate?hl=pt-BR&langpair=en|pt&u=http://cquestionbank.blogspot.com/2009/09/multiple-choice-questions-in-c.html

Questão EPO - Pilha

Considere o seguinte programa:

#include < stdio.h>
#define TAM 8
typedef struct _PILHA

{
    int pilha [TAM ];
    int topo ;
} PILHA ;

void inserePilha ( int valor , PILHA *p)
{
    Inserir dois comandos aqui
}

int main (void)
{
    PILHA p;
    p. topo = -1;
    inserePilha (10 , &p);
    inserePilha (20 , &p);
    printf ("%d %d\n", p. pilha [0] , p. pilha [1]);

getch();
}

Quais dois comandos devem ser incluídos no trecho indicado na listagem para que os valores 10 e 20 sejam impressos pelo programa?

a) p->topo++; p->pilha[p->topo] = valor;
b) p->pilha[p->topo] = valor; p->topo++;
c) p.topo++; p.pilha[p.topo] = valor;
d) pilha[topo] = valor; topo++;
e) NDA

Referência:
http://equipe.nce.ufrj.br/adriano/c/provas/p20062/p2/p2vermelha.pdf
Página 4 – Questão 6.

Questão EPO - Estrutura de Dados

Dos objetivos específicos das EDs:

I. Consolidar os conhecimentos sobre programação previamente adquiridos;
II. Fornecer domínio da alocação dinâmica de memória;
III. Utilização otimizada das diversas estruturas de dados;
IV. Introduzir aspectos básicos de programação para a criação de algoritmos abstratos;

Qual não faz parte?

a) I
b) II
c) III
d) IV
e) NDA

Referência:
http://www.univasf.edu.br/~marcelo.linder/arquivos_ed1/aulas/aula1.pdf
SLIDE 4 - Estrutura de Dados

Questão EPO - Fila

Sobre fila:

I. Os dados são armazenados pela ordem de entrada;
II. A operação dequeue é usada para retirar um elemento, removendo-o do fim.
III. Na fila “o primeiro que entra é o primeiro que sai”(first in, first out);
IV. Só podemos retirar o elemento do início.

Das características acima quais estão corretas?

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

Fonte: Slide do professor sobre FILA foi usado como referência.

Questão EPO - Árvore Binária

Sobre a árvore apresentada abaixo pode-se afirmar:

a) Esta é uma árvore estritamente binária completa
b) Esta é uma árvore estritamente binária extendida
c) Esta é uma árvore binária contida
d) Esta é uma árvore binária quase completa
e) NDA

Questão EPO - Árvore Binária

Sobre Árvore Binária:

I. Um conjunto de nós com a mesma profundidade é denominado nível.
II. A profundidade de um nó é a distância deste nó até a raiz.
III. Uma árvore binária é estritamente binária quando esta possui sub-árvores esquerda e direita não-vazias.
IV. Uma árvore binária é completa quando todos os pais possuem pelo menos um filho.

Qual das características acima não é correspondente?

A) I
B) II
C) III
D) IV
E) NDA

Referência: http://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria

Questão EPO - Alocação Dinâmica

Das principais características da alocação dinâmica abaixo especificadas:

I. Os dados se encontram espalhados na memória do computador em vários blocos;

II. Podemos ir solicitando mais e mais memória a medida em que precisarmos de mais espaço para armazenar as informações.

III. Podemos liberar espaços de memória quando estes não forem mais necessários ao programa.

IV.  O ponteiro ajuda a localizar os registros alocados, o que nos permite encadear os dados e indicar onde está o dado seguinte na memória.

V. Permite criar programas que usam apenas a memória necessária.

Qual ou quais NÃO se aplica(m)?

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

Referência:
http://osorio.wait4.org/oldsite/alg-ed/aula04.pdf
Página 2 – Sobre as características da alocação dinâmica.