Apol 05

Prévia do material em texto

CURSO: CST ANÁLISE E DESENVOLVIMENTO DE SISTEMAS
Atenção. Este gabarito é para uso exclusivo do aluno e não deve ser publicado ou compartilhado em redes sociais ou grupo de mensagens.
O seu compartilhamento infringe as políticas do Centro Universitário UNINTER e poderá implicar sanções disciplinares, com possibilidade de desligamento do
quadro de alunos do Centro Universitário, bem como responder ações judiciais no âmbito cível e criminal.
Nota: 20
Disciplina(s):
Estrutura de Dados
Data de início: 22/04/2019 09:19
Prazo máximo entrega: - 
Data de entrega: 22/04/2019 21:21
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.
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.
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.
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.
B A palavra-chave 4455, será inserida na última posição disponível do vetor.
C A palavra-chave 9128, será inserida na posição 19 do vetor.
D O maior valor possível representado com 4 dígitos será colocado na posição 98.
E A palavra-chave 1873, será inserida na posição 91 do vetor.
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.
B O uso de estrutura de tabela hash sempre apresentará um desempenho de busca superior ao endereçamento
direito.
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.
D A função hash que utiliza o método da divisão só pode ser aplicado para palavras-chave do tipo numérica.
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.
Um vértice só sai da pilha quando é localizado o elemento que contém um ponteiro nulo da sua lista encadeada de
vizinhos.
�
Você acertou!
O cálculo de d não é o dobro. A equação é apresentada na página 20 da AULA 6.
�
O tempo de busca com endereçamento direto é atrelado ao algoritmo de busca adotado. AULA 6 – TEMA 1.�
Neste caso, a chave continuará na posição 26 para o vetor 100 e para o 110.�
44+55 = 99 MOD 100 = 99. 99 é a ultima posição possível deste vetor.�
91+28 = 119 MOD 100 = 19.�
O maior valor com 4 dígitos é 9999 = 99+99 = 198 MOD 100 = 98.�
18+73 = 91 MOD 100 = 91.�
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.
�
Nem sempre. Se a função hash adotada é muito complexa, talvez apresente um desempenho inferior. Portanto, escolher
a função hash adequada é fundamental.
�
Correto. AULA 6 – TEMA 2.�
Qualquer tipo de dado pode ser usado no método da divisão.�
Não é o quociente da divisão, mas sim o resto da divisão.�
ESTRUTURA DE DADOS