Questão EPO - Heap sort

HeapSort, assinale a alternativa correta:

a) As estruturas de dados heap é um ponteiro que pode ser visto como uma árvore binária incompleta. Cada nó da árvore binária corresponde a um elemento da matriz. 
b) As estruturas de dados binários heap é uma matriz que pode ser visto como uma árvore binária completa. Cada nó da árvore binária corresponde a um conjunto de elemento da matriz. 
c) As estruturas de dados heap é uma matriz que pode ser visto como uma árvore binária incompleta. Cada nó da árvore binária corresponde a um elemento da matriz.
d) As estruturas de dados binários heap é uma matriz que pode ser visto como uma árvore binária completa. Cada nó da árvore binária corresponde a um elemento da matriz.
e) n.d.a

Fonte:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Questão EPO - Bubble sort

Bubble Sort consiste em comparar todos os pares consecutivos (adjacentes no vetor) de chaves, realizando troca caso necessário. Realiza um certo número de varreduras (passadas) sobre o vetor a ser ordenado. O procedimento termina quando, em uma dada varredura, nenhuma troca de chaves ocorre. Suponha que se deseja classificar em ordem crescente o seguinte vetor de chaves [28, 26, 30, 24, 25]. Ao fim da segunda varredura tem-se:

a) [26, 28, 24, 25, 30]
b) [26, 24, 28, 25, 30]
c) [24, 25, 26, 28, 30]
d) [26, 24, 25, 28, 30]
e) nda

Fonte:
http://www.inf.ufrgs.br/~dsogari/material/S3/INF01124/Aulas/Aula05-bubblesort.pdf

Questão EPO - Hash Table

Sobre Hash Table, assinale a alternativa incorreta:

a) Com a tabela hash é possível garantir a ordem em que os itens são armazenados dentro dela.
b) Uma tabela de hash consiste em uma estrutura de dados que possui como vantagem o alto desempenho na busca por informações. (teóricamente, o custo computacional seria práticamente constante).
c) Cada item armazenado na tabela de Hash possui um valor numérico (índice) que o identifica únicamente dentro da estrutura de dados. E este índice é gerado a partir de operações matemáticas.
d) Para encontrar um item dentro de uma tabela de hash, basta passar o valor do índice para a mesma, que o índice numérico será calculado e, a partir dele, a localização da informação.
e) n.d.a.

Referencia:
http://www.guj.com.br/java/53108-hashtable
http://en.wikipedia.org/wiki/Hash_table

Questão EPO - Merge sort

Mergesort (ordenação por intercalaçao) divide o vetor de entrada em dois subvetores com metade do tamanho do vetor original (em caso de tamanho ímpar, um dos subvetores tería um elemento a mais que o outro). Cada um dos subvetores é ordenado recursivamente. Os dois subvetores são intercalados em um vetor temporário. Mergesort garante que os dois subproblemas têm tamanho n/2, mas requer alocaçao de memória para o vetor temporário. A desvantagem é:

a) de juntar as duas metades em um único conjunto já classificado após classificar as duas metades recursivamente aplicando o Mergesort.
b) a facilidade, que esse método de ordenação tem, de implementação.
c) faz uso de dois array auxiliar, gerando um gasto extra de memória (o dobro).
d) é 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.
e) n.d.a

Fonte:
http://www.lcad.icmc.usp.br/~nonato/ED/Ordenacao/node52.htm
http://w3.ualg.pt/~hshah/ped/Aula%2014/merge_final.html

Questão EPO - Quicksort

O Quick Sort é um dos método mais rápidos de ordenação, apesar de às vezes partições desequilibradas poderem conduzir a uma ordenação lenta. Esse método de ordenação utiliza a técnica divide and conquer (dividir o problema inicial em dois subproblemas e resolver um problema menor utilizando a recursividade). Porque é que a seguinte lista é pouco eficiente no método de ordenação do quick sort?  Lista: (9, 8, 7, 6, 5, 4, 3, 2, 1).

a) Visto que o algoritmo escolhe o primeiro elemento para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada (decrescentemente).
b) Visto que o algoritmo escolhe o elemento central para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada
c)  Visto que o algoritmo escolhe o terceiro elemento para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada
d) Visto que o algoritmo escolhe o último elemento para pivô, neste caso, é uma má escolha visto que a lista já se encontra ordenada (decrescentemente).
e) n.d.a

Fontes:
http://en.wikipedia.org/wiki/Quicksort
http://w3.ualg.pt/~hshah/ped/Aula%2014/Quick_final.html

Questão EPO - Recursividade

Sobre recursividade é correto afirmar que:

a) O método de recursividade deve ser utilizado para excluir uma expressão aritmética na qual um procedimento pode chamar a si mesmo, ou seja, a recursividade consiste em um método que, para que possa ser aplicado a uma estrutura, aplica a si mesmo para as subestruturas componentes.

b) O método de recursividade deve ser utilizado para avaliar uma expressão aritmética na qual um classe pode chamar a si mesmo, ou seja, a recursividade consiste em uma interface que, para que possa ser aplicado a uma estrutura, aplica a si mesmo para as subestruturas componentes.

c) O método de recursividade deve ser utilizado para analizar uma expressão aritmética na qual um procedimento pode chamar um outro procedimento congruente, ou seja, a recursividade consiste em um método que, para que possa ser aplicado a uma estrutura, aplica a si mesmo para as subestruturas componentes.

d) O método de recursividade deve ser utilizado para avaliar uma expressão aritmética na qual um procedimento pode chamar a si mesmo, ou seja, a recursividade consiste em um método que, para que possa ser aplicado a uma estrutura, aplica a si mesmo para as subestruturas componentes.

e) n.d.a.

Referencia: http://www.questoesdeconcursos.com.br

Questão EPO - Linked List

Sobre Linked List, assinale a alternativa INCORRETA:

a) Ao manipular listas ligadas no local, é preciso ter cuidado para não usar os valores que você tem invalidado em trabalhos anteriores. Isso faz com que algoritmos para inserir ou excluir os nós da lista encadeada pouco sutil.

b) As listas são estruturas de dados de armazenamento sequencial assim como os arrays. Mas,diferentemente dos arrays, as listas não possuem capacidade fixa o que facilita bastante o trabalho.

c) Ao manipular listas ligadas no local, é preciso ter cuidado para não usar os valores que você tem invalidado em trabalhos anteriores. Isso faz com que algoritmos para inserir ou excluir os nós da lista encadeada pouco sutil.

d) As listas são estruturas de dados de armazenamento sequencial assim como os arrays. Assim como as arrays, as listas possuem capacidade fixa o que facilita bastante o trabalho.

e) n.d.a

Fonte: http://en.wikipedia.org/wiki/Linked_list

Questão EPO - Árvore Binária

O percurso em pré-ordem segue os nós até chegar os mais “profundos”, em “ramos” de subárvores da esquerda para a direita. É conhecida usualmente pelo nome de percurso em profundidade (depth-first). O percurso em pré-ordem é:

a) A B D C E G F H I
b) A D B C E G F I H
c) D B C E G F I H A
d) D B G E H I F C A

Questão EPO - Árvore Binária

Podemos representar a expressão aritmética:

a) a + b /c − d ∗ e + f
b) ((a + b) /(c − d)) ∗ (e + f )
c) (a + b) /c − (d ∗ e) + f
d) a + (b / c) − d ∗ e + f)

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

A alocação dinâmica é o processo que aloca memória em tempo de execução. Ela é utilizada quando não se sabe ao certo quanto de memória será necessário para o armazenamento das informações, podendo ser determinadas em tempo de execução conforme a necessidade do programa. Dessa forma evita-se o desperdício de memória. Qual é a desvantagem da alocação dinâmica?

a) A desvantagem da alocação dinâmica está na pilha de memória estruturada, o que causaria o fechamento do programa e também, com a alocação dinâmica, o programa torna-se mais lento, pois ela requer muito do processamento.

b) A desvantagem da alocação dinâmica está no rompimento da pilha de memória, o que causaria o fechamento do programa e também, com a alocação dinâmica, o programa torna-se mais lento, pois ela requer muito do processamento.

c) A desvantagem da alocação dinâmica está no compartilhamento da pilha de memória, o que causaria um erro no programa e também, com a alocação dinâmica, o programa torna-se ineficiente.

d) A desvantagem da alocação dinâmica está no rompimento da pilha de memória, o que causaria o fechamento do programa e também, com a alocação dinâmica, o programa torna-se mais lento, apesar de não requerer muito do processamento.

Questão EPO - Fila

Outra estrutura de dados bastante usada em computação é a fila. Na estrutura fila, os acessos aos elementos também seguem uma regra.

a) Na fila “o ultimo que entra é o primeiro que sai”. A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila, e só podemos retirar o elemento do final.

b) Na fila “o primeiro que entra é o primeiro que sai”. A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila, e só podemos retirar o elemento do início.

c) Na fila “o primeiro que entra é o último que sai”. A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila, e só podemos retirar o elemento do início.

d) Na fila “o último que entra é o último que sai”. A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila, e só podemos retirar o elemento do início.

Referencia: slide da aula

Questão EPO - Estrutura de Dados

Também faz parte dos o Objetivos e Visão Geral das Estruturas Dados:

I. Identificar e desenvolver modelos matemáticos, determinando que classes de problemas podem ser resolvidos com o uso deles;

II. Criar representações concretas dos objetos e desenvolver rotinas capazes de atuar sobre estas representações, de acordo com o modelo considerado;

III. A distribuição da estrutura de dados correta que levam a programas elegantes e eficientes.

IV. O projetista deve ser capaz de escolher a mais adequada para resolver o problema proposto, tomando como medidas de eficiência da implementação, as suas necessidades de espaço e armazenamento e tempo de execução.

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

Referencia: slides da aula

Questão EPO - Pilha

A idéia fundamental sobre pilha é que todo acesso a seus elementos é feito...

a) a partir do seu topo.
b) a partir do primeiro membro.
c) a partir do elemento anterior.
d) n.d.a.

Referencia: slide da aula

Questão EPO - Ponteiro

Ao lidar com arranjos, uma operação crítica é o cálculo do endereço para o elemento desejado no arranjo, o que é feito através da manipulação de ponteiros. De fato, em algumas linguagens (como C), os conceitos de "arranjo" e "ponteiro" são intercambiáveis. Em outras estruturas de dados, como listas encadeadas, ponteiros são usados como referências para intercalar cada elemento da estrutura com seus vizinhos (seja anterior ou próximo).    Ponteiros também são utilizados para simular a passagem de parâmetros por referência em linguagens que não oferecem essa construção (como o C). Isso é útil se desejamos?

a) que uma modificação em um valor não seja feito pela função chamada e seja visível pela função que a chamou, ou também para que uma função possa retornar múltiplos valores.

b) que uma modificação em um valor feito pela função chamada não seja visível pela função que a chamou, ou também para que uma função possa retornar múltiplos valores.

c) que uma modificação em um valor feito pela função chamada seja visível pela função que a chamou, ou também para que uma função possa retornar múltiplos valores.

d) que uma modificação de vários valor não seja feito pela função chamada e seja visível pela função que a chamou, ou também para que uma função possa retornar múltiplos valores.

Referencia: http://pt.wikipedia.org/wiki/Ponteiro_(programa%C3%A7%C3%A3o)