Questão EPO - Bubble sort

Das afirmativas abaixo sobre o algoritmo de ordenação Bubble Sort, qual está incorreta:

a) O Bubble Sort segue os seguintes passos: primeiro percorre o vetor inteiro, comparando todos os elementos adjacentes (dois a dois), segundo, troca a posição desses dois elementos se eles já não estiverem ordenados, e finalmente repete esses passos acima com os primeiros elementos n-1, depois com os primeiros  n-2 até que reste apenas um item.

b) O Bubble Sort é um método de ordenação com um custo muito alto: ele só é adequado para vetores pequenos, uma vez que o número de operações de trocas (swap) não se altera mesmo que o vetor já esteja ordenado.

c) O Bubble Sort possui uma forma melhorada: termina a execução se nenhuma troca de posições (swap) foi realizada após um percurso completo do vetor

d) Apenas as alternativas a e c estão corretas.

e) N.D.A.

Fonte:
http://www2.dcc.ufmg.br/disciplinas/aeds2_turmaA1/bubblesort.pdf

Questão EPO - Hash Table

Sobre os métodos de pesquisa utilizados pela Hash Table, é correto afirmar que:

a) Uma Hash Table é uma coleção não-ordenada onde os objetos são inseridos e removidos através de uma função de dispersão (hash function) que converte a chave de acesso escolhida para o objeto no índice do vetor, que aponta para a localização desse objeto

b) A busca, nas Hash Tables é otimizada pelo uso de chaves nos objetos das tabelas, que nada mais é que um campo único na tabela, evitando buscas com custo alto.

c) As Hash Tables não possuem elevada rapidez na manipulação de dados, pois se utilizam de métodos de acesso com uso de vetores, muito lentos.

d) Colisão é uma situação em que duas chaves diferentes resultaram pela função de dispersão, no mesmo índice da tabela

e) N.D.A.

Fonte:
http://www.deetc.isel.ipl.pt/programacao/aed/turmas/LI31D/Slides/7-HashTables.pdf

Questão EPO - Heap sort

O algoritmo Heapsort resolve o problema da ordenação de um vetor.  O algoritmo recebe um vetor A[1..n] e rearranja o vetor de modo que ele fique em ordem crescente. Seu funcionamento, em pseudo-código segue esses parâmetros:

Heapsort (A, n)
1    Constrói-Max-Heap (A, n)
2    para  m ← n, n−1, … , 2  faça
3        A[1] ↔ A[m]
4        Corrige-Descendo (A, m−1, 1)

De acordo com o enunciado, escolha a alternativa que descreve cada um dos 4 passos enumerados no código HeapSort acima:

a) 1. . Trecho do código onde é informado a troca (swap) que deve ser efetuada, dentro do que ficou estabelecido no algoritmo, enquanto as condições do laço não atingem seu limite
2. Constrói-Max-Heap transforma o vetor A[1..n] em max-heap.
3. Ordena o vetor. Se A[i] é maior ou igual que seus filhos então não é preciso fazer nada; senão, troque A[i] com o maior dos filhos e repita o processo para o filho envolvido na troca.
4. Laço “do-while” que informa o total de índices (heaps) que irão ser percorridos

b) 1. Constrói-Max-Heap transforma o vetor A[1..n] em max-heap.
2. Laço “do-while” que informa o total de índices (heaps) que irão ser percorridos
3. Trecho do código onde é informado a troca (swap) que deve ser efetuada, dentro do que ficou estabelecido no algoritmo, enquanto as condições do laço não atingem seu limite
4. Ordena o vetor. Se A[i] é maior ou igual que seus filhos então não é preciso fazer nada; senão, troque A[i] com o maior dos filhos e repita o processo para o filho envolvido na troca.

c) 1. Constrói-Max-Heap transforma o vetor A[1..n] em max-heap.
2.  Trecho do código onde é informado a troca (swap) que deve ser efetuada, dentro do que ficou estabelecido no algoritmo, enquanto as condições do laço não atingem seu limite
3. Laço “do-while” que informa o total de índices (heaps) que irão ser percorridos
4. Ordena o vetor. Se A[i] é maior ou igual que seus filhos então não é preciso fazer nada; senão, troque A[i] com o maior dos filhos e repita o processo para o filho envolvido na troca.

d) 1. Constrói-Max-Heap transforma o vetor A[1..n] em max-heap.
2. Ordena o vetor. Se A[i] é maior ou igual que seus filhos então não é preciso fazer nada; senão, troque A[i] com o maior dos filhos e repita o processo para o filho envolvido na troca.
3. Trecho do código onde é informado a troca (swap) que deve ser efetuada enquanto as condições do laço não atingem seu limite
4. Trecho do código onde é informado a troca (swap) que deve ser efetuada, dentro do que ficou estabelecido no algoritmo, enquanto as condições do laço não atingem seu limite

e) N.D.A.

Fonte:
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/hpsrt-pr.html

Questão EPO - Linked List

Listas ligadas (Linked Lists) é uma estrutura de dados onde os objetos são arranjados em ordem linear, ordem esta estabelecida pela ligação (links) dos elementos da lista, sendo que cada nó da lista armazena um elemento e uma referência para o próximo nó da lista.

Tendo em vista essa definição, qual das alternativas não estabelece diferenças entre uma Linked List e um vetor (array)

a) Lista é uma seqüência de tamanho arbitrário e dinâmico de elementos de algum tipo base, ao contrário do vetor que possui tamanho fixo
b) Lista se utiliza de um tamanho necessário para si, ao contrário do vetor que pode se utilizar de um tamanho maior do que realmente precisa
c) A ordem das listas é determinada por um índice e o dos vetores por um ponteiro
d) Listas são um tipo abstrato de dados fundamentais enquanto os vetores possuem um tipo primitivo fixo de dados
e) N.D.A.

Fonte:
http://dsc.ufcg.edu.br/~adalberto/disciplinas/aulas/Lista%20Encadeada.pdf

Questão EPO - Merge sort

O Merge Sort é um algoritmo de ordenação que se utiliza de recursão para ordenar os elementos de um vetor, assim como o Bubble Sort e o Quick Sort, entre outros. Sobre o Merge Sort é correto afirmar que:

a) O merge Sort é um algoritmo que possui uma única forma de ordenação que consiste em dividir a lista inicial em duas listas similares cada uma com um tamanho igual à metade da lista original , porém não realiza a reunião novamente das sub-listas que separou. Por isso é considerado como um algoritmo de complexidade alta, ou seja, O(n log n)

b) Uma das vantagens do uso do Merge sort é a facilidade, que esse método de ordenação tem, de implementação.  A desvantagem é que requer o dobro de memória, ou seja, precisa de uma lista com as mesmas dimensões da lista que está a ser classificada.

c) O Merge Sort é um algoritmo de ordenação de complexidade de caso médio, ou seja, O(n log n), efetuando a ordenação do vetor escolhendo um pivô aleatoriamente depois dividindo a lista inicial e ordenando seus membros comparando-os com esse pivô.

d) O Merge Sort é um algoritmo que realiza a ordenação da lista da seguinte forma: é feito uma lista com os elementos de posição ímpar (a1, a3, a5, ...) e outra com os elementos pares (a2, a4, ...), porém sem o uso adicional de memória, já que esse algoritmo não cria uma lista adicional para conter os dados subdivididos do vetor que está colocando em ordem.

e) N.D.A.

Fonte:
http://w3.ualg.pt/~hshah/ped/Aula%2014/merge_final.html

Questão EPO - Quicksort

O QuickSort é um algoritmo que se utiliza da técnica dividir-para-conquistar,  efetuando a partição do vetor desordenado em sub-vetores menores e escolhendo um vetor aleatório pra servir de parâmetro pra a ordenação interna. Tendo em vista essa definição, qual alternativa está incorreta:

a) O QuickSort necessita apenas de uma pequena pilha como memória auxiliar para conter os sub-vetores já parcialmente ordenados
b) O pior caso de ordenação do QuickSort ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos arquivos já ordenados
c) O QuickSort possui uma implementação extremamente simples, já que pequenos erros cometidos no código não influem na entrada de dados
d) O QuickSort é um método de ordenação não estável e que possui seu pior caso em O(n2) comparações.
e) N.D.A.

Fonte:
http://www.decom.ufop.br/toffolo/site_media/cms_page_media/27/T-15.%20Ordenacao%20(Parte%202).pdf

Questão EPO - Recursividade

Considerando os conceitos que envolvem recursividade em linguagens de programação, encontre a alternativa incorreta:

a) Função Recursiva é aquela que chama a si própria. Uma função também poderá ser chamada recursiva se chamar outra função que, em algum momento, chamem a primeira função, tornando esse conjunto de funções um processo recursivo;

b) As funções recursivas são consideradas, em Programação, soluções ditas mais elegantes e simples por não se utilizarem de métodos iterativos de repetição como laços como for, while e do-while;

c) Cada vez que a função recursiva é chamada, são alojados e armazenados uma cópia dos seus parâmetros, porém não é possível manter os valores das chamadas anteriores, possível apenas em estruturas como for e while;

d) Uma função pode chamar a si própria um número limitado de vezes, sendo esse limite dado pelo tamanho da pilha, se o número máximo da pilha for atingido, haverá um estouro de pilha ou “Stack Overflow”;

e) N.D.A.

Fonte:
http://www.sssinformatica.com.br/prc/Recursividade2_arquivos/frame.htm#slide0011.htm

Questão EPO - Árvore Binária

O método conhecido como percurso em pré-ordem implica em executar recursivamente os três passos na seguinte ordem: 

1. Visitar a raiz;
2. Percorrer a sub-árvore da esquerda em pré-ordem;
3. Percorre a sub-árvore da direita em pré-ordem.

Para a árvore da figura acima, no caso da visita significar imprimir, qual seria o resultado da impressão, em ordem:

a) F B C D A E H G I;
b) F B A D C E H G I;
c) B F A D C E H G I;
d) F D C E G I H G I;
e) N.D.A.

Fonte: http://equipe.nce.ufrj.br/adriano/c/apostila/arvore.htm#aplicaarv

Questão EPO - Árvore Binária

A seguinte árvore binária apresenta uma sequência de operações matemáticas a serem realizadas desde a raiz até as folhas

Dentre as alternativas abaixo, qual a alternativa que representa as saídas da árvore:

a) (+A((*B – C)%(D*E*F)))
b) (A+ ((C – B) * (E * F) % D))))
c) (A+((B – C) * D%(E * F))))
d) A + (E * F) % D * (B – C ))))
e) N.D.A.

Fonte: http://equipe.nce.ufrj.br/adriano/c/apostila/arvore.htm#introducao

Questão EPO - Fila

As seguintes tabelas representam a memória de um computador que está executando um programa para alocar caracteres em uma fila q, em três estágios diferentes, porém consecutivos:

Momento1
q.ítems
4.    E
3.    D
2.    C
1.
0.
       
Momento 2 (Consecutivo a Momento 1)                   
q.ítems               
4.    E
3.    D
2.    C
1.
0.    F

Momento 3 (Consecutivo ao Momento 2)
q.ítems               
4.     E
3.     D
2.     C
1.     G
0.     F
                   
Qual alternativa determina corretamente a posição de início, do final da fila, os conteúdos dessas posições, respectivamente:

a) Momento 1 q.inicio -  1 (vazio), q.final – 1 (vazio)
    Momento 2 q.inicio – 1 (vazio), q.final – 0 (F)
    Momento 3 q.inicio (E), q.final – 1 (F)

b) Momento 1 q.inicio = q.final (F)
    Momento 2 q.inicio – 1 (vazio), q.final – 0 (F)
    Momento 3 q.inicio (4),  q.final – 1 (G)

c) Momento 1 q.inicio -  4 (E), q.final – 1 (vazio)
    Momento 2 q.inicio – 1 (vazio), q.final – 0 (F)
    Momento 3 q.inicio = q.final – 1 (G)

d) Momento 1 q.inicio -  2 (C) , q.final – 2 (C)
    Momento 2 q.inicio – 2 (F), q.final – 0 (F)
    Momento 3 q.inicio – 4 (E), q.final – 1 (G)

e) N.D.A.

Questão EPO - Pilha

Dos seguintes agrupamentos de propriedades, qual a alternativa que contém todas as definições corretas para Pilha na Estrutura de Dados:

a)    I. A pilha segue uma ordem linear, inserindo/retirando dados “do mais recente ao menos recente”;
II. Imagem freqüentemente associada a uma teoria onde o topo da pilha é associado ao receptáculo de uma cabeça de gravação/leitura, que pode empilhar ou desempilhar itens da pilha
III. Utiliza o método FIFO (Fisrt In, Fisrt Out)

b)    I. Quanto mais recentemente o dado for inserido na pilha, mais próximo ele está de seu topo
II. Na Estrutura de dados de uma Pilha, o comando pop retira o item que se encontra no topo da pilha
III. Utiliza o método LIFO (Last In, Fisrt Out)

c)    I. A função Push em uma pilha nada mais é do que inserir um dado no topo, podendo essa função ser repetida até que a capacidade da pilha esteja esgotada
II. Uma pilha contém uma sequência de decisões adiadas: a ordem de remoção garante que as estruturas mais internas serão processadas antes das mais externas ( do topo para a base)
III. Além dos extremos, a Pilha pode dar acesso além do topo também a camadas intermediárias, resgatando itens através da função Top

d)    I.  Numa aplicação prática, a Pilha não é indicada para se estabelecer a ordem de chamada de subprogramas, pois as informações de saída de uma pilha são aleatórios;
II. Por ser uma estrutura linear, o acesso aos dados da pilha se faz através da ordem “do dado inserido mais recentemente ao dado inserido menos recentemente”;
III. O comando Top pode ser utilizado para retornar um dado armazenadao no topo da pilha, sem contudo retira-lo de lá.

e)    N.D.A.

Fonte:
http://cco.linkedej.com.br/wp-content/uploads/group-documents/9/1268948079-04_estruturas_dados_pilhas_filas.pdf
Algoritmos e Estruturas de Dados II – Estruturas de Dados Básicas Pilhas e Filas – Leonardo José Silvestre – lsilvestre@ufsj.edu.br

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

O seguinte trecho de código cria um vetor de números inteiros com 10 elementos:

    int * v;
    v = (int * ) malloc(10*sizeof(int));

Qual o significado da declaração int * v e v = (int * )malloc(10*sizeof(int)); :

a) O Comando v = (int * ) malloc(10*sizeof(int)); reserve espaço de memória da área livre e atribui endereço de variável int *v, que passa a armazenar o endereço inicial de uma área contínua de memória suficiente para conter 10 valores inteiros.

b) O Comando v = (int * ) malloc(10*sizeof(int)); reserve espaço de memória da área livre e atribui endereço de variável int *v, que passa a ser uma varíavel global ;

b) O Comando v = (int * ) malloc(10*sizeof(int)); armazena o endereço inicial de uma área contínua de memória suficiente para conter 10 valores inteiros e a declaração de variável int * v reserva espaço de memória da área livre para a alocação da variável.

c) O Comando v = (int * ) malloc(10*sizeof(int)); armazena o endereço inicial de uma área contínua de memória suficiente para conter 10 valores inteiros e a declaração de variável int * v podendo ser tratado como um vetor declarado estaticamente

d) O Comando v = (int * ) malloc(10*sizeof(int)); reserve espaço de memória da área livre e atribui endereço de variável int *v, que responde com um mensagem de tratamento printf v==NULL

e) N.D.A.

Fonte:
http://www.tecgraf.puc-rio.br/~mgattass/ed/material/ApresentacoesEmPDF/ed05-Vetores.pdf

Waldemar Celes, Renato Cerqueira, José Lucas Rangel,
Introdução a Estruturas de Dados, Editora Campus
(2004)
Capítulo 5 – Vetores e alocação dinâmica

Questão EPO - Estrutura de Dados

Levando em consideração os itens abaixo, qual das alternativas se enquadra na explicação dos seguintes tópicos: 

I. Estrutura de Dados (Descrição);
II. Estruturas de Dados (Objetivo);

a) I - Ao serem aplicadas, permitem que certas operações críticas sejam executadas usando o menor custo possível (tempo e espaço de memória);
    II - Algumas são especializadas para certas tarefas (ex: B-Tree, para bases de dados ou tabelas de routing para redes).

b) I - É uma maneira de armazenar e organizar dados, facilitando o acesso e modificação;
    II - Ao serem aplicadas, permite que certas operações críticas sejam executadas usando o menor custo possível (tempo e espaço de memória);

c) I - Um conjunto bem especificado de instruções simples a serem seguidas para resolver um problema.
    II - Ao serem aplicadas, permite que certas operações críticas sejam executadas usando o menor custo possível (tempo e espaço de memória);

d) I - Algumas são especializadas para certas tarefas (ex: B-Tree, para bases de dados ou tabelas de routing para redes).
    II - Um conjunto bem especificado de instruções simples a serem seguidas para resolver um problema.

e) N.D.A.

Fonte:
http://ssdi.di.fct.unl.pt/seminf/docs/aula05/ED-seminario.pdf
Algoritmos e Estruturas de Dados, Prof° Vasco Amaral, Universidade Nova de Lisboa (UNL), e-mail: vasco.amaral@di.fct.unl.pt

Questão EPO - Struct

1º) Dada a instrução

aaa.bbb.ccc = 25

a)    ccc é membro da estrutura bbb;
b)    bbb é membro da estrutura aaa;
c)    aaa é membro da estrutura bbb;
d)    aaa é membro da estrutura ccc;
e)    N.D.A.


2º) A instrução:

typedef double Velocidade

a) cria um tipo de dado chamado Velocidade;
b) renomeia o tipo double;
c) velocidade é um sinônimo para o tipo double;
d) double passa a ser um novo tipo de dado;
e) N.D.A.

Fonte: Victorine Viviane Mizrahi, Treinamento em linguagem C++, Módulo 2, 2º Edição, Person Prentice Hall Editora, São Paulo, 2007, ISBN 9788576050469,
Página 213.

Questão EPO - Ponteiro

O seguinte programa apresenta um erro de sintaxe :

#include <iostream>
using namespace std;
int main ( )
    {
    const VAL = 987;
    int i = 987;
    const *p = VAL;
    cout<< *p;
    return 0;
}

Para obter a impressão do conteúdo da variável VAL, o programa deve ser reescrito com a sintaxe:

a) int *p = VAL;
b) int i = &VAL;
c) const *p = &VAL;
d) int i = &p;
e) N.D.A.

Fonte: Victorine Viviane Mizrahi, Treinamento em linguagem C++, Módulo 1 2º Edição, Person Prentice Hall Editora, São Paulo, 2006, ISBN 9788576050452,
Páginas 178 e 179 (Adaptação de duas questões).