AS Estrutura De Dados Não Lineares

Prévia do material em texto

30/10/2020 Fazer teste: <font class="click">AS I</font> – ...
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_565515_1&course_id=_62… 1/2
 Fazer teste: <font class="click">AS I</font>ESTRUTURAS DE DADOS NÃO-LINEARES - 40h_Turma_01_102020 Material Referencial ATIVIDADES DA DISCIPLINA
Fazer teste: AS I 
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 3.
Forçar conclusão Uma vez iniciado, este Teste deve ser concluído em uma sessão. Não saia do teste antes de clicar em Salvar e enviar.
Suas respostas foram salvas automaticamente.
a.
b.
c.
d.
e.
PERGUNTA 1
Considere a seguinte de�nição para uma função recursiva:
Neste contexto, o valor de f(5) é:
31.
33.
32.
30.
34.
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 2
Um vetor, ou array, pode ser de�nido como um conjunto �nito e ordenado de elementos homogêneos. Neste sentido, considere as
seguintes a�rmações:
I - Um vetor pode armazenar, de maneira e�ciente, dados de diferentes tipos.
II - O armazenamento dos dados de um vetor na memória de um computador é feito de forma contígua.
III - O acesso aos dados de um vetor, armazenado na memória de um computador, é feito por meio de busca linear, veri�cando-se todos
os elementos até encontrar aquele que se busca.
IV - O acesso aos dados de um vetor é feito por meio de índices que identi�cam suas respectivas posições.
É VERDADEIRO o que se a�rma em
III e IV, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
II e IV, apenas.
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 3
A operação de busca em um vetor consiste em encontrar um determinado valor em um dado vetor. Assim, considerando o vetor v=
[9,4,2,5,2,1,8,6] e uma função busca(x) que implementa a operação de busca no vetor v, o retorno da função busca(8) é
7.
6.
1.
8.
-1.
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 4
Sejam os contadores x e y utilizados para a de�nição dos índices dos ponteiros head e tail, respectivamente, uma �la circular de tamanho n
e os índices dos ponteiros head=x mod n e tail=y mod n. Considerando este contexto, a �la circular está:
cheia quando x≠y.
vazia quando x=y=n.
vazia quando x=y.
cheia quando x mod n=y mod n.
vazia quando x<n e y<n.
0,25 pontos   Salva
?
 Estado de Conclusão da Pergunta:
 Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas. Salvar todas as respostas Salvar e Env
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/execute/courseMain?course_id=_628440_1
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453836_1&mode=reset
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453850_1&mode=reset
31/10/2020 Fazer teste: <font class="click">AS II</font> – ...
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_565517_1&course_id=_62… 1/2
 Fazer teste: <font class="click">AS II</font>ESTRUTURAS DE DADOS NÃO-LINEARES - 40h_Turma_01_102020 Material Referencial ATIVIDADES DA DISCIPLINA
Fazer teste: AS II 
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 2.
Forçar conclusão Uma vez iniciado, este Teste deve ser concluído em uma sessão. Não saia do teste antes de clicar em Salvar e enviar.
Suas respostas foram salvas automaticamente.
a.
b.
c.
d.
e.
PERGUNTA 1
Questão anulada, selecione uma das opções abaixo para receber a pontuação.
Considere a árvore binária da questão 8, a qual representa uma expressão, e selecione a alternativa que mostra de forma correta a
expressão em notação pre�xa, resultado do percurso pelo método pré-ordem.
+A*-BC^D*EF;
+A*-^BCD*EF;
+A-*BC^D*FE;
+A*-CB^D*EF;
+A*-CB^D*FE;
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 2
Questão anulada, selecione uma das opções abaixo para receber a pontuação.
Considerando a árvore binária da questão 4, o resultado do percurso em ordem (in ordem) enumera os vértices da seguinte
maneira;
D, B, H, E, I, A, F, K, C;
D, H, B, E, I, A, F, K, C;
D, B, H, E, I, C, F, K, A.
D, B, E, H, I, A, F, K, C;
D, B, I, E, H, A, F, K, C;
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 3
Questão anulada, selecione uma das opções abaixo para receber a pontuação.
Considerando a árvore binária da questão 4, o resultado do percurso em pós-ordem enumera os vértice da seguinte maneira;
D, H, I, E, B, K, C, F, A;
D, H, I, B, E, K, F, C, A.
D, H, I, E, B, F, K, C, A;
D, H, I, E, K, B, F, C, A;
D, H, I, E, B, K, F, C, A;
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 4
Questão anulada, selecione uma das opções abaixo para receber a pontuação.
Considerando a árvore binária da questão 4, o resultado do percurso em pré-ordem enumera os vértice da seguinte maneira;
A, B, C, D, E, F, H, I, K;
A, B, E, I, D, H, C, F, K;
A, B, D, E, H, I, C, F, K;
A, B, C, F, E, D, K, I, H;
A, B, D, E, I, H, C, F, K.
0,25 pontos   Salva
?
 Estado de Conclusão da Pergunta:
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/execute/courseMain?course_id=_628440_1
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453836_1&mode=reset
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453850_1&mode=reset
29/10/2020 Fazer teste: <font class="click">AS III</font> – ...
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_565516_1&course_id=_62… 1/2
 Fazer teste: <font class="click">AS III</font>ESTRUTURAS DE DADOS NÃO-LINEARES - 40h_Turma_01_102020 Material Referencial ATIVIDADES DA DISCIPLINA
Fazer teste: AS III 
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 1.
Forçar conclusão Uma vez iniciado, este Teste deve ser concluído em uma sessão. Não saia do teste antes de clicar em Salvar e enviar.
Suas respostas foram salvas automaticamente.
a.
b.
c.
d.
e.
PERGUNTA 1
Considere a árvore de busca binária representada abaixo:
Se utilizarmos o algoritmo de busca, em sua versão recursiva, o número necessário de chamadas ao algoritmo para encontrar o valor de chave igual a 18 é de:
7 chamadas.
3 chamadas;
4 chamadas;
6 chamadas;
5 chamadas;
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 2
A rotação esquerda simples é um procedimento que deve ser aplicado para balancear uma árvore desbalanceada enraizada no vértice v. Esse procedimento
consiste dos seguintes passos:
Passo 1: separar a subárvore direita;
Passo 2: faça a subárvore esquerda, da subárvore separada, tornar-se a subárvore direita do vértice v;
Passo 3: faça da árvore com raiz em v a subárvore esquerda da subárvore separada.
Assim, esse procedimento deve ser aplicado quando:
O vértice v da árvore apresenta fb(v) > 1;
O vértice v da árvore apresenta fb(v) = -1.
O vértice v da árvore apresenta fb(v) > -1;
O vértice v da árvore apresenta fb(v) < -1;
O vértice v da árvore apresenta fb(v) < 1;
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 3
As árvores vermelho-pretas são casos particulares de árvores de busca binária, observando o mesmo objetivo de organizar os elementos (chaves) de forma que
eles possam ser comparados. A principal vantagem oferecida pelas árvores vermelho-pretas é:
Garantir que a complexidade dos algoritmos seja linear;
Garantir que a árvore mantenha seu balanceamento após a realização de operação;
Garantir que a árvore mantenha sua largura após a realização de operações;
Garantir que a complexidade dos algoritmos seja exponencial;
Garantir que a complexidade dos algoritmos seja quadrática.
0,25pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 4
Considere os passos para o balanceamento de uma árvore AVL que são descritos na �gura abaixo:
Nesse contexto, os passos descritos ilustram o procedimento denominado de:
Dupla rotação à direita;
Rotação à esquerda;
Tripla rotação à direita.
Rotação à direita;
Dupla rotação à esquerda;
0,25 pontos   Salva
?
 Estado de Conclusão da Pergunta:
 Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas. Salvar todas as respostas Salvar e Enviar
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/execute/courseMain?course_id=_628440_1
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453836_1&mode=reset
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453850_1&mode=reset
31/10/2020 Fazer teste: <font class="click">AS IV</font> – ...
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_565514_1&course_id=_62… 1/2
 Fazer teste: <font class="click">AS IV</font>ESTRUTURAS DE DADOS NÃO-LINEARES - 40h_Turma_01_102020 Material Referencial ATIVIDADES DA DISCIPLINA
Fazer teste: AS IV 
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 2.
Forçar conclusão Uma vez iniciado, este Teste deve ser concluído em uma sessão. Não saia do teste antes de clicar em Salvar e enviar.
Suas respostas foram salvas automaticamente.
 Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
a.
b.
c.
d.
e.
PERGUNTA 1
Uma colisão ocorre quando dois valores de chave são mapeados, por uma função hash para um mesmo índice de uma posição na tabela.
Dizemos que esses valores são sinônimos em relação à função. A ocorrência de colisões pode ter sua probabilidade de ocorrência
associada a uma medida denominada:
Fator de degeneração;
Fator de colisão;
Fator de carga.
Fator de independência;
Fator de coincidência;
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 2
As colisões podem ser tratadas de duas maneiras, por encadeamento ou por endereçamento aberto. O tratamento de colisões por
encadeamento por ser feito de duas formas diferentes: por encadeamento exterior e por encadeamento interior. Nesse contexto, selecione
a alternativa CORRETA dentre as disponíveis abaixo.
No encadeamento exterior, a ideia base é manter m listas encadeadas ou duplamente ligadas, uma para cada posição na tabela.
Nesse caso, a tabela não armazena nenhum endereço de memória para os registros, em vez disso, cada posição na tabela aponta
para outro registro;
O método de tratamento de colisões por endereçamento aberto é uma alternativa às abordagens anteriores. Nesse caso, o
tratamento de colisões não considera o armazenamento de ponteiros, mas somente dos registros. Na ocorrência de uma colisão, a
função deve ser capaz de calcular o índice para outra posição na tabela.
No encadeamento exterior, a ideia base é manter m listas encadeadas ou duplamente ligadas, uma para cada posição na tabela.
Nesse caso, a tabela armazena o endereço de memória para os registros;
O tratamento de colisões com encadeamento interior é utilizado quando não queremos manter uma estrutura exterior à tabela, de
modo que não podemos aumentar o espaço de endereçamento inde�nidamente. Esse método prevê a divisão da tabela em três
partições.
O tratamento de colisões com encadeamento interior é utilizado quando não queremos manter uma estrutura exterior à tabela, de
modo que possamos aumentar o espaço de endereçamento inde�nidamente. Esse método prevê a divisão da tabela em duas
partições.
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 3
Sobre a principal característica do hashing perfeito, é correto o que se a�rma em:
O hashing perfeito apresenta resultados excelentes para o melhor caso quando consideramos um conjunto dinâmico de chaves;
O hashing perfeito apresenta resultados excelentes para o caso médio quando consideramos um conjunto estático de chaves;
O hashing perfeito apresenta resultados excelentes para o pior caso quando consideramos um conjunto dinâmico de chaves;
O hashing perfeito apresenta resultados excelentes para o pior caso quando consideramos um conjunto estático de chaves;
O hashing perfeito apresenta resultados excelentes para o caso médio quando consideramos um conjunto estático de chaves.
0,25 pontos   Salva
a.
b.
c.
d.
e.
PERGUNTA 4
Uma alternativa para a estruturação de dados que possa viabilizar, por exemplo, a operação de busca, é a utilização de tabelas de
endereço direto. A ideia, nesse tipo de abordagem, é acessar o dado de forma direta através de seu endereço, sem que seja necessária a
leitura de outros dados. Nesse contexto, selecione a alternativa CORRETA dentre as disponíveis abaixo.
As tabelas de endereçamento direto funcionam bem para chaves que estejam previamente ordenadas;
As tabelas de endereçamento direto funcionam bem para chaves independente de estarem previamente ordenadas;
As tabelas de endereçamento direto funcionam bem para chaves de tamanho �xo;
As tabelas de endereçamento direto funcionam bem para chaves de tamanho variável;
As tabelas de endereçamento direto funcionam bem para chaves estrangeiras.
0,25 pontos   Salva
Salvar todas as respostas Salvar e Enviar
? Estado de Conclusão da Pergunta:
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/execute/courseMain?course_id=_628440_1
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453836_1&mode=reset
https://bb.cruzeirodosulvirtual.com.br/webapps/blackboard/content/listContent.jsp?course_id=_628440_1&content_id=_8453850_1&mode=reset