Estrutura de dados - 2 Período - Estácio EAD

Prévia do material em texto

Cr
ea
te
d 
in 
M
as
te
r P
DF
 E
dit
or
25/09/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/6
Avaliando
Aprendizado
 
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS   
Aluno(a): MAX CLEITON SOUZA PEREIRA 202301116058
Acertos: 1,8 de 2,0 25/09/2023
Acerto: 0,2  / 0,2
A complexidade computacional é uma abstração para facilitar a comparação de algoritmos de forma
independente do ambiente de execução e de variações na sua entrada. As complexidades podem ser
representadas pelo número de operações requeridas. Dentre as seguintes complexidades de pior caso,
representadas pelo seu número de operações, qual é a melhor? (menos operações)
2n
(nlog n)/2
 100n + 5log n
2n2
nlog n + 500
Respondido em 25/09/2023 19:54:56
Explicação:
O conceito de complexidade é assintótico, ou seja, o que importa é quando o tamanho da entrada n cresce
arbitrariamente. Por isso, os termos dominantes de cada resposta são os únicos relevantes. 500n é assintoticamente
menor que n2, por exemplo, pois para n acima de 500 o quadrado de n será maior que 500n. Dessa forma podemos
ordenar em forma crescente de complexidade os termos dominantes das respostas: n, nlog n, n2, 2n. O menor deles é
n, logo a resposta correta é 100n+5log n.
Acerto: 0,2  / 0,2
Uma lista circular é uma estrutura de dados contínua, permitindo que seja iterada sobre ela de forma in�nita.
Uma das suas aplicações em jogos digitais é:
Em jogos de um jogador para armazenar um conjunto �xo de elementos.
 Em jogos multijogador em turnos, permitindo ceder o controle a um jogador por vez.
Em jogos multijogador para garantir que apenas um dos jogadores jogue todas as vezes.
Em jogos mobile, para armazenar o número do telefone do jogador.
Em jogos competitivos, para garantir que não há scripts ou bots rodando no computador.
Respondido em 25/09/2023 19:55:28
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:voltar();
Cr
ea
te
d 
in 
M
as
te
r P
DF
 E
dit
or
25/09/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/6
Explicação:
A grande virtude das listas circulares é o fato delas poderem ser percorridas um elemento por vez, de forma in�nita.
Apenas quando todos os elementos forem percorridos uma vez, começarão a ser percorridos pela segunda vez, na
mesma ordem. Essa disposição é excelente para a implementação de políticas ¿Round robin¿, ou seja, onde cada
jogador tem a sua vez de jogar e as vezes são igualmente distribuídas entre os jogadores.
Por isso a resposta correta é em jogos multijogador em turnos, permitindo ceder o controle a um jogador por vez.
Acerto: 0,2  / 0,2
Seja a seguinte árvore binária de busca, marque a opção que apresenta o percurso em pré-ordem dessa árvore:
D,B,E,F,C,A
F,C,E,B,A,D
A,B,C,D,E,F
 A,D,C,E,B,F
D,A,B,E,C,F
Respondido em 25/09/2023 19:55:51
Explicação:
A resposta correta é a questão E. O percurso em pré-ordem é de�nido como se segue. A partir da raiz r da árvore T,
percorre-se a árvore da seguinte forma:
1 - visita-se a raiz;
2 - percorre-se a subárvores esquerda de T, em pré-ordem e
3 - percorre-se a subárvores direita de T, em pré-ordem.
Resultado da pesquisa pré-ordem:
 Questão3
a
Cr
ea
te
d 
in 
M
as
te
r P
DF
 E
dit
or
25/09/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/6
Acerto: 0,2  / 0,2
Um percurso é uma forma organizada de acesso à informação armazenada nos nós de uma estrutura de dados.
Sobre Árvores Binárias de Busca, marque a opção correta:
Toda árvore binária de busca tem altura proporcional a n, onde n é o número de nós na árvore.
Toda árvore binária de busca tem altura proporcional a log n, onde n é o número de nós na árvore.
Não é possível remover um nó interno com dois �lhos de uma árvore binária de busca.
 No pior cenário, uma busca por um elemento em uma árvore binária de busca pode exceder O(log n) ,
chegando a n  passos nessa busca.
Toda nova chave inserida em uma árvore binária de busca é inserida na raiz da árvore.
Respondido em 25/09/2023 19:56:15
Explicação:
No pior cenário, os nós de uma árvore podem estar inseridos de tal forma a causar desbalanceamento progressivo,
levando a n  passos em caso de busca por um elemento.
Acerto: 0,2  / 0,2
Um vetor está armazenado em memória no endereço-base 24. Considerando que uma palavra em memória
ocupa 1 byte, e esse vetor é constituído por elementos que ocupam 4 palavras, qual é o endereço de memória
ocupado pelos elementos de índices 2 e 50 respectivamente? .
28 e 224
26 e 74
28 e 220
 32 e 224
32 e 220
Respondido em 25/09/2023 19:56:50
Explicação:
Para calcular o endereço absoluto em memória você deve utilizar a fórmula A=B+t*i . No caso B é o endereço base
(24), t é o tamanho de cada elemento (4) e i é o índice do elemento (2 e 50). Aplicando a fórmula temos 32=24+2*4  e
224=24+50*4
 Questão4
a
 Questão5
a
Cr
ea
te
d 
in 
M
as
te
r P
DF
 E
dit
or
25/09/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/6
Acerto: 0,0  / 0,2
Uma Pilha é uma estrutura de dados que permite o armazenamento de elementos (ou nós) sequencialmente.
Sobre as Pilhas é possível a�rmar que:
Permitem inserção no seu �nal e remoção apenas no seu início.
Permitem inserção ou remoção apenas no seu início ou no seu �nal.
Permitem inserção ou remoção em qualquer de suas posições.
 Permitem inserção no seu início e remoção apenas no seu �nal.
 Permitem inserção ou remoção apenas no seu início.
Respondido em 25/09/2023 19:59:28
Explicação:
A Pilha, assemelhando-se ao seu conceito na vida real, permite inserções e remoções apenas no seu início (push e
pop). Dessa forma, implementa a política ¿First In, Last Out¿ (FILO) na qual o nó que chegou há menos tempo será
sempre removido primeiro. As demais respostas indicam outras estruturas como listas, �las e deques.
Acerto: 0,2  / 0,2
Marque a opção correta acerca da visita In-Ordem, usada em percursos de árvores binárias de busca:
 O percurso in-ordem inicia a visita nas sub-árvores a esquerda em ordem simétrica, depois visita a raiz
da árvore e depois as sub-árvores à direita em ordem simétrica.
O percurso in-ordem inicia a visita nas sub-árvores a direita, depois visita a raiz da árvore e depois as
sub-árvores à esquerda em ordem simétrica.
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois
as sub-árvores à direita em ordem simétrica, terminando pela raiz principal.
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois
as sub-árvores à direita em ordem assimétrica.
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois
as sub-árvores à direita em ordem simétrica.
Respondido em 25/09/2023 20:00:57
Explicação:
O percurso em ordem simétrica (In-ordem) é de�nido como se segue. A partir da raiz r da árvore T, percorre-se a
árvore da seguinte forma:
1 - percorre-se a sub-árvores esquerda de T, em ordem simétrica e
2 - visita-se a raiz;
3 - percorre-se a sub-árvores direita de T, em ordem simétrica.
Acerto: 0,2  / 0,2
A complexidade de execução é uma medida da e�ciência de um algoritmo. Ela indica o número de operações que
o algoritmo precisa realizar para completar a sua tarefa, em função do tamanho da entrada. Nesse sentido,
marque a opção correta sobre a análise de complexidade das operações de rotação em árvores AVL:
 Questão6
a
 Questão7
a
 Questão8
a
Cr
ea
te
d 
in 
M
as
te
r P
DF
 E
dit
or
25/09/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/6
As rotações simples e duplas possuem complexidade de execução O(n2).
As rotações simples e duplas possuem complexidade de execução O(n).
As rotações simples e duplas possuem complexidade de execução O(n log n).
 As rotações simples e duplas possuem complexidade deexecução O(1).
As rotações simples e duplas possuem complexidade de execução O(logn).
Respondido em 25/09/2023 20:01:19
Explicação:
As operações de rotação simples e duplas são utilizadas tanto na inserção quanto na remoção de nós de árvore AVL e
servem de auxílio para tornar um nó que foi desbalanceado seja balanceado novamente. Essas operações incluem
trocas de ponteiros entre os nós, ou seja, O(1), o que não penaliza a complexidade de execução das operações na
árvore.
Acerto: 0,2  / 0,2
Em Python é possível implementar um array utilizando o tipo padrão list. Essa implementação permite o uso das
seguintes funções para inserir e remover um elemento, respectivamente:
insert, delete/pop.
impose, remove/destroy.
insert, remove/destroy.
 append, remove/pop.
append, pop/delete.
Respondido em 25/09/2023 20:01:54
Explicação:
Em Python a função append insere um elemento ao �nal da lista. As funções "remove" e "pop" podem remover um
elemento, de maneiras diferentes. Remove tira um elemento conhecido usando o seu conteúdo, já pop remove um
elemento usando seu índice, ou seja, a sua posição na lista.
Acerto: 0,2  / 0,2
Uma Lista pode ser implementada de forma contígua ou encadeada. No caso de uma lista ordenada
implementada de forma encadeada, as complexidades de pior caso de busca, inserção e remoção são
respectivamente:
 O(n), O(n) e O(n).
O(log n), O(n) e O(n).
O(n), O(n) e O(1).
O(1), O(n) e O(n).
O(n), O(1) e O(n).
Respondido em 25/09/2023 20:02:14
Explicação:
A busca é O(n) pois no pior caso você terá que percorrer toda a lista sequencialmente até encontrar o último
elemento. Já a inserção, no seu pior caso, colocará um elemento no �nal da lista, uma operação simples, mas a busca
para achar a posição correta já é O(n). A remoção de qualquer nó também é uma operação de custo constante,
 Questão9
a
 Questão10
a
Cr
ea
te
d 
in 
M
as
te
r P
DF
 E
dit
or
25/09/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/6
bastando reapontar um ponteiro, mas a busca pelo nó a ser removido também é O(n), o que faz a operação de
remoção também possuir complexidade O(n).