Apol 5

Prévia do material em texto

Questão 1/5 - Estrutura de Dados 
Na AULA 5 estudamos grafos e seus algoritmos de busca. 
Acerca da busca em profundidade no grafo, assinale a alternativa INCORRETA. 
Nota: 0.0 
 
A A busca em profundidade trabalha com o uma pilha que mantém todos os vértices que ainda 
não tiveram todos os seus vizinhos visitados nela. 
 
B A busca em profundidade pode ser implementada com qualquer tipo de representação de 
grafos: matriz ou lista. 
 
C Uma variável mantém salvo todos os vértices já visitados, pois podemos passar somente uma 
vez por cada vértice. 
 
D Um vértice, quando visitado pela primeira vez, tem sua lista de vizinhos acessada 
imediatamente e seu número é colocado na pilha. 
 
E Um vértice sai da pilha quando o algoritmo pula para o próximo vizinho deste vértice. 
Um vértice só sai da pilha quando é localizado o elemento que contém um ponteiro nulo da sua lista 
encadeada de vizinhos. 
Questão 2/5 - Estrutura de Dados 
Na AULA 6 estudamos endereçamento aberto de tabelas hash com tentativa linear e tentativa quadrática. 
Acerca da tentativa linear e da tentativa quadrática, assinale a alternativa INCORRETA: 
Nota: 20.0 
 
A Na tentativa linear, quando uma colisão ocorre, a próxima posição livre, subsequente, é 
acessada. 
 
B Na tentativa quadrática, quando uma colisão ocorre, a primeira posição a ser testada após a 
colisão é sempre a posição seguinte do vetor. 
 
C Na tentativa quadrática, quando uma colisão ocorre, a nova tentativa é feita em uma posição 
que está a uma distância d da posição originalmente testada. Onde d será sempre o dobro da 
posição originalmente testada. 
Você acertou! 
O cálculo de d não é o dobro. A equação é apresentada na página 20 da AULA 6. 
 
D A função hash adotada independe do tipo de tentativa empregado (linear ou quadrática). 
 
E A tentativa quadrática tende a espalhar mais as chaves colididas na tabela hash. 
Questão 3/5 - Estrutura de Dados 
Na AULA 6 estudamos a estrutura de dados do tipo hash. 
Acerca de hashs, vetores e tipos de endereçamento, assinale a alternativa INCORRETA. 
Nota: 0.0 
 
A O uso de tabela hash é capaz de transformar o tempo de busca de um dado em uma estrutura de 
dados do tipo vetor, em uma complexidade que independe do tamanho do conjunto de dados. 
 
B Podemos definir a posição de inserção de um dado no vetor utilizando uma função hash. Esta 
função será uma equação lógica e/ou matemática. 
 
C O endereçamento direto em um vetor é aquele onde armazenamos um novo dado na primeira 
posição livre disponível no vetor. 
 
D O acesso a qualquer dado de um vetor com endereçamento direito é realizado com O(1), bem 
como o tempo de busca de uma informação neste vetor. 
O tempo de busca com endereçamento direto é atrelado ao algoritmo de busca adotado. AULA 6 – 
TEMA 1. 
 
E Palavra-chave em uma tabela hash é aquele dado utilizado no cálculo de uma posição 
utilizando um algoritmo de hash. 
Questão 4/5 - Estrutura de Dados 
O método da divisão é um tipo de função hash bastante empregado na construção de tabelas hash. 
Assuma que você tem disponível, para utilizar como palavras-chave, valores numéricos inteiros de 4 dígitos. Você decide que irá agrupar os 
dígitos em pares e somá-los para usar como palavra-chave. Por exemplo, o número 1234, será: 12 + 34 = 46. 
Assuma também que você tem um vetor de dimensão 100 (posições 0 até 99) disponível para armazenamento e que irá adotar o método da 
divisão. Assinale a alternativa INCORRETA: 
Nota: 0.0 
 
A A palavra-chave 0125 será inserida na posição 26. Porém, se alterarmos o tamanho do vetor 
para 110, a nova posição desta chave será 36. 
Neste caso, a chave continuará na posição 26 para o vetor 100 e para o 110. 
 
B A palavra-chave 4455, será inserida na última posição disponível do vetor. 
44+55 = 99 MOD 100 = 99. 99 é a ultima posição possível deste vetor. 
 
C A palavra-chave 9128, será inserida na posição 19 do vetor. 
91+28 = 119 MOD 100 = 19. 
 
D O maior valor possível representado com 4 dígitos será colocado na posição 98. 
O maior valor com 4 dígitos é 9999 = 99+99 = 198 MOD 100 = 98. 
 
E A palavra-chave 1873, será inserida na posição 91 do vetor. 
18+73 = 91 MOD 100 = 91. 
Questão 5/5 - Estrutura de Dados 
A definição de uma boa função hash é fundamental para termos uma tabela hash com um bom desempenho. 
Acerca de funções hash, assinale a alternativa CORRETA: 
Nota: 0.0 
 
A Uma função hash apresenta sempre a mesma fórmula bem definida, e independe do tamanho 
do conjunto de dados, e dos tipos de dados-chave utilizados. 
Uma função hash não apresenta uma fórmula definida, e deve ser projetada levando em consideração o 
tamanho do conjunto de dados, seu comportamento e os tipos de dados-chave utilizados. 
 
B O uso de estrutura de tabela hash sempre apresentará um desempenho de busca superior ao 
endereçamento direito. 
Nem sempre. Se a função hash adotada é muito complexa, talvez apresente um desempenho inferior. 
Portanto, escolher a função hash adequada é fundamental. 
 
C Uma função hash necessita inserir dados que minimizem o número de colisões, reduzindo 
também o tempo gasto resolvendo colisões e reavendo os dados. 
Correto. AULA 6 – TEMA 2. 
 
D A função hash que utiliza o método da divisão só pode ser aplicado para palavras-chave do tipo 
numérica. 
Qualquer tipo de dado pode ser usado no método da divisão. 
 
E O método da divisão utiliza o quociente da divisão de dois valores para encontrar a posição de 
uma palavra-chave. 
Não é o quociente da divisão, mas sim o resto da divisão.