1) As Tabelas Hash (Hash tables) são tipos abstratos de dados presentes em praticamente todas as linguagens de programação de alto nível. Os dicionários Python, map em C++ e Go, array associativo em PHP, Hash em Ruby, Hashtable em Java e assim por diante. Ela permite distribuir pares de chave, valor dentro da "Tabela". Dada uma chave, a função Hash decide em qual endereço dessa tabela aquele valor deve ser armazenado.

Considere a frase a seguir:
"Para evitar que se tenha o problema de ________ em uma tabela é necessário escolher uma boa _________, o que é uma tarefa ___________dependendo da situação"

Escolha a alternativa que completa corretamente as lacunas.
Alternativas:

a) Memória, arquitetura, complexa
b) armazenamento, estrutura, simples
c) colisão, entrada de dados, simples
d) colisão, função hash, complexa
e) colisão, tabela hash, difícil

2) Hash é uma generalização da noção mais simples de um arranjo comum, sendo uma estrutura de dados do tipo dicionário. Dicionários são estruturas especializadas em prover as operações de inserir, pesquisar e remover. A ideia central do Hash é utilizar uma função, aplicada sobre parte da informação (chave), para retornar o índice onde a informação deve ou deveria estar armazenada.
Sobre tabelas Hash, julgue as afirmativas em V para Verdadeiras e F para Falsas.
( ) O critério principal para a escolha de uma função hash que seja considerada boa é a diminuição do problema da colisão

( ) O que decide em qual local da tabela será armazenado determinado dado é a sua imagem em uma função hash.

( ) Relacionar o conteúdo que está sendo buscado com o índice da posição onde está armazenado pode gerar uma série de problemas.

Assinale a alternativa que apresenta a sequência correta.

Alternativas:

a)
F, F, F

b)
V, F, F

c)
V, V, F

d)
F, F, V

e)
V, V, V

3)
A preocupação com a complexidade de algoritmos é fundamental para projetar algoritmos eficientes. Podemos desenvolver um algoritmo e depois analisar a sua complexidade para verificar a sua eficiência. Mas o melhor ainda é ter a preocupação de projetar algoritmos eficientes desde a sua concepção.



A notação BIG O é utilizada para indicar a complexidade de algoritmos baseados em sua dominância assintótica. As funções a seguir são utilizadas normalmente para expressar complexidade.
- n²
- n³
- logN
- NlogN

Assinale a alternativa que apresenta a ordem crescente das funções em relação a sua complexidade.

Alternativas:

a) n³ > n² > logN > NlogN

b) NlogN < logN < n² < n³

c) n² < n³ < NlogN < logN

d) logN < NlogN < n² < n³

e) n² > n³ > logN > NlogN

4) Na maioria das vezes, a escolha de um algoritmo é feita através de critérios subjetivos como a facilidade de compreensão, codificação e depuração e eficiencia na utilização dos recursos do computador e rapidez. A análise de algoritmo fornece uma medida objetiva de desempenho proporcional ao tempo de execução do algoritmo. O tempo de execução de um algoritmo para uma determinada entrada pode ser medido pelo número de operações primitivas que ele executa. Como esta medida fornece um nível de detalhamento grande convém adotar medidas de tempo assintótica.
A coluna A apresentam operações de estruturas de dados e a coluna B as complexidades de algoritmos em seu caso médio.

COLUNA A COLUNA B
1. Remoção em Árvore a) O(1)
2. Consulta em Fila b) O(n)
3. Consulta em Heap c) O(logn)
4. Remoção em Hash

Assinale a alternativa que associa de forma correta as colunas.

Alternativas:

a) 1 - a), 2 - a), 3 - b), 4 - c)
b) 1 - c), 2 - b), 3 - a), 4 - b)
c) 1 - a), 2 - a), 3 - b), 4 - b)
d) 1 - c), 2 - a), 3 - b), 4 - c)
e)1 - a), 2 - a), 3 - c), 4 - c)

5) A complexidade pode ser calculada através do tempo de execução do algoritmo determinado pelas instruções executadas :quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n; e também do espaço de memória utilizado pelo algoritmo : quanto “espaço de memória/disco” é preciso para armazenar a(s) estrutura(s) utilizada(s) pelo algoritmo. Uma das principais medidas de complexidade é a quantidade de vezes que a operação fundamental é executada. Por exemplo, para um algoritmo de ordenação, uma operação fundamental é a comparação entre elementos quando à ordem.

Considere o seguinte algoritmo de multiplicação de matrizes:
programa multiplica_matrizes;
matriz mat1, mat2, mat3;
inteiro linha, coluna, i, acumula;
"leia mat1";
"leia mat2";
"verifique se mat1 é compativel com mat2";
para linha de 1 até "numero de linhas de mat1" faça
para coluna de 1 até "numero de colunas de mat2" faça
acumula=0;
para i de 1 até "numero de colunas de mat1" faça
acumula=acumula+mat1[linha][i]*mat2[i][coluna];
fimpara;
mat3[linha][coluna]=acumula;
fimpara;
fimpara;
imprima mat3;
fim programa;
Sendo a operação mais importante a multiplicação entre dois elementos. Assinale a alternativa que apresenta a complexidade deste algoritmo.
Alternativas:
a) O(logn)
b) O(n)
c) O(1)
d) O(n²)
e) O(n3)