Estácio_ GabaritoSimuladoEstrutura de dados em Python01

Prévia do material em texto

06/04/2023, 09:13 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305580929&cod_prova=6146816559&f_cod_disc=… 1/5
 
Meus
Simulados
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS EM PYTHON   
Aluno(a): ELBA LUCIA DA SILVEIRA ARAUJO DA MATA 202001039368
Acertos: 6,0 de 10,0 05/04/2023
Acerto: 1,0  / 1,0
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)
nlog n + 500
 100n + 5log n
2n2
2n
(nlog n)/2
Respondido em 06/04/2023 08:11:48
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: 1,0  / 1,0
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:
 append, remove/pop.
insert, remove/destroy.
insert, delete/pop.
append, pop/delete.
impose, remove/destroy.
Respondido em 06/04/2023 08:12:07
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
06/04/2023, 09:13 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305580929&cod_prova=6146816559&f_cod_disc=… 2/5
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: 1,0  / 1,0
Matrizes podem ser implementadas em Python utilizando a biblioteca numpy, trazendo diversas funções já
implementadas. Dentre os pares de função com sua funcionalidade a seguir, qual é o correto?
matriz.max() retorna o desvio padrão da matriz.
matriz.min() retorna o valor médio da matriz.
matriz.std() retorna a variância da matriz.
matriz.mean() retorna o valor mínimo da matriz.
 matriz.sum() retorna a soma dos elementos da matriz.
Respondido em 06/04/2023 08:13:01
Explicação:
Dentre os pares apresentados, o único correto é o da função sum() que é a soma dos elementos. std() e mean() são
funções estatísticas que retornam o desvio padrão e a média respectivamente. max() retorna o elemento de maior
valor e min(), por sua vez, retorna o elemento de menor valor.
Acerto: 0,0  / 1,0
Suponha que você está implementando um programa que precisa armazenar dados ordenados em uma
estrutura para serem tratados posteriormente, na ordem inversa à que foram recebidos. Haverá uma grande
quantidade de recebimentos e tratamento de dados, mas o tamanho esperado da estrutura não deve variar
muito. Qual tipo de estrutura de dados é a melhor nessa situação?
Lista em alocação contígua.
Lista simplesmente encadeada.
 Fila.
 Pilha.
Lista duplamente encadeada.
Respondido em 06/04/2023 08:17:35
Explicação:
A pilha permite o tratamento de nós usando a política requerida, FILO ¿ ¿�rst in last out¿ -. Além disso, as operações de
inserção e remoção são O(1), ou seja, de complexidade constante, a melhor possível. Isso condiz com o requisito de
que haverá muitas operações desse tipo. Por �m, o fato de a estrutura não variar muito em tamanho permite o uso de
uma alocação contígua e otimizada para a pilha. A �la não obedece a lógica FILO e as listas têm complexidade de
inserção e remoção O(n) sendo muito piores que a pilha, principalmente quando o número desses tipos de operação é
grande.
Acerto: 1,0  / 1,0
 Questão3
a
 Questão4
a
 Questão5
a
06/04/2023, 09:13 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305580929&cod_prova=6146816559&f_cod_disc=… 3/5
Uma Deque é uma estrutura de dados mais generalista que as pilhas e �las. Para implementá-la de forma
e�ciente, você pode usar:
Pilha com 1 variável: topo.
 Lista duplamente encadeada com 2 variáveis: início e �nal.
Lista contígua com 1 variável: início.
Fila com 2 variáveis: início e �nal.
Lista simplesmente encadeada com nó cabeça.
Respondido em 06/04/2023 08:20:30
Explicação:
Para implementar uma deque e�cientemente, você precisa ter um ponteiro para o início e o �nal da deque, permitindo
inserções e remoções em ambas as pontas com complexidade O(1) , sem  a necessidade de percorrer a estrutura, o
que seria O(n).
Além disso, a �la é uma especialização da deque. Ou seja, toda �la é um deque, mas nem toda deque é uma �la.
Podemos assim eliminar a resposta contendo �la. A resposta restante que possui 2 variáveis é a correta. Lista
duplamente encadeada. Ela permite a inserção e remoção nas extremidades com complexidade O(1).
A lista contígua e a simplesmente encadeada com nó cabeça levariam a operação de inserção e remoção ao �nal da �la
terem complexidade O(n) por precisarem percorrer toda a estrutura, sendo também descartadas.
Acerto: 1,0  / 1,0
Em uma implementação da estrutura de dados do tipo �la, você possui um espaço de memória contíguo a ela
alocada com capacidade para M nós. A variável da �la é F, e duas variáveis guardam os índices do início e �nal da
�la (inicioF e �nalF).  Em uma implementação otimizada de F, como podemos identi�car que a �la está cheia?
 InicioF==(�nalF+1)mod M
InicioF==�nalF + 1
InicioF== �nalF
FinalF== M
InicioF = M
Respondido em 06/04/2023 08:21:00
Explicação:
Em uma implementação otimizada da �la, é usado um sistema modular, onde o início e o �nal da �la se movem a cada
inserção e remoção. A cada inserção, �nalF aumenta em 1, até o máximo M, depois volta para 0 e assim por diante. A
cada remoção inícioF aumenta em 1, até o máximo M e depois volta a 0. dessa forma a �la está cheia quando
(�nalF+1)modM é igual a inicio.
Acerto: 0,0  / 1,0
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 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.
 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.
 Questão6
a
 Questão7
a
06/04/2023, 09:13 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305580929&cod_prova=6146816559&f_cod_disc=… 4/5
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.
Respondido em 06/04/2023 08:22:38
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,0  / 1,0
Seja a seguinte árvore binária. Analise as a�rmativas e marque a correta.
 Aobuscar pelo nó 45 na árvore acima, um algoritmo de busca em Python irá realizar sempre
O(n) passos. Isto ocorre uma vez que é necessário analisar todos os nós da árvore para encontrar o nó
45.
A árvore acima possui 4 nós folhas.
Supondo que a árvore em questão é uma árvore binária de busca, a inserção de um novo nó com chave
47 pode ser feita em qualquer subárvore vazia.
 A �gura ilustra uma árvore binária de busca porque para todos os nós vale a seguinte propriedade: os
nós contidos na subárvores esquerda são menores que a raiz e os contidos na subárvore direita são
maiores.
É possível inserir mais um nó �lho ao nó 30.
Respondido em 06/04/2023 08:44:47
Explicação:
A árvore é uma árvore binária de busca porque dado um nó qualquer da árvore, os nós contidos na subárvore
esquerda são menores que a raiz e os a direita, maiores que a raiz. A busca só seria executada em O(n) caso a árvore
fosse uma árvore zig zag.  47 só poderia ser inserido à direita de 45. A árvore tem 3 folhas. Arvores binárias só podem
ter nós com grau 2.
Acerto: 1,0  / 1,0
Existem vários tipos diferentes de árvores de busca, como árvores binárias, AVL e árvores B. Nesse sentido,
marque a opção correta sobre os procedimentos de rotação em árvores AVL:
 Questão8
a
 Questão9
a
06/04/2023, 09:13 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305580929&cod_prova=6146816559&f_cod_disc=… 5/5
Uma rotação dupla à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
esquerda.
Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
esquerda.
Uma rotação dupla à direita de um nó x acontece quando um desbalanceamento de x acontece à direita.
 Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
direita.
Uma rotação simples à direita de um nó x acontece quando um desbalanceamento de x acontece à
direita.
Respondido em 06/04/2023 08:31:54
Explicação:
Em uma árvore AVL, uma rotação simples à esquerda de um nó acontece quando um desbalanceamento de  acontece
à direita. Se um nó  desbalanceia para um lado, ele deve rotacionar de forma inversa para �car balanceado.
Acerto: 0,0  / 1,0
Seja as seguintes a�rmações sobre árvores binárias:
I - Os nós que não possuem �lhos são chamados de nós folhas.
II - O nó raiz é um nó na árvore que não possui antecessor (ou não tem pai).
III - As árvores binárias são estruturas não lineares.
Estão corretas as a�rmativas:
I, apenas.
III, apenas.
 I, II e III.
II e III, apenas.
 I e II, apenas.
Respondido em 06/04/2023 08:43:38
Explicação:
Os nós que são folhas não possuem apontamentos para outros nós, ou seja, não possuem �lhos. Por outro lado, um nó
raiz não possui pai, ou seja, não tem apontadores antecessores. Árvores binárias são estruturas que não possuem
linearidade.
 Questão10
a